Ist mein Binärbaum richtig Knoten hinzuzufügen?

Question

Ich habe gerade eine Methode, um die Höhe meiner binären Baum Implementierung zu testen, wie folgt:

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

Aber es gibt eine Höhe von 6 und 7 nicht, wenn ich die Knoten 1-6 hinzuzufügen.

Hier ist mein Binary Tree Code:

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

Ich denke, das Problem ist mein Knoten in dem Baum hinzufügen, aber ich habe einen Blick auf andere Beispiele genommen, aber sie scheinen alle das gleiche tun werden Ich bin .. Also ich kann das Problem nicht erkennen!

Danke!

Answer 1

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

}

Sie kehrten -1 auf node==null wenn Sie 0.

Der Zustand zurückkehren sollte wahr ist, wenn wir Blatt ankommen, so zum Beispiel, wenn wir 1-2 hinzufügen, dann haben wir Höhe wie 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.

Versuchen Sie, height(null) durch -1 im vorherigen Beispiel zu ersetzen, um selbst zu sehen.

Übrigens ist Ihre BinaryTree-Implementierung tatsächlich ein binärer Suchbaum, da Sie weniger Elemente auf die linken und größere Elemente auf der rechten Seite setzen. Wenn Sie einen Suchbaum haben, dann Ok, aber wenn Sie einen allgemeinen implementieren möchten Binärbaum dann sollten Sie die Add-Funktion ändern.