java - 二叉树搜索小于的值

Question

我正在为大学工作创建一个二叉树算法，我需要开发一个算法来有效地找到所有小于指定值的值(它们需要按顺序排列)。

                     10
                    /  \
                   9    11
                  /       \
                 5         15
                / \        / \
               1   8      13  19
                         /  \
                        12  14   

这是我想出的解决方案(上图是为了防止您忘记二叉树的样子)。

private BinaryTreeNode root;
public int[] getBeforeJoinedNum(int num){
        usersInOrder = new ArrayList<User>();
        beforeNum(num, root);
        return usersInOrder;
}

private void beforeNum(int num, BinaryTreeNode n){
        if (n != null){
            beforeNum(num, n.getLeft());
            int nodeValue = n.getValue();
            if (num<nodeValue){
                usersInOrder.add(n.getValue());
                beforeNum(num, n.getRight());
            }
        }
    }

此算法的问题在于它进行了不必要的比较。例如，如果我想要所有小于 10 的数字，如果它小于 10，代码将检查 9 剩下的所有内容(即 1、5、8)，而显然小于 9 的任何内容当然应该是在列表中，无需任何比较。

我怎样才能让这个算法更有效率？不幸的是，我不能使用 Java 集合框架，因为数据结构是类(class)作业的重点。

Answer 1

对于您知道满足该属性的子树，只需进行标准的中序遍历即可:

private void addAll(UserNode n) {
    if (n == null) return;
    addAll(n.getLeft());
    usersInOrder.add(n.getValue());
    addAll(n.getRight());
}

private void beforeNum(int num, UserNode n){
    if (n == null) return;
    if (n.getValue() < num) {
        addAll(n.getLeft());
        usersInOrder.add(n.getValue());
        beforeNum(num, n.getRight());
    } else {
        beforeNum(num, n.getLeft());
    }
}

请注意，我还在 beforeNum 中修复了一个逻辑错误: 你搞混了<与 >并且您没有在正确的情况下遍历正确的子树。