python - 递归树遍历将结果添加到python中的嵌套字典

Question

我正在尝试对一棵树进行递归遍历。我的 class Node 有方法 get_children，我用它来理解应该停止遍历。我面临的困难是我生成的字典应该呈现一个带有遍历结果的嵌套结构。如果遍历本身是微不足道的，那么附加子元素就不是(我试图用 dfs/bfs 解决)

我的示例树如下所示:

class Node:

    def __init__(self, parent=None, lft=None, rght=None, children=[]):
        self.value = 'random_value'
        self.parent = parent
        # lft and rght probably don't make much sense(cause node can have >2 children) but they are present in the Node structure
        self.lft = lft
        self.rght = rght
        self.children = children


    def get_children(self, node):
        return self.children


n1 = Node()
n2 = Node()
n3 = Node()
n4 = Node()
n5 = Node()
n6 = Node()
n7 = Node()
n8 = Node()
# adding connections as on the picture above
n1.lft = n2
n1.rght = n3
n1.children = [n2, n3]

n2.parent = n1

n3.parent = n1
n3.rght = n4
n3.children = [n4]

n4.parent = n3
n4.rght = n5
n4.children = [n5]

n5.parent = n4
n5.lft = n7
n5.rght = n6
n5.children = [n6,n7,n8]

n6.parent = n5
n7.parent = n5
n8.parent = n5

我的 dfs 和 bfs 允许我遍历树。但我还必须将一些路径传递到结果字典中的当前位置，以便插入新的子值，这变得非常麻烦。

我的尝试:

# try bfs
@staticmethod
def breadth_first_search(root):
    import collections

    res_dict = {
        "node": {
            "name": root.name,
            "children": []
        }
    }

    visited = set()
    queue = collections.deque([root])

    current = ["node", "children"]

    while queue:
        vertex = queue.popleft()

        for idx, neighbour in enumerate(vertex.get_children()):
            # logic
            # gets difficult to track the nested levels in the resulting dict, now it always appends to the ["node"]["children"] and don't pay attention to the nested levels
            res_dict["node"]["children"].append(neighbour)

            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

# try with dfs
@classmethod
def dfs(node):
    if not node.get_children():
        return node
    else:
        for idx, child_node in enumerate(node.get_children()):
            # logic
            # gets difficult to track the nested levels in the dict

            return Node.dfs(child_node)

我想要达到的结果:

 desired_dict = {
        # root
        "node": n1.value,
        "children": [
            {
                "name": n2.value,
                "children": []
            },
            {
                "name": n3.value,
                "children": [
                    {
                        "name": n4.value,
                        "children": [
                            {
                                "name": n5.value,
                                "children": [
                                  {
                                    "name": n6.value,
                                    "children": []
                                  },
                                  {
                                    "name": n7.value,
                                    "children": []
                                  },
                                  {
                                    "name": n8.value,
                                    "children": []
                                  }
                                ]
                            }
                        ]
                    }
                ]
            }
        ]
    }

如何递归遍历树并在遍历时创建结构如 desired_dict 的 dict？

REPL

Answer 1

您可以使用 DFS 来完成任务。您需要将字典传递给 DFS 以用树的当前节点填充它。在调用下一级 DFS 之前创建一个新的字典并将其放入当前字典的 children 数组中

python代码中的思路:

def dfs(node, ndict):
    ndict["value"] = node.value
    ndict["children"] = []
    for idx, child in enumerate(node.get_children()):
        child_dict = {}
        dfs(child, child_dict)
        ndict["children"].append(child_dict)