java - Java中如何向完全二叉树插入节点？

Question

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

//fields
private T item;
private int size;
private CBTree<T> left, right;

//add method
public void add(T item) 
{
    if(left == null)
    {
        left = new CBTree<T>(item);
        size += left.size;
    }
    else if(right == null)
    {
        right = new CBTree<T>(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 的左子节点。我知道发生这种情况是因为以下行将这棵树的根重新分配为左节点根的 child 。

left.add(item);

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

Answer 1

仅仅检查 child 的 child 来确定去哪一边是不够的，因为一旦树达到高度 4，它就不再起作用了，因为根的 child 的 child 不会从此改变指向前方，但我们仍然可以向左或向右走。

我想到了两种方法:

1. 每个节点都有一个完整变量。

   没有子节点的节点是完整的。

   具有 2 个大小相等的完整子节点的节点已完成。

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

2. 根据大小以数学方式确定子树是否完整。

   大小为 2^n - 1 的树已完成(对于某些 n)。

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

无论哪种方法，在进行插入时，如果满足以下任一条件，我们都会向左移动 (left.add(item)):

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

我会将实现细节留给您。

<小时/>

注意:在执行 left.add(item); 和 right.add(item); 时，您还需要更新大小。您可能只需在 add 函数中添加 size++ 即可，因为我们要添加 1 个元素，因此无论如何大小都会增加 1。