遍历二叉树以更改每个节点的值？

Question

我正在尝试遍历一个二叉树，把“newvalue”加到每个节点当前的值上。

def(node, 2):

之前的样子：

      1
     / \
    2   3
   /\   /
  5  6  7 

之后的样子：

      3
     /\
    4  5
   /\  /
  7  8 9

我应该如何用递归的方法来实现这个呢？

Answer 1

在编程中，有时候我们需要处理一些数据，可能会用到数组。数组就像一个盒子，里面可以放很多东西，比如数字、字母等。每个东西都有一个位置，我们可以通过这个位置来找到它。

当我们想要从数组中取出某个特定的东西时，我们需要知道它的位置。这个位置通常是从0开始的，也就是说，第一个东西的位置是0，第二个是1，以此类推。

如果我们想要把新的东西放进数组里，我们也需要指定一个位置。如果这个位置已经有东西了，新的东西就会替换掉原来的东西。

总之，数组是一个很方便的工具，可以帮助我们整理和管理数据，让我们更容易找到和使用这些数据。

def add_value(node, delta):
    node.value += delta
    for child in node.children:
        add_value(child, delta)

Answer 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)

如果你有任何问题，请告诉我。如果这个练习是在学校给你的，他们其实只是想让你认识到这是一个简单的树遍历，也就是在遍历树的时候改变节点的值。我建议你尝试自己编写所有不同的树遍历方法，不要看笔记。这样你会对树和递归有很多了解。