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

debugcn 发表于 Dev

褪色

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

//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。我知道发生这种情况是因为以下行将这棵树的根重新分配为根。

left.add(item);

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

褪色

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

//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);
    }
    else if(right == null)
    {
        right = new CBTree<T>(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;
    }
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。