创建 Java 二叉搜索树

Creating Java binary search tree

提问by oneNewbieCoder

So here is the Node class:

所以这里是 Node 类：

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

How I create the tree:

我如何创建树：

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

This method computes the depth:

此方法计算深度：

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

And these two combined should print the tree by its levels:

这两个组合应该按其级别打印树：

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

In a test class I have:

在测试课中，我有：

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

And I get this output:

我得到这个输出：

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

I should get

我应该得到

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

1. What's wrong with the getDepthmethod because it seems that it returns 4 levels instead of 3?
2. Why are there additional nodes? (those zeroes)

1. 该getDepth方法有什么问题，因为它似乎返回 4 个级别而不是 3 个级别？
2. 为什么会有额外的节点？（那些零）

I'm pretty sure I solved the problems but I will need an explanation for the following:

我很确定我解决了这些问题，但我需要对以下内容进行解释：

This is the modified printlevelmethod:

这是修改后的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);  
    }
}

As you can see I test now if the current node has childs instead of checking if the current node exists and this is why those zeroes appeard because the traversal reached the leafs that had no info assigned on their right and left childs.

正如你所看到的，我现在测试当前节点是否有子节点而不是检查当前节点是否存在，这就是为什么出现这些零的原因，因为遍历到达了没有在其左右子节点上分配信息的叶子。

The thing I want to understand is the difference between incrementing currentLeveland then passing it to the call of printLeveland simply passing currentLevel+1to the call. Shouldn't it be the same thing ?

我想了解的是递增currentLevel然后将其传递给调用printLevel和简单地传递currentLevel+1给调用之间的区别。不应该是一样的吗？

And the getDepthfunction:

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

Same thing here: traversal reached the leafs and got one more call for its childs thus returning one additional level so again, the solution is to test if the current node has childs instead of checking if the current node exits.

同样的事情：遍历到达叶子节点并再次调用其子节点，从而返回一个额外的级别，因此再次，解决方案是测试当前节点是否有子节点，而不是检查当前节点是否存在。

回答by tim

What's wrong with the getDepth method because it seems that it returns 4 levels instead of 3?

getDepth 方法有什么问题，因为它似乎返回 4 个级别而不是 3 个级别？

From your print method it seems, that you number the levels from 0 to n (the root of a tree beeing 0). Your getDepth method however will never return 0. Two things: if (node != null)this check does not seem to make very much sense. Null does not seem to be an allowed input (as the root is constructed on construction of a Tree). If this is the case (and you do want to check it) an exception might be more appropriate. The main problem seems to be this: return max + 1; So the minimal value returned is 0 + 1, which is 1.

从您的打印方法看来，您将级别编号为 0 到 n（树的根为 0）。但是，您的 getDepth 方法永远不会返回 0。两件事：if (node != null)此检查似乎没有多大意义。Null 似乎不是允许的输入（因为根是在构建树时构建的）。如果是这种情况（并且您确实想检查它），则例外可能更合适。主要的问题似乎是这样的：return max + 1; 所以返回的最小值是0+1，也就是1。

As a small sidenote: I would save the values of the two recursive calls of getDepth, it would greatly increase performance. Also, if you do use short variable names such as i, m or j (in a non-loop index kind of way) it would be helpful to document their meaning.

作为一个小旁注：我会保存 getDepth 的两个递归调用的值，这将大大提高性能。此外，如果您确实使用了短变量名，例如 i、m 或 j（以非循环索引的方式），记录它们的含义会很有帮助。

And conserning your first question: tree.setLeft(new Node());What would be the value of this Node as of now? And what will happen if the i < j codition in the recurive call will not pass? If you can answer those questions, you should be able to fix the code yourself.

考虑到您的第一个问题： tree.setLeft(new Node());截至目前，该节点的价值是多少？如果i < j 递归调用中的条件不通过会发生什么？如果你能回答这些问题，你应该能够自己修复代码。