0

二分木を横断して、各ノードの現在の値に「newvalue」を追加しようとしています。

デフォルト(ノード、2):

前：

      1
     / \
    2   3
   /\   /
  5  6  7

後：

      3
     /\
    4  5
   /\  /
  7  8 9

これに再帰的にどのようにアプローチすればよいですか?!

4

2 に答える 2

2

Harold は非常にクリーンで一般的な例を提供してくれました。これは、バイナリツリーで機能する注釈付きのテイクです

再帰アルゴリズムでは、次の 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 に答える