在二叉树插入中，只有左树是右树。正确的树是错误的

Question

我有一个btree类和一个insert函数，可以在树的宽度方向上插入节点。但树没有在右侧插入节点。

我正在创建根节点。insert函数将左、右节点正确插入根节点。

然后递归地，我尝试在左侧节点插入两个节点，在右侧节点插入两个节点。但在这一步中，所有节点仅添加到左侧。节点也会添加到无父节点。

我知道，我在插入函数中的最后一个语句中犯了一个错误。但是我尝试了很多组合，但是都导致了一些错误。

class BinTree(object):
  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None

  def insert(self,val):
    if self.left is None:
      self.left = BinTree(val)
    elif self.right is None:
      self.right = BinTree(val)
    elif self.left:
      self.left.insert(val)
    else:
      self.right.insert(val)

root = BTree('A')
root.insert('B')
root.insert('C')
root.insert(None)
root.insert('D')
root.insert(None)
root.insert('E')
root.insert('F')

Expected:
                 A
              /     \
             B       C
            /\       /\
        None  D  None  E
             /
            F

Getting:
                 A
              /     \
             B       C
            / \
        None   D
         /  \
     None    E
       /
      F

Answer 1

你不能用你保存的当前字段通过递归真正得到你想要的结果。每个节点只“知道”它的当前状态，这就是为什么你树的右侧将永远保持在深度1。

我想到的一个解决方案是添加一个右孩子和左孩子金额字段。这将有助于跟踪余额。它看起来像这样：

 class Node(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.right_count = 0
        self.left_count = 0
        self.even_depth = True
        self.needed_to_even = 1

    def insert(self, val):
        if self.left is None:
            self.left = Node(val)
            self.left_count += 1
        elif self.right is None:
            self.right = Node(val)
            self.right_count += 1
        elif self.left_count > self.right_count + self.needed_to_even or not self.even_depth:
            self.even_depth = False
            if self.left_count == self.right_count:
                self.needed_to_even *= 2
                self.even_depth = True
            self.right.insert(val)
            self.right_count += 1
        else:
            self.left.insert(val)
            self.left_count += 1

Answer 2

您的树完全按照代码建议进行构建。

插入函数检查是否有一个空子节点，并设置是否找到了一个--否则它将递归向左（无论其长度如何），这正是您得到的树。

其次，您的输出不清楚-添加None是什么意思？

为了实现完整树的构建，你需要计算你的元素。

然后我们将能够使用计数除以2来找到正确的路径（取叶子或右边），直到到达正确的叶子。添加self.cnt=1到构造函数。将此用于插入的伪代码：

insert:
    cnt = self.cnt++ // Increase the count and get the new value
    while (cnt > 0) {
        path.push(cnt % 2 == 0 ? left : right) // If even, go left. Else go right.
        cnt = cnt / 2
    }
    path.reverse // We need to start from the last element we pushed
    current = head
    while (path not empty)
        current = current.path.pop
    current = val

试着看一下树的编号，以便更好地理解它：

             1
           /   \
          2     3
         / \   /  \
        5   6 7    8

Answer 3

一旦你的代码在那里找到一个不是无的节点，它就会向左遍历，这就像深度优先搜索（DFS）。所以代码不会再看右边是否还有一些空缺需要填补，而是向左移动。这会导致你的树偏向左边。

相反，您应该使用广度优先搜索（BFS）来搜索树中的下一个空缺，因此以广度优先的顺序进行搜索。为此，您可以使用一个单独的方法来执行此BFS并返回空缺的位置（通过提供其父节点以及新的子节点应该位于哪一侧）。

以下是新方法的外观：

def next_free(self):
    queue = [self]
    while len(queue):
        node = queue.pop(0) # Here you get the nodes in BFS order
        if node.val is None: # Cannot have children
            continue
        for side, child in enumerate((node.left, node.right)):
            if child is None: # Found the first vacancy in BFS order!
                return node, side
            queue.append(child)

现在，插入方法变得微不足道：

def insert(self,val):
    node, side = self.next_free()
    if side == 0:
        node.left = Node(val)
    else:
        node.right = Node(val)

你可以看到它在repl上运行。信息技术