搜索二进制搜索树（BST）的最佳算法

Question

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

int value;
String name;

所以它的节点是这样的。

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

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

现在我想根据“值”变量的升序显示树节点。无需更改原始树。哪种算法/方法对此最有效？

Answer 1

这应该行得通：

void addToTree(Node Tree, Node x){
    if (Tree.value < x.value){
        if (Tree.right == null){
            Tree.right = x
        } else {
            addToTree(Tree.right, x)
        }
    } else if (Tree.value > x.value) {
        if (Tree.left == null){
            Tree.left = x
        } else {
            addToTree(Tree.left, x)
        }
    } else {
        throw new Exception("Value already exists.")
    }
}

Node getFromTree(Node Tree, int x){
    if (Tree.value < x.value){
        if (Tree.right == null){
            throw new Exception("Value doesn't exist.")
        } else {
            return getFromTree(Tree.right, x)
        }
    } else if (Tree.value > x.value){
        if (Tree.left == null){
            throw new Exception("Value doesn't exist.")
        } else {
            return getFromTree(Tree.left, x)
        }
    } else {
        return Tree
    }
}

它按值（Node.value）对节点进行排序和查找。

Answer 2

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

您可以使用< code >递归版本

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