Правильно ли добавлено мое двоичное дерево?

Question

Я только что создал метод, чтобы проверить высоту моего бинарного дерева реализации следующим образом:

public int height() { 
    return height(rootNode); 
} 
private int height(BinaryTreeNode node) { 
    if(node == null) return -1; 
    else return 1 + Math.max(height(node.getLeftChild()), height(node.getRightChild())); 
} 

Но она возвращает высоту 6, а не 7, когда я добавить узлы 1-6.

Вот мой Binary Tree код:

import java.util.ArrayList; 
import java.util.Iterator; 
import java.util.LinkedList; 
import java.util.Queue; 

public class BinaryTree<E extends Comparable<E>> 
{ 
    private class BinaryTreeNode 
    { 
     private E value; 
     private BinaryTreeNode leftChild, rightChild; 

     public BinaryTreeNode(E value) { 
      this(value, null, null); 
     } 

     public BinaryTreeNode(E value, BinaryTreeNode leftChild, BinaryTreeNode rightChild) { 
      this.value = value; 
      this.leftChild = leftChild; 
      this.rightChild = rightChild; 
     } 

     public E getValue() { 
      return value; 
     } 

     public BinaryTreeNode getLeftChild() { 
      return leftChild; 
     } 

     public BinaryTreeNode getRightChild() { 
      return rightChild; 
     } 

     public void setLeftChild(BinaryTreeNode newLeftChild) { 
      this.leftChild = newLeftChild; 
     } 

     public void setRightChild(BinaryTreeNode newRightChild) { 
      this.rightChild = newRightChild; 
     } 
    } 

    private BinaryTreeNode rootNode; 

    public BinaryTree() { 
     this.rootNode = null; 
    } 

    public void addNode(E value) { 
     if(rootNode == null) 
      rootNode = new BinaryTreeNode(value); 
     else 
      addNode(value, rootNode); 
    } 

    //TODO: Implement removeNode() 

    public void printLevelOrder() { 
     printLevelOrder(rootNode); 
    } 

    public int height() { 
     return height(rootNode); 
    } 

    public void inOrderTraversal() { 
     if(rootNode != null) inOrderTraversal(rootNode); 
     else System.out.println("The tree is empty!"); 
    } 

    private void addNode(E value, BinaryTreeNode node) { 
     if(node.getValue().compareTo(value) > 0) { 
      if(node.getLeftChild() != null) 
       addNode(value, node.getLeftChild()); 
      else 
       node.setLeftChild(new BinaryTreeNode(value)); 
     } else { 
      if(node.getRightChild() != null) 
       addNode(value, node.getRightChild()); 
      else 
       node.setRightChild(new BinaryTreeNode(value)); 
     } 
    } 

    private void printLevelOrder(BinaryTreeNode node) { 
     Queue<BinaryTreeNode> currentLevel = new LinkedList<BinaryTreeNode>(); 
     Queue<BinaryTreeNode> nextLevel = new LinkedList<BinaryTreeNode>(); 

     currentLevel.add(node); 

     while (!currentLevel.isEmpty()) { 
      Iterator<BinaryTreeNode> iter = currentLevel.iterator(); 
      while (iter.hasNext()) { 
       BinaryTreeNode currentNode = iter.next(); 
       if (currentNode.leftChild != null) { 
        nextLevel.add(currentNode.leftChild); 
       } 
       if (currentNode.rightChild != null) { 
        nextLevel.add(currentNode.rightChild); 
       } 
       System.out.print(currentNode.value + " "); 
      } 
      System.out.println(); 
      currentLevel = nextLevel; 
      nextLevel = new LinkedList<BinaryTreeNode>(); 

     } 
    } 

    private int height(BinaryTreeNode node) { 
     if(node == null) return -1; 
     else return 1 + Math.max(height(node.getLeftChild()), height(node.getRightChild())); 
    } 

    private void inOrderTraversal(BinaryTreeNode node) { 
     if(node != null) { 
      inOrderTraversal(node.leftChild); 
      System.out.println(node.getValue() + " "); 
      inOrderTraversal(node.getRightChild()); 
     } 
    } 

    public BinaryTreeNode getRoot() { 
     return rootNode; 
    } 
} 

Я думаю, что проблема заключается в добавлении моего узла в дерево, но я принял взглянуть на других примерах, но все они, кажется, делают то же самое Я .. Поэтому я не могу понять проблему!

Спасибо!

Answer 1

private int height(BinaryTreeNode node) { 
if(node == null) return 0; 
else return 1 + Math.max(height(node.getLeftChild()), height(node.getRightChild())); 

}

Вы возвращались -1 на node==null, когда вы должны вернуть 0.

условие истинно, когда мы приходим к листу так, например, если мы добавим 1-2, то мы имеем высота, как 1+Max(leftof(1),rightof(1)) =
1+Max(height(null),height(2)) =
1+Max(0,1+Max(leftof(2),rightof(2))) =
1+Max(0,1+Max(height(null),height(null))) =
1+Max(0,1+Max(0,0)) =
1+Max(0,1+0)
1+1=2.

Попробуйте заменить height(null) на -1 в предыдущем примере, чтобы увидеть сам.

Кстати, ваша реализация BinaryTree на самом деле является двоичным деревом поиска, поскольку вы помещаете меньше элементов в левый и более крупные элементы справа. Если дерево поиска - это ваше намерение, то Ok, но если вы хотите реализовать общий бинарное дерево, тогда вы должны изменить функцию добавления.