創建Java的二叉搜索樹

Question

因此，這裏的節點類：

public class Node 
{ 
    private int _info; 
    private Node _left; 
    private Node _right; 

    public Node() 
    { 
     //this._info = Integer.MIN_VALUE; 
     this._left = null; 
     this._right = null; 
    } 


    public int getInfo() 
    { 
     return _info; 
    } 

    public void setInfo(int _info) 
    { 
     this._info = _info; 
    } 

    public Node getLeft() 
    { 
     return _left; 
    } 

    public void setLeft(Node _left) 
    { 
     this._left = _left; 
    } 

    public Node getRight() 
    { 
     return _right; 
    } 

    public void setRight(Node _right) 
    { 
     this._right = _right; 
    } 
} 

如何創建樹：

public class BalancedBinaryTree 
{ 
    private ArrayList<Integer> _numbers; 
    private Node _root; 

    public BalancedBinaryTree(ArrayList<Integer> numbers) 
    { 
     this._numbers = new ArrayList<>(); 
     this._numbers.addAll(numbers); 
     Collections.sort(this._numbers); 

     this._root = new Node(); 

     this.create(this._root, 0, this._numbers.size()); 
    } 

    private void create(Node tree, int i, int j) 
    { 
     if (i < j) 
     { 
      int m = i + (j - i)/2; 

      tree.setInfo(this._numbers.get(m)); 

      tree.setLeft(new Node()); 
      create(tree.getLeft(), i, m); 

      tree.setRight(new Node()); 
      create(tree.getRight(), m + 1, j); 
     } 
    } 

此方法計算的深度：

public static int getDepth(Node node) 
    { 
     if (node == null) 
     { 
      return 0; 
     } 
     else 
     { 
      int max = 0; 
      if (getDepth(node.getLeft()) > getDepth(node.getRight())) 
      { 
       max = getDepth(node.getLeft()); 
      } 
      else 
      { 
       max = getDepth(node.getRight()); 
      } 
      return max + 1; 
     } 
    } 

而這些兩個組合應該按其級別打印該樹：

public static void printLevel(Node node, int levelToDisplay, int currentLevel) 
    { 
     if (node != null) 
     { 
      printLevel(node.getLeft(), levelToDisplay, currentLevel); 
      if (currentLevel == levelToDisplay) 
      { 
       System.out.print(node.getInfo() + " "); 
      } 
      currentLevel++; 
      printLevel(node.getRight(), levelToDisplay, currentLevel); 
     } 
    } 

    public static void printLevels(Node node) 
    { 
     for (int i = 0; i < getDepth(node); i++) 
     { 
      System.out.println("Level :" + i); 
      printLevel(node, i, 0); 
      System.out.println(); 
     } 
    } 

在測試類我：

testNumbers.add(15); 
    testNumbers.add(20); 
    testNumbers.add(25); 
    testNumbers.add(30); 
    testNumbers.add(35); 
    testNumbers.add(40); 
    testNumbers.add(45); 


    BalancedBinaryTree tree = new BalancedBinaryTree(testNumbers); 
    BalancedBinaryTree.printLevels(tree.getRoot()); 

而且我得到這樣的輸出：

Level :0 
0 15 20 30 
Level :1 
0 0 25 0 35 40 
Level :2 
0 0 0 45 
Level :3 
0 

我應該得到

Level :0 
30 
Level :1 
20 40 
Level :2 
15 25 35 45 

1. 有什麼不對的getDepth方法因爲它似乎會返回4級3的廣告？
2. 爲什麼還有其他節點？ （那些零）

我敢肯定，我解決了這個問題，但我會需要以下的解釋：

這是修改後的printlevel方法：

public static void printLevel(Node node, int levelToDisplay, int currentLevel) 
{ 
    if (node.getLeft() != null && node.getRight() != null)   
    { 
     printLevel(node.getLeft(), levelToDisplay, currentLevel+1); 
     if (currentLevel == levelToDisplay) 
     { 
      System.out.print(node.getInfo() + " "); 
     } 
     printLevel(node.getRight(), levelToDisplay, currentLevel+1); 
    } 
} 

，你可以請參閱我現在測試，如果當前節點有孩子，而不是檢查當前節點是否存在，這就是爲什麼這些零出現，因爲遍歷到達沒有在其右側和左側孩子分配信息的葉子。

我想了解的是增加currentLevel然後將它傳遞給printLevel的呼叫，並簡單地將currentLevel+1傳遞給呼叫之間的差異。它不應該是同一件事嗎？

而且getDepth功能：

public static int getDepth(Node node) 
{ 
    if (node.getLeft() == null && node.getRight() == null) 
    { 
     return 0; 
    } 
    else 
    { 
     int max = 0; 
     if (getDepth(node.getLeft()) > getDepth(node.getRight())) 
     { 
      max = getDepth(node.getLeft()); 
     } 
     else 
     { 
      max = getDepth(node.getRight()); 
     } 
     return 1 + max; 
    } 
} 

這裏

同一件事：遍歷到達葉子並得到了它的子從而使再次返回一個額外的水平多了一個電話，解決的辦法是測試如果當前節點childs而不是檢查當前節點是否退出。

Answer 1

getDepth方法有什麼問題，因爲它似乎返回4個級別而不是3個？

從你的打印方法看來，你編號的級別從0到n（樹的根0）。但是，您的getDepth方法將永遠不會返回0. 兩件事：if (node != null)此檢查似乎沒有多大意義。 Null似乎不是允許的輸入（因爲根構造在樹上）。如果是這種情況（你確實想檢查一下），一個例外可能更合適。 主要問題似乎是這樣的：return max + 1; 所以返回的最小值是0 + 1，即1。

作爲一個小小的註釋：我將保存getDepth的兩個遞歸調用的值，這將大大提高性能。 另外，如果確實使用短變量名稱，例如i，m或j（以非循環索引方式），那麼記錄它們的含義將會有所幫助。

並保留你的第一個問題： tree.setLeft(new Node()); 到目前爲止，這個節點的價值是多少？如果經常性呼叫中的代碼不能通過，會發生什麼？如果你能回答這些問題，你應該能夠自己修復代碼。