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.Main 클래스 =

패키지 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) }

로 삽입 메소드를 호출한다

---->

인서트 (15, NULL)

I이 널 매번하세요 이것은 타나 교체 현재 노드 초래 t 노드.

전화를 걸 때 root1 참조가 null이고 내 루트를 가리키지 않는 이유를 알아낼 수 없습니까?

추가 정보 : insertData에서 통화 중

그것()을 삽입하는(). say insertData (15)를 두 번째로 호출하는 동안 insert (15, this.root) -> insert (node, root1)를 호출합니다. 하지만이 root1 참조가 null로 밝혀졌습니다.하지만이 루트를 검사 할 때 정확한 루트 노드를 나타냅니다.

고마워요!

Answer 1

좋아, 여기 당신이 첫 번째 요소를 삽입하면

는

(10)를 삽입, 당신의 코드에 대한 건조 실행이 API insert은 코드에 따라 당신을 위해 새로운 루트를 만들고 그것을 값을 설정합니다 10,

지금 제 2 삽입가 흥미있게,

스택 트레이스

을 happenes 무엇을보고

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 인수는 null이고 첫 번째 조건이 실행 됨). 이전에 정의 된 루트는 삭제됩니다. 이것이 루트를 다시 무시하는 문제를 일으키는 원인입니다.

Answer 2

첫 번째 노드 즉 루트를 삽입 한 후 왼쪽 및 오른쪽 노드는 null입니다. 다음 번에 왼쪽 또는 오른쪽 자식 노드를 삽입하는 동안 해당 조건을 확인하지 않습니다.

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