python - “倒着”建树

Question

我需要在 Python 中创建一个树状结构。我有一个函数 get(parentId)，它返回一个包含该父对象的对象列表——我认为这应该递归完成。

结果应该是这样的：["root object", ["child1 of root", "child2 of root", ["child2-1", "child2-2"]]]

每个对象都有一个属性 parent，即 get() 的 parentId，但作为起点，我只有根对象。

Answer 1

树有一个标准的数据结构，它不是列表的列表。

创建一个 class Node，其属性children包含一个list（或者set，如果您不关心顺序）“子”节点。还要创建一个方法，该方法add_child采用一个节点，设置该节点的parent，并将其添加到children列表中。就像是：

class Node(object):
    def __init__(self, children={}):
        self.parent = None
        self.children = children

    def add_child(self, child):
        child.parent = self
        self.children.add(child)

要遍历树，只需询问根的孩子，然后是他们的孩子，等等。这可以递归地完成，但为了速度和内存效率，您可能希望在 Python 中迭代地完成。

def walk(root):
    yield root
    for child in root.children:
        for elt in walk(child):
            yield elt

---

当然，这已经做过很多次了，所以你不应该自己写它，除非它是家庭作业或学习练习。

由于 HTML/XML 文档的结构类似于树，因此您可能应该将许多 DOM 树库之一用于实际数据结构。尝试xml.dom.minidom或lxml。

Answer 2

假设您仍然对树的列表表示感兴趣（这不一定是无用的事情），这是一个递归函数定义，我相信它可以满足您的需求（前提是该get()函数确实之前已定义）：

def build_tree(node):
    return [node,[build_tree(child) for child in get(node)]]

您可以以类似于以下方式使用它：

root = 1  # or whatever other representation you may use for root
list = build_tree(root)
print list