ошибка в создании сбалансированного двоичного дерева с использованием Java

Question

Я написал этот код для создания binary tree, но выглядит как этот код создает unbalanced binary tree. Узлы получают только на поддерево rightroot. Я получаю Null pointer exception, если пытаюсь получить доступ к дочерним узлам левого поддерева. Я хочу создать balanced binary tree с узлами, вставленными из left to right. Какую ошибку я делаю здесь и как ее исправить?

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

Вам нужно хранить количество элементов для каждого суб-дерева на каждом дереве-узел, как это:

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