我正在尝试使用传入整数的列表或数组实现来创建树。它们需要在进入时添加到树中。下面的代码是我到目前为止所拥有的,但是在输入了大约第5个数字之后,前面的一些元素被覆盖了。我不知道如何纠正这个问题。我是Python的新手,但有Java的背景知识。我试图学习不同的数据结构是如何在其他语言中实现的。你知道吗
编辑: 一些样本输入是6,8,3,9,2,1。它们将被单独输入,直到输入了sentinel值(在本例中为“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;
如果您真的只是尝试将“$”符号插入到数组中,以逐级填充二叉树(但实际上并不关心树中值的顺序,那么这可能就是您想要的:
如您所见,每个级别完成后,
update
函数会添加正确数量的$
元素来填充下一个级别:元素的值将被忽略,它们只是在接收时放入树中,在分配下一个级别之前填充每个级别。随机输入看起来是一样的:
给出您的示例代码,我认为您实际上想要创建一个最小堆。如果是这样的话,您仍然可以使用这个答案作为起点,您只需要扩展功能来添加比较和交换函数来维护heap属性。下面是添加
restore_heap
函数的示例:如您所见,这会在每次插入后恢复堆:
相关问题 更多 >
编程相关推荐