java - 节点未添加到树中

Question

我一直在尝试使用 Java 创建一个整数二叉搜索树，但由于某种原因，我在向树添加新节点时出错了。

这是NODE 类。

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

这是带有 insert() 方法的 BST(二叉搜索树)类。

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() 方法出错了。

即使在调用 insert() 方法之后，对象 tree 仍会在其中携带 null。

你能在代码中发现一些不稳定的地方吗？

谢谢!

Answer 1

在 NODE 类中使用递归 insert 方法(而不是像您那样利用无限循环):

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

主要的 insert 方法位于 NODE 类中，因为它必须在树中的节点上递归地调用自身。