java - 节点未添加到树

Question

我一直在尝试integer binary search tree使用 Java 创建一个，由于某种原因，我在向树中添加新节点时出错了。

这是NODE课程。

class NODE
{
    NODE left = null, right = null;
    int info;
    public NODE(int x)
    {
        info = x;
    }
}

这是带有该方法的BST(Binary Seaatch Tree) 类。insert()

class BST
{
    NODE tree = null;
    public void insert(int x)
    {
        NODE node = new NODE(x);
        NODE temp = tree;
        while(true)
        {
            if(temp == null)
            {
                temp = node;
                break;
            }
            else if(temp.info > x) temp = temp.left;
            else temp = temp.right;
        }
    }
    //other methods present here
}

由于我无法弄清楚的原因，该 insert()方法出错了。

即使在调用方法之后，对象也会tree包含在其中。nullinsert()

你能在代码中找到一些参差不齐的地方吗？

谢谢！

Answer 1

在类中使用递归insert方法NODE（而不是像您那样使用无限循环）：

public void insert(int x) {
        if(x < this.info) {
            if(this.left == null)
                this.left = new NODE(x);
            else
                this.left.insert(x);
        }
        else {
            if(this.right == null)
                this.right = new NODE(x);
            else
                this.right.insert(x);
        }
    }

并且您的BST课程将具有以下insert方法（只需调用其他insert方法）：

public void insert(int x) {
    if(tree == null)
        tree = new NODE(x);
    else
        tree.insert(x);
}

maininsert方法在NODE类中，因为它必须在树中的节点上递归调用自身。

Answer 2

当然 tree 仍然为空 - 你没有为这个字段分配任何东西。在 temp = 树之后；和 temp = 节点；只有温度改变了，树没有改变。

Answer 3

insert() 方法应该将节点的子节点插入树中，调用已声明的节点作为参数。例如：

//Returns true/false depending on whether the insert is successful
public boolean insert(int x, Node node, boolean leftChild) {      
    if (node == null) return false;
    Node child = new Node(x);
    if (leftChild) {
        if (node.left != null) return false;
        node.left = child;
    } else {
        if (node.right != null) return false;
        node.right = child;
    }
    return true;
}