java - 搜索二叉搜索树 (BST) 的最佳算法

Question

我有一个二叉搜索树，它的每个节点都有两个值。

int value;
String name;

所以它的节点是这样的。

class Node {
        int value;
        String name;
        Node left, right;
}

我已经根据节点的“name”变量的升序在 BST 中插入了值。因此，树的中序遍历将按“name”的升序返回节点。

现在我想根据“value”变量的升序显示树节点。不改变原来的树。什么算法/方法对此最有效？

Answer 1

使用带有比较器的 TreeSet，该比较器根据名称升序排序并从左到右遍历节点，如下所示:

您可以使用递归版本

    public static Iterable<Node> order(Node root) {
        Comparator<Node> cmp = (node1, node2) -> node1.name.compareTo(node2.name);
        TreeSet<Node> set = new TreeSet<>(cmp);
        visit(set, root);
        return set;
    }

    public static void visit(TreeSet<Node> set, Node node) {
        if (node == null)
            return;
        set.add(node);
        visit(set, node.left);
        visit(set, node.right);
    }

，或队列版本

    public static Iterable<Node> order(Node root) {
        Comparator<Node> cmp = (node1, node2) -> node1.name.compareTo(node2.name);
        Queue<Node> queue = new ArrayDeque<>();
        TreeSet<Node> set = new TreeSet<>(cmp);
        queue.add(root);
        set.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.left != null) {
                queue.add(node.left);
                set.add(node.left);
            }

            if (node.right != null) {
                queue.add(node.right);
                set.add(root);
            }
        }
        return set;
    }