我试图创建一个使用列表或来电整数数组实现的树。他们需要为他们进入被添加到树。下面的代码是什么,我有这么远,但各地进入了第5号之后,以前的一些元素都被覆盖。我不能确定如何解决此问题。我是全新的Python的,但在Java的背景知识。我想学习不同的数据结构是如何在其他语言中实现。
编辑:一些样品投入将是6,8,3,9,2,1。直到警戒值被输入(在这种情况下,“结束”),他们将分别进入。的“$”在那里表示一个空元素,所以如果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;
如果你真的只是想插入“$”符号到一个数组填写逐级二叉树水平(但你真的不关心在树中值的排序,那么这可能是你想要什么:
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, '$', '$', '$', '$', '$', '$', '$']
鉴于你的示例代码,我觉得你真的想创建一个最小堆。如果是这样的话,你仍然可以使用这个答案为出发点,你只需要扩展添加的比较和交换功能,以保持堆属性的功能。下面是增加了一个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, '$', '$', '$', '$', '$', '$']