在BST中插入一个节点

Question

我试图在我的自定义BST中插入节点。第一次调用insertData方法时，新节点以root身份正确插入。问题发生在第二次和后续调用中。

下面是我的代码：

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

Tree类=

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 。用法;

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）{ 插入件（15,10） }

这使得调用insert方法---->

插入（15，NULL）

每次我得到这个空，这导致当前节点替换袋鼠t节点。

我无法弄清楚为什么在调用过程中，root1引用为空而不是指向我的根？

更多信息：

从insertData在通话过程中

它（）来插入（）。说我在第二次调用insertData（15）时，我打电话插入（15，this.root） - > insert（node，root1）。但是这个root1引用原来是null.but当我检查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参数为空，第一个条件被执行），放弃以前定义的根。这是什么导致你的问题，你一遍又一遍地重写你的根。

Answer 2

插入第一个节点（即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) 
    { 
     if(root1.getLeftChild()==null) 
      root1.setLeftChild(node); 
     else 
      root1.setLeftChild(insert(node,root1.getLeftChild())); 
    } 
    else if(node.compareTo(root1) >0) 
    { 

     if(root1.getRightChild()==null) 
      root1.setRightChild(node); 
     else 
      root1.setRightChild(insert(node,root1.getRightChild())); 
    } 

return root1; 
}