递归解析树的所有级别

Question

递归解析此树结构的所有级别的最佳方法是什么。三个层次是第一个，但它应该如何继续解析剩余的数据？这是来自我无法完成的可容性测试。问题还有很多，但这就是我卡住的地方。

tree = (5, (8, (12, None, None), (2, None, None)),(9, (7, (1, None, None), None), (4, (3, None, None), None)))

def recurse(T):
    calc = 0
    def do_calc(T, calc):
        if T == ():
            return calc
        calc += 1
        return do_calc(T[1:], calc)
    return do_calc(T, calc)

print recurse(tree)

Answer 1

通常，当递归使用 binary trees 时，您只需处理手头的节点并递归到 children，如果有的话。 "trick" 是将 children 或子分支视为树本身。您还必须确定终止递归的边缘条件。

您当前的代码将采用初始节点，即树的根，递增累加器 calc 并递归调用 do_calc 元组的其余部分 .这不同于递归到 children。由于根节点是一个三元组，recurse(tree) 将 return 3。边缘条件是与空元组的比较。

看来你要数树的节点数：

def tree_count(tree):
    # The edge condition: if a node is falsy (None, empty, what have you),
    # then terminate the recursion
    if not tree:
        return 0
    # Unpack the node, nicer to work with.
    value, left, right = tree
    # Count this node and recurse in to children.
    return 1 + tree_count(left) + tree_count(right)

另一方面，如果您的最终目标是对树的值求和：

def tree_sum(tree):
    # The edge condition
    if not tree:
        return 0             
    value, left, right = tree
    # Sum this value and the values of children, if any
    return value + tree_sum(left) + tree_sum(right)

如果您的实际树是 k-ary tree 或只是一棵每个节点具有不同数量 children 的树：

def tree_sum(tree):
    if not tree:
        return 0
    # This still makes the assumption that the value is the 1st item of
    # a node tuple
    value, children = tree[0], tree[1:]
    # In python3:
    #value, *children = tree
    return value + sum(tree_sum(child) for child in children)

如前所述，代码假设节点是一个元组，其中第一个元素包含值，就像提供的示例数据一样。没有看到 实际数据 就不可能做得更好。如果碰巧你的节点实际上是(left, value, right)元组左右，相应地修改。

Answer 2

看起来你想获得树的深度。这是递归的典型解决方案：

tree = (5, (8, (12, None, None), (2, None, None)),(9, (7, (1, None, None), None), (4, (3, None, None), None)))

def tree_depth(node):

    if not isinstance(node, tuple):
        return 1
    else:
        return max(tree_depth(subnode) for subnode in node) + 1

print tree_depth(tree)

输出为5.

示例代码中使用了内置函数max and generator expression。

递归解析树的所有级别

recursively parse all of the levels of tree

python

recursion

binary-tree