我的二叉樹是否正確添加節點？

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。

這裏是我的二叉樹代碼：

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。

嘗試用-1代替height(null)，以便自己查看。

順便說一句，你的BinaryTree實現實際上是一個二叉搜索樹，因爲你把更少的元素放在左邊，更大的元素放在右邊，如果搜索樹是你的意圖然後確定，但是如果你想實現一個普通的二叉樹，那麼你應該改變添加功能。