1

「100101」のようなバイナリシーケンスからツリーをバイナリ作成しようとしています。このようにツリーを作成したいと思います。（基本的に1は右に行くことを意味し、0は左に行くことを意味します）

                                <Root node>
                                    |
                                    1
                                   /
                                  0
                                 /
                                0
                                 \
                                  1
                                 /
                                0
                                 \
                                  1

だから私はここでそれをしましたコードです：ここで値は文字列シーケンスになります（例：value = "1001"）

def _inserto(root,value):
    for i in value:
        if root == None:
            root = BSTNode(i)
            current = root
        elif i == "1":
            if current.right is not None:
                current.right = BSTNode(i)
                current = current.right
            else:
                current.right = BSTNode(i)
                current = current.right
        elif i == "0":
            if (current.left is not None):
                current.left = BSTNode(i)
                current = current.left
            else:
                current.left =BSTNode(i)
                current = current.left
    return root

ここで問題となるのは、「01」のような別のシーケンスを入力する場合、ツリーは次のようになるはずです。

                            <Root Node>
                                |
                                1
                               /
                              0
                             / \
                            0   1
                             \
                              1
                             /
                            0
                             \
                              1

、しかし、私の関数が古いツリーを上書きしようとしているので、私は本当に苦労しています。

4

1 に答える 1

2

問題は、既存のノードを処理するコードにあります。存在する場合、コードはそれを新しいBSTNodeで上書きし、その下にある既存のノードをすべて失います。必要なものは次のようなものです。

    elif i == "1":
        if current.right is None:
            current.right = BSTNode(i)
        current = current.right
    elif i == "0":
        if root.left is None:
            current.left = BSTNode(i)
        current = current.left

これにより、ノードがまだ存在しない場合にのみノードが割り当てられ、この新しいノードに現在のノードが設定されます。

于 2012-07-22T23:17:28.250 に答える