二叉树 搜索小于的值

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 的数字，代码将检查 9 剩下的所有内容（即 1,5,8），如果它小于 10，而很明显任何小于 9 的东西当然都应该在列表中，不需要任何比较。

如何使此算法更有效率？不幸的是，我不能使用 Java 集合框架，因为数据结构是课程的重点。

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中的一个逻辑错误：您将<与>混淆，并且在正确的情况下没有遍历正确的子树。

Answer 2

听说过无序搜索吗？ 下面是一个示例代码。修改它，使其接受一个参数，该参数"用户节点"，并在它仍然小于"用户节点"时停止遍历

public void inOrderTraverse(Node root){
        if(root != null){
            inOrderTraverse(root.getLeft());
            System.out.print("  "+root.getData());
            inOrderTraverse(root.getRight());
        }
    }

这是一个快速修改的版本：

public void inOrderTraverse(Node root,UserNode n){
        if(root != null&&root.compareTo(n)<0){
            inOrderTraverse(root.getLeft());
            System.out.print("  "+root.getData());
            inOrderTraverse(root.getRight());
        }
    }

无论如何，您都需要遍历左侧的所有节点。