4

我为节点制作了自定义类

class NodeTree(object):
    def __init__(self, name = None, children = None):
        self.name = name
        self.children = children

并定义了一个创建树的函数（一个包含其子节点的节点）

def create_tree(d):
    x = NodeTree()
    for a in d.keys():
        if type(d[a]) == str:
            x.name = d[a]
        if type(d[a]) == list:
            if d[a] != []:
                for b in d[a]:
                    x.add_child(create_tree(b))
    return x

输入是一个 dict，其中一个参数用于节点名称和一个列表，其子节点与父节点的形式相同。该函数工作正常，我已经制作了证明它的方法，但我找不到正确遍历它并获得树的高度的方法。我不知道“高度”是否是正确的术语，因为我知道它可能是矛盾的，我需要将节点计为度量单位，如下所示：

                                      parent
                                         |
                                         |
                                     ---------
                                     |       |
                                    child   child

这棵树的高度是 2，我已经尝试了一切，从类中的计数器到标签，一切似乎都退化了，我从来没有得到正确的高度。我应该如何处理？

4

1 回答 1

4

要为您的树创建一个确定节点高度的递归height方法（即，从该节点到叶子的路径中的最大节点数）：

def height(self):
    if not self.children:  # base case
        return 1
    else:                  # recursive case
        return 1 + max(child.height() for child in self.children)

其他树遍历也可以递归完成。例如，下面是一个生成器方法，它以“预先顺序”（即每个父节点在其子节点和死节点之前）生成树节点的名称：

def preorder(self):
    yield self.name
    for child in self.children:
        yield from child.preorder() # Python 3.3 only!

该yield from循环中的语法在 Python 3.3 中是新的。您可以通过以下方式在早期版本中获得相同的结果：

        for descendent in child.preorder():
            yield descendent
于 2012-12-05T19:17:04.917 回答