遍历非二进制

Question

我为节点创建了自定义类

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

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

^{pr2}$

输入是一个dict，其中一个参数用于节点名，一个列表及其子节点的形式与父节点相同。 这个函数运行得很好，我已经提出了方法来证明它，但我找不到一种方法来遍历它，得到树的高度。我不知道“高度”是否正确，因为我知道它可能是矛盾的，我需要将节点计数为度量单位，如下所示：

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

这棵树的高度是2，我尝试了所有的方法，从计数器到类中的标签，所有的东西似乎都退化了，我从来没有得到正确的高度。 我该怎么做？在

Answer 1

要为树创建一个递归的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)

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

^{pr2}$

该循环中的yield from语法在Python3.3中是新的。您可以在早期版本中使用此选项获得相同的结果：

        for descendent in child.preorder():
            yield descendent