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

这只会在没有节点存在的情况下分配一个节点，然后将 current 设置为这个新节点。