python - 如何使用整数列表创建树而不覆盖先前输入的值
问题描述
我正在尝试使用传入整数的列表或数组实现来创建树。它们需要在输入时添加到树中。下面的代码是我到目前为止的代码,但是在输入了大约 5 个数字之后,之前的一些元素被覆盖了。我不确定如何纠正这个问题。我是 Python 的新手,但有 Java 的背景知识。我正在尝试了解如何用其他语言实现不同的数据结构。
编辑:一些样本输入将是 6,8,3,9,2,1。它们将分别输入,直到输入标记值(在本例中为“结束”)。'$' 代表一个空元素,所以如果先输入 6,那将是根。那么 8 将是它的右孩子。如果没有输入小于 6 的数字,则根的左孩子将是“$”。使用上述值打印树后,它应该反映所附图片。 预期产出
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, '$', '$', '$', '$', '$', '$']
推荐阅读
- java - 在 Android 上启动任何地图应用程序
- java - 快速排序算法修改
- ios - AdMob 通过 Test Flight 进行测试和构建,而不是来自 App Store?
- python - 超级缩减字符串 python
- c++ - 计算用箭头和鼠标移动的对象
- php - 为附加整数的配置文件用户名编写 .htaccess
- java - SocketIO Java 客户端通过 NodeJS 的快速 Web 服务器获取发出的数据
- python-xarray - dataset.assign_attrs() 例子?
- git - 新的 VSTS Git 私有存储库
- typescript - 无法为类型创建键入的快捷方式