python - 在Python中从二叉序列创建二叉树

Question

我正在尝试从像“100101”这样的二进制序列创建一棵树然后我希望像这样创建树。 (基本上1表示向右，0表示向左)

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

所以我在这里做的是代码:其中值是字符串序列(例如值 =“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

，但我真的很难过，因为我的函数将覆盖旧树。

Answer 1

问题出在处理现有节点的代码上。如果存在，代码将使用新的 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

如果还没有节点，这只会分配一个节点，然后将当前节点设置为这个新节点。