创建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()); 到目前为止，这个节点的价值是多少？如果经常性呼叫中的代码不能通过，会发生什么？如果你能回答这些问题，你应该能够自己修复代码。