이진 검색 트리에 삽입 할 수 없습니다.

Question

이진 검색 트리에 삽입 및 인쇄를 구현할 때. 첫 번째 루트 노드 만 출력합니다. 왜 도와 주시겠습니까? 바이너리 검색 트리의 기본 구현. 처음에는 학습을 시작하고 고급 항목으로 이동하지만 첫 번째 단계에서는 걸림돌이됩니다. 루트 노드에 노드를 추가하지 않는 것 같습니다.

class bstrees{ 
class Node 
{ 
    int data; 
    Node left; 
    Node right; 
    public Node(int data) 
    { 
     this.data=data; 
     this.left=null;  
     this.right=null; 
    } 
} 
Node root; 
bstrees(){root=null;} 

public void insert(int data){ 
    root=insert_node(root,data); 
} 
public Node insert_node(Node r,int n){ 
    if(r==null){ 
     Node n1=new Node(n); 
     //root=n1; 
     return n1 ; 
    } 
    else if(root.data<=n){ 
     insert_node(root.right,n); 
    } 
    else{ 
     insert_node(root.left,n); 
    } 
    return r; 
} 
public void print_t(){ 
    print_t(root); 
} 
private void print_t(Node r){ 
    //System.out.println(r); 
    if(r!=null){ 

    // System.out.println(r.left);   
    // System.out.println(r.right); 
     print_t(r.left); 
     System.out.println(r.data+" "); 
     print_t(r.right); 
    } 

} 


} 
public class BST_prac { 
public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    bstrees b1=new bstrees(); 
    b1.insert(5); 
    b1.insert(1); 
    b1.print_t(); 

} 

} 

그것은 단지 트리에 값 1 삽입 호출에

Answer 1

5. insert_node(root.left,n) 호출은 새로운 노드를 생성 출력한다, 그러나 새롭게 생성 된 노드에 대한 참조가 저장되어 있지 않은 트리 자체가 효과적으로 변경되지 않는다는 것을 의미합니다. 참조는 새로 생성 된 노드의 부모 노드에 저장되어야합니다. 노드가 오른쪽 하위 트리에 삽입되는 경우에도 마찬가지입니다.

Answer 2

Codor에서 언급 한대로 새 노드를 삽입 할 때 왼쪽 노드 또는 오른쪽 노드에 추가 할 것인지 여부와 같이 부모 노드의 참조를 저장하지 않습니다. 항상 새로운 노드를 생성합니다. 삽입 메소드에서 코드 작업을하기 위해 약간의 변경을했습니다.

public void insert(int data){ 
     //creating root node if root node itself is null 
     if(root==null){ 
      root =new Node(data); 
     } else { 
      root=insert_node(root, data, null, null); 
     } 
     //System.out.println("after insert root data is " + root.data); 
    } 
    public Node insert_node(Node node, int n, String dir, Node parent){ 
     //traverse and insert in proper nodes 
     //assign left or right child based on some logic i have taken direction as string here. 
     if(node == null) { 
      Node n1 = new Node(n); 
      if(dir.equalsIgnoreCase("left")) { 
       parent.left = n1; 
      } else { 
       parent.right = n1; 
      } 
     } 
     else if(root.data<=n){ 
      parent = root; 
      insert_node(root.right, n, "right", parent); 
     } 
     else{ 
      parent = root; 
      insert_node(root.left, n, "left", parent); 
     } 
     return root; 
    }