java - 在 BST 中插入节点

Question

我正在尝试在自定义 BST 中插入节点。第一次调用 insertData 方法时，新节点作为根正确插入。第二次及后续调用时出现问题。

下面是我的代码:

1.节点类=

package ishan.trees.tree;

class Node implements Comparable<Node> {

private int data;
public int getData() {
    return data;
}

public void setData(int data) {
    this.data = data;
}

public Node getLeftChild() {
    return leftChild;
}

public void setLeftChild(Node leftChild) {
    this.leftChild = leftChild;
}

public Node getRightChild() {
    return rightChild;
}

public void setRightChild(Node rightChild) {
    this.rightChild = rightChild;
}

private Node leftChild;
private Node rightChild;

public Node(int data,Node leftChild,Node rightChild)
{
    this.data=data;
    this.leftChild=leftChild;
    this.rightChild=rightChild;

}

@Override
public int compareTo(Node o) {
    if(o.getData() > this.data)
    return -1;

    if(o.getData() < this.data)
        return 1;

    return 0;
}
}

树类=

package ishan.trees.tree;

public class Tree {

private Node root=null;

public Node getRoot() {
    return root;
}

public void insertData(int data)
{
    Node node=new Node(data,null,null);
    insert(node,this.root);

}

private Node insert(Comparable<Node> node,Node root1)
{
        if(root1==null)
        {//insert as first element ie root
            this.root=new Node(((Node)node).getData(),null,null);
        }
        else if(node.compareTo(root1) <0)
        {
            root1.setLeftChild(insert(node,root1.getLeftChild()));
        }
        else if(node.compareTo(root1) >0)
        {

            root1.setLeftChild(insert(node,root1.getRightChild()));
        }

 return root1;  
}
}

3.主类=

包 ishan.trees.usage;

import ishan.trees.tree.Tree;

public class Usuage {

public static void main(String a[])
{
    Tree tree=new Tree();
    tree.insertData(10); //---------1
    tree.insertData(15); //---------2
    tree.insertData(9);  //---------3
    tree.insertData(4);  //---------4
}
}

当我调试第二个调用时，它是这样的:

插入数据(15){ 插入(15,10)}

调用插入方法为 ---->

插入(15,空)

我每次都得到这个空值，这会导致当前节点替换根节点。

我不明白为什么在通话过程中，root1 引用为空并且不指向我的根？

更多信息:

在从 insertData() 到 insert() 的调用期间。说在第二次调用 insertData(15) 期间，我调用了 insert(15,this.root) -->insert(node,root1) 。但这个 root1 引用结果是空的。但是当我检查 this.root 时它指的是正确的根节点..

谢谢!

Answer 1

好的，这里是您的代码的试运行，

插入 10。

当您插入第一个元素时，此 API insert 会根据您的代码为您创建一个新的根并将其值设置为 10，

现在第二次插入变得有趣，看看会发生什么

堆栈跟踪

insertData(15);
insert(node,root) // here root is your actuall root, originally initialized when u inserted first

// it goes to last else if inside insert api
root1.setRightChild(insert(node,root1.getRightChild())); // see now, this apis actually calls insert again, coz new node value was greater then root value

// this is how next stack trace will look like, as root right child was null
insert(node,null); // observer second argument is null again

现在，根据您的插入代码，最终将再次创建根(root1 参数为空，执行第一个条件)，丢弃先前定义的根。这就是导致您问题的原因，您一次又一次地覆盖您的根目录。