python - 水平填充二叉树

Question

为了更好地理解递归函数，我尝试为二叉树创建一个 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 上。我怎样才能让这个同时考虑节点的左右 child ？

Answer 1

为此，您实际上不需要带有左右指针的节点结构。只需将整棵树存储在一个数组中，以便索引 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