完美的二叉树与正确的数据

Question

我遇到了一个问题，试图用正确的数据填充具有已知数量节点的完美二叉树。基本上，我有一个实现创建了这个:

     7
  5     6
 1 2   3 4

然而，我想创建一个这样的树:

     7
  3     6
 1 2   4 5

我目前插入树节点的实现如下:

def _add_node(self, val, ref = None):
    # reference to root of tree
    ref = self.root if ref is None else ref
    if ref.right is None:
        ref.right = Node(val, ref)
        return
    elif ref.left is None:
        ref.left = Node(val, ref)
        return
    else:
        parent = (val - 1) / 2
        if parent % 2 == 0:
            self._add_node(val, ref.left) 
        else:
            self._add_node(val, ref.right)

给定x节点，我使用range(x)创建树，每次迭代调用add_node(i)。除了顺序不正确之外，它可以正常工作。

对于我的生活，我想不出一个简单的方法来设置值来表示底部布局而不是顶部。有人能帮我吗?

Answer 1

这似乎与您输入数据的顺序有关。你是如何传递数据的?

还要考虑你的实现。检查右子节点是否为空，如果为空，就把节点放在那里。但是，如果不是，则继续移动到左侧节点。这就是问题所在。

假设您以倒叙时间顺序传递数据，则从根位置7开始。然后你移动到6，你把它放在右边的节点。然后移到5;您检查右节点是否为空，实际上不是，因为它被6填充，所以您继续检查左节点是否为空，结果发现它是空的。所以把5放在这里。

你看到问题了吗?

您需要找出一种方法来解决这个问题，但希望这对您的调试有帮助。

祝你好运!