java - 创建Java二叉搜索树

Question

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

如何创建树:

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

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

Answer 1

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

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

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

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