如何在不覆盖以前输入的值的情况下使用整数列表创建树

Question

我正在尝试使用传入整数的列表或数组实现来创建一个树。它们需要在输入时添加到树中。下面的代码是我到目前为止所拥有的，但是在输入了大约5个数字之后，前面的一些元素被覆盖了。我不确定如何纠正这个问题。我是Python的新手，但对Java有一定的背景知识。我正在尝试学习不同的数据结构是如何在其他语言中实现的。

编辑:一些样本输入将是6,8,3,9,2,1。它们将被单独输入，直到输入一个标记值(在本例中为'end')。“$”表示一个空元素，所以如果首先输入6，它就是根元素。那么8就是它的正确的孩子。如果输入的数字不小于6，则根的左子元素将是"$“。一旦使用上面的值打印了树，它应该会反映附加的图片。Expected Output

binaryTree = ["$","$"];
counter = 0;

def update(user_input):        
    if(binaryTree[0] == "$"):  # set root
        binaryTree[0] = user_input;
        binaryTree.append("$");
        counter += 1;
    elif(binaryTree[counter] == "$"):  # if current element is empty

        if(user_input >= binaryTree[counter-1]):    # setting rightChild
            binaryTree.append("$");
            rightChild = ((counter - 1)*2)+2;
            binaryTree[rightChild] = user_input
        elif(user_input < binaryTree[counter -1]):  # setting leftChild
            binaryTree.append("$");
            leftChild = ((counter-1)*2)+1;
            binaryTree[leftChild] = user_input;
        binaryTree.append("$");
        counter += 1;
    else:                              # if current element is NOT empty
        if(user_input >= binaryTree[counter-2]):
            binaryTree.append("$");
            rightChild =((counter-2)*2)+2;
            binaryTree[rightChild] = user_input;
        elif(user_input < binaryTree[counter -2]):
            binaryTree.append("$");
            leftChild = ((counter-2)*2)+1;
            binaryTree[leftChild] = user_input;
        counter += 1;

Answer 1

如果您真的只是尝试将"$“符号插入到数组中以逐层填充二叉树(但您真的不关心树中值的顺序，那么这可能就是您想要的：

import math


class BinaryTree(object):

    def __init__(self):
        self.binary_tree = ["$"]
        self.counter = 1
        self.height = 0

    def update(self, user_input):
        self.binary_tree[self.counter - 1] = user_input
        new_level = int(math.floor(math.log(self.counter + 1, 2)))
        if new_level > self.height:
            self.binary_tree.extend(["$"] * (2 ** new_level))
            self.height += 1
        self.counter += 1


bt = BinaryTree()
while True:
    i = int(input())
    bt.update(i)
    print(bt.binary_tree)

正如您所看到的，随着每一层的完成，update函数将添加正确数量的$元素来填充下一层：

$ python tree.py
1
[1, '$', '$']
1
[1, 1, '$']
1
[1, 1, 1, '$', '$', '$', '$']
1
[1, 1, 1, 1, '$', '$', '$']
1
[1, 1, 1, 1, 1, '$', '$']
1
[1, 1, 1, 1, 1, 1, '$']
1
[1, 1, 1, 1, 1, 1, 1, '$', '$', '$', '$', '$', '$', '$', '$']

元素的值被忽略，它们只是在接收时被放入树中，在分配下一层之前填充每一层。随机输入看起来是一样的：

$ python q.py
2
[2, '$', '$']
5
[2, 5, '$']
3
[2, 5, 3, '$', '$', '$', '$']
6
[2, 5, 3, 6, '$', '$', '$']
2
[2, 5, 3, 6, 2, '$', '$']
2
[2, 5, 3, 6, 2, 2, '$']
76
[2, 5, 3, 6, 2, 2, 76, '$', '$', '$', '$', '$', '$', '$', '$']
3
[2, 5, 3, 6, 2, 2, 76, 3, '$', '$', '$', '$', '$', '$', '$']

根据您的示例代码，我认为您实际上想要创建一个min heap。如果是这样的话，您仍然可以使用这个答案作为起点，您只需要扩展功能来添加比较和交换函数来维护堆属性。下面是一个添加restore_heap函数的示例：

class BinaryTree(object):

    def __init__(self):
        self.binary_tree = ["$"]
        self.counter = 1
        self.height = 0

    def update(self, user_input):
        index = self.counter - 1
        self.binary_tree[index] = user_input
        new_level = int(math.floor(math.log(self.counter + 1, 2)))
        if new_level > self.height:
            self.binary_tree.extend(["$"] * (2 ** new_level))
            self.height += 1
        self.counter += 1
        self.restore_heap(index)

    def restore_heap(self, index):
        parent_index = (index - 1) / 2
        if parent_index < 0:
            return
        elif self.binary_tree[index] < self.binary_tree[parent_index]:
            tmp = self.binary_tree[parent_index]
            self.binary_tree[parent_index] = self.binary_tree[index]
            self.binary_tree[index] = tmp
        self.restore_heap(parent_index)

如您所见，这将在每次插入后恢复堆：

16
[16, '$', '$']
15
[15, 16, '$']
14
[14, 16, 15, '$', '$', '$', '$']
13
[13, 14, 15, 16, '$', '$', '$']
12
[12, 13, 15, 16, 14, '$', '$']
11
[11, 13, 12, 16, 14, 15, '$']
10
[10, 13, 11, 16, 14, 15, 12, '$', '$', '$', '$', '$', '$', '$', '$']
9
[9, 10, 11, 13, 14, 15, 12, 16, '$', '$', '$', '$', '$', '$', '$']
8
[8, 9, 11, 10, 14, 15, 12, 16, 13, '$', '$', '$', '$', '$', '$']