如何在Java中将节点插入完整的二叉树？

众所周知，当插入完整的二叉树时，我们必须从左到右填充所有叶子的所有叶子。 我有以下方法将节点插入完整的二叉树。

//fields private T item; private int size; private CBTree left, right; //add method public void add(T item) { if(left == null) { left = new CBTree(item); size += left.size; } else if(right == null) { right = new CBTree(item); size += right.size; } else if(!((left.left != null) && (left.right != null)) && ((right.left == null) || (right.right == null))) { left.add(item); } else { right.add(item); } } 

这个实现的问题是，在第11个节点之后，它将第12个节点添加到8的左子节点而不是6节。我知道发生了这种情况，因为以下行将该树的根重新分配为该节点的左子节点。根。

 left.add(item); 

所以它将root更改为2.有没有办法将root更改回原始值？ 我试图在不使用堆栈和队列的情况下完成此任务。

Answer 1

仅仅检查孩子的孩子来确定去哪一侧是不够的，因为一旦树达到高度4就不再有效，因为根的孩子的孩子从那时起不会改变我们仍然可以向左或向右走。

我想到了两种方法：

1. 在每个节点上都有一个complete变量。

   没有子节点的节点已完成。

   完成具有2个完全相同大小子节点的节点。

   每当更新树（插入或删除）时，您也会为每个受影响的节点更新此变量。

2. 根据大小在数学上确定子树是否完整。

   大小为2^n - 1树是完整的（对于某些n ）。

   注意：只有在不保持树完整的情况下我们不允许自由删除元素时，这才有效。

对于这两种方法，在进行插入时，如果满足以下任一条件，我们向左（ left.add(item) ）：

• 左子树不完整
• 左右子树的大小相同（都是完整的，这意味着我们通过此插入增加高度）

我将把实施细节留给您。

---

注意：执行left.add(item);需要更新大小left.add(item); 和right.add(item); 。 你可能只需要在add函数中add一个size++ ，因为我们添加了1个元素，所以无论如何大小都会增加1。

Answer 2

感谢Dukeling的回答，实现该方法的正确方法是在数学上确定子树是否已满。 这是代码：

 //fields private T item; private int size; private CBTree left, right; //add method public void add(T item) { if(left == null) { left = new CBTree(item); } else if(right == null) { right = new CBTree(item); } else if(leftFull()) { right.add(item); } else { left.add(item); } size++; } //Checks if the left subtree is full public boolean leftFull() { int used, leafs = 1; while(leafs <= size + 1) { leafs *= 2; } leafs /= 2; used = (size + 1) % leafs; if(used >= (leafs / 2)) { return true; } else { return false; } }