为了更好地理解递归函数,我尝试为二叉树创建一个 Python 脚本,该脚本插入值,在进入下一个之前完全填充级别。
这是我的树节点实现:
class Node:
def __init__(self, value):
self.value = value
self.right_child = None
self.left_child = None
self.parent = None
class Tree:
def __init__(self):
self.root = None
我现在遇到的问题是设置满足该标准的条件。
举个例子:这里我按顺序添加以下数字:12, 5, 18, 2, 9, 15, 19, 13, 17。因此,将东西放入下一级的唯一条件是父级已满。
_12_______
/ \
5 __18_
/ \ / \
2 9 15_ 19
/ \
13 17
这是我到目前为止所拥有的:
def insert(self,value):
if(self.root==None):
self.root=Node(value)
else:
self._insert(value,self.root)
def _insert(self, value, curNode):
if(curNode.left_child==None):
curNode.left_child=Node(value)
curNode.left_child.parent = curNode
elif(curNode.right_child==None):
curNode.right_child=Node(value)
curNode.right_child.parent = curNode
else:
self._insert(value,curNode.left_child)
给出:
_12_
/ \
__5 18
/ \
__2_ 9
/ \
15_ 19
/ \
13 17
因此忽略了所有正确的 child 。当然,问题出在我的代码的最后一个 else
上。我怎样才能让它同时考虑节点的左子节点和右子节点?
最佳答案
为此,您实际上不需要带有左指针和右指针的节点结构。只需将整个树存储在一个数组中,以便索引 N
处的节点的子节点位于 2*N+1
和 2*N+2
:
def print_tree(items, pos, level):
if pos >= len(items):
return
print('.' * level, items[pos])
print_tree(items, pos * 2 + 1, level + 1)
print_tree(items, pos * 2 + 2, level + 1)
print_tree([12, 5, 18, 2, 9 , 15, 19, 13, 17], 0, 0)
打印
12
. 5
.. 2
... 13
... 17
.. 9
. 18
.. 15
.. 19
这就是你想要的。
这称为 binary heap .
如果您正在寻找一棵搜索树(维护值顺序的树),并希望保持平衡,请查看 https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
关于python - 层次填充二叉树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56794909/