バイナリツリーはノードを正しく追加していますか？次のように

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

をしかし、私は、ノード1-6を追加するときには、6の高さを返し、ない7。ここで

は私のバイナリツリーのコードです：

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

は、私はこの問題は木に私のノードを追加していると思いますが、私は他の例を見て撮影しましたが、それらはすべて同じことをやっているように見えます私は..だから私は問題を認識できない！

ありがとうございます！あなたが戻った

-1 node==nullに、我々は持っている例えば、我々が1-2を追加した場合ので、私たちは葉に到着したときに、条件が真である0

を返すべきとき

Answer 1

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

}高
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(leftof(1),rightof(1))よう= 1+Max(0,1+Max(0,0)) =
1+Max(0,1+0) =
1+1=2。

height(null)を前の例の-1に置き換えて、自分で確認してください。

ところで、あなたのBinaryTreeの実装は実際にはバイナリ検索ツリーです。なぜなら、あなたは右の左の大きな要素に要素を入れていないからです。検索ツリーがあなたの意向であるならば、しかし一般的なバイナリツリーであれば、add関数を変更する必要があります。