如何在Java中将节点插入完整的二叉树中? [英] How to insert a node into a complete binary tree in Java?

问题描述

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

As we all know, when inserting into a complete binary tree we have to fill all the children for all the leafs from left to right. I have the following method that inserts a node into a complete binary tree.

//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.根的子代.

The problem with this implementation is that after the 11th node it adds the 12th node to the left child of 8 instead of 6. I understand that this is happening because the following line is reassigning the root of this tree to be the left child of the root.

left.add(item);

因此它将根更改为2.是否有办法将根更改回其原始值?我试图在不使用堆栈和队列的情况下完成此操作.

So it is changing the root to 2. Is there a way to change the root back to its original value? I am trying to accomplish this without using stacks and queues.

推荐答案

由于Dukeling的回答，实现该方法的正确方法是数学确定子树是否已满.这是代码:

Thanks to Dukeling's answer, the correct way to implement the method was to mathematically determine if the subtree was full. Here is the code:

//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;
    }
}

这篇关于如何在Java中将节点插入完整的二叉树中?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！