Fehler beim Erstellen eines ausgeglichenen Binärbaums mit Java

Question

Ich habe diesen Code geschrieben, um eine binary tree zu erstellen, sieht aber so aus, als ob dieser Code eine unbalanced binary tree erstellt. Die Knoten werden nur auf dem Teilbaum right von root erhalten. Ich bekomme Null pointer exception, wenn ich versuche, auf Kindknoten des linken Teilbaums zuzugreifen. Ich möchte ein balanced binary tree mit Knoten erstellen eingefügt von left to right. Welchen Fehler mache ich hier und wie korrigiere ich ihn?

public class binTree { 

    public static class TreeNode{ 
     public int val; 
     public TreeNode left; 
     public TreeNode right; 

     public TreeNode(int val){ 
      this.val = val; 
      this.left = null; 
      this.right = null; 
     } 
    } 

    public TreeNode root; 

    public binTree(){ 
     this.root = null; 

    } 

    public void insert(int data){ 
     root = insert(root,data); 
    } 
    public TreeNode insert(TreeNode node,int data){ 

     if(node == null){ 
      node = new TreeNode(data); 
      //root = node; 
     } 
     else{ 
      if(node.left == null){ 
       node.left = insert(node.left,data); 
      } 
      else{ 
       node.right = insert(node.right,data); 
      } 
     } 
     return node; 

    } 


    public static void main(String args[]){ 
     binTree obj = new binTree(); 

     obj.insert(5); 
     obj.insert(11); 
     obj.insert(13); 
     obj.insert(1); 
     obj.insert(7); 
     obj.insert(21); 
     obj.insert(35); 
     System.out.println(obj.root.right.left.val); 
     System.out.println(obj.root.left.right.val); // this throws null pointer exception 
    } 

} 

Answer 1

Sie verlassen nun die Menge der Elemente für jeden Unterbaum an jedem Baum-Knoten wie folgt speichern müssen:

public class BinTree { 

    private TreeNode root; 

    public static class TreeNode { 

     public int val; 
     public int elements = 0; 
     public TreeNode left; 
     public TreeNode right; 

     public TreeNode(int val) { 
      this.val = val; 
      this.left = null; 
      this.right = null; 
     } 
    } 

    public BinTree() { 
     this.root = null; 
    } 

    public void insert(int data) { 
     root = insert(root, data); 
    } 

    private static int height(TreeNode node) { 
     int result = 0; 
     if (node != null) { 
      result++; 
      int total = node.elements; 
      int heightElements = 2; 
      while (total > heightElements) { 
       total -= heightElements; 
       heightElements *= 2; 
       result++; 
      } 
     } 
     return result; 
    } 

    public TreeNode insert(TreeNode node, int data) { 
     if (node == null) { 
      node = new TreeNode(data); 
     } else if (height(node.left) == height(node.right)) { 
      node.left = insert(node.left, data); 
     } else { 
      node.right = insert(node.right, data); 
     } 
     node.elements++; 
     return node; 
    } 

    public static void main(String args[]) { 
     BinTree obj = new BinTree(); 
     obj.insert(5); 
     obj.insert(11); 
     obj.insert(13); 
     obj.insert(1); 
     obj.insert(7); 
     obj.insert(21); 
     obj.insert(35); 

     System.out.println(obj.root.val); 
     System.out.println(obj.root.left.val); 
     System.out.println(obj.root.right.val); 
     System.out.println(obj.root.left.left.val); 
     System.out.println(obj.root.left.right.val); 
     System.out.println(obj.root.right.left.val); 
     System.out.println(obj.root.right.right.val); 
    } 
}