1

我正在尝试从像“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

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

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

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

于 2012-07-22T23:17:28.250 回答