在BST中插入节点

伊山·索尼（Ishan Soni）

我正在尝试在自定义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
}
}

当我调试第二个电话时，它是这样的：

insertData（15）{insert（15,10）}

它以---->的形式调用insert方法

插入（15，空）

我每次都获得此null，这导致当前节点替换了根节点。

我无法弄清楚为什么在通话期间，root1引用为null而不指向我的root？

更多信息：

在从insertData（）到insert（）的调用期间。在第二次调用insertData（15）时说，我对insert（15，this.root）-> insert（node，root1）进行了调用。但是这个root1引用结果为null。但是当我检查this.root时，它引用的是正确的根节点..

谢谢！

技师

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

插入10。

当您插入第一个元素时，此APIinsert将根据您的代码为您创建一个新的根并将其值设置为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

现在，按照您的插入代码，最终将再次创建root（root1参数为null，将执行第一个条件），并丢弃先前定义的root。这就是造成您的问题的原因，您一次又一次地覆盖了您的根源。

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

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