0

我正在尝试遍历二叉树以将“newvalue”添加到每个节点的当前值。

定义（节点，2）：

前：

      1
     / \
    2   3
   /\   /
  5  6  7

后：

      3
     /\
    4  5
   /\  /
  7  8 9

我应该如何递归处理这个问题？！

4

2 回答 2

2

哈罗德提供了一个非常干净和普遍的例子。这是一个带有注释的片段，适用于二叉树

使用递归算法，您必须考虑两件事：1. 基本情况 2. 递归调用

在你的例子中： - 基本情况=节点没有孩子。不会发生递归调用 - 递归调用 = 每个节点都是自己的迷你树，因此在每个子节点上调用函数

def increase_tree_values(node, delta):
    """ Increases/decreases the value of all nodes in the tree by the value 'delta'
    """

    # increase the current node's value
    node.value += delta

    # recursively call function on left child, if it exists
    if node.left_child:
        increase_tree_values(node.left_child, delta)

    # recursively call function on right child, if it exists
    if node.right_child:
        increase_tree_values(node.right_child, delta)



# presuming you have some binary tree called 'tree' already constructed
# increase all nodes in 'tree' by 2
increase_tree_values(tree, 2)

如果您有任何问题，请告诉我。如果这个练习是在学校提供给你的，他们实际上只是想让你把它识别为一个简单的树遍历，你可以在遍历树时更改节点的值。我建议您尝试编写所有不同的树遍历，而无需任何注释。这样你会学到很多关于树和递归的知识。

于 2013-03-08T06:13:08.580 回答
1 
def add_value(node, delta):
    node.value += delta
    for child in node.children:
        add_value(child, delta)
于 2013-03-08T05:08:30.127 回答