“倒着”造树

Question

我需要用Python创建一个类似树的结构。我有一个get（parentId）函数，它返回一个带有该父对象的对象列表——我认为应该递归地执行。在

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

每个对象都有一个属性parent，它是get（）的parentId，但是作为起点，我只有根对象。在

Answer 1

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

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

您可以使用类似的方法：

^{pr2}$

Answer 2

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

创建一个类Node，属性children包含子节点的list（或者{}，如果你不关心顺序的话）。还要创建一个方法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中迭代地执行。在

^{pr2}$

---

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

由于HTML/XML文档的结构类似于树，所以您可能应该为实际的数据结构使用许多DOM树库中的一个。尝试xml.dom.minidom或lxml。在