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

Question

我有一个btree类和一个insert函数，可以将节点插入到树中。但是树没有在右边插入节点。你知道吗

我正在创建根节点。insert函数将左、右节点正确地插入到根节点。你知道吗

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

我知道，我在insert函数的最后一个else语句中犯了一个错误。但我试过很多组合，但都有一些错误。你知道吗

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。你知道吗

我们想到的一个解决方案是添加right children和left children数量字段。这将有助于跟踪余额。它看起来是这样的：

 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

你的树是完全按照你的代码建议构建的。你知道吗

insert函数检查是否有空的子级，并设置是否找到了一个-否则它将递归地转到左边（不管它的长度），而这正是您得到的树。你知道吗

第二，您的输出不清楚—添加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

当您的代码在那里找到一个不存在的节点时，它将立即向左遍历，这类似于depth-first search（DFS）。因此，代码不会进一步查看右侧，以查看是否仍有一些空缺需要填补，但还是会转到左侧。这会导致偏向树的左侧。你知道吗

相反，您应该使用breadth-first search（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)

现在insert方法变得很简单：

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

你可以看到它在repl.it上运行。你知道吗