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

Question

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

int value;
String name;

所以它的节点是这样的。

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

我根据节点"名称"变量的升序在 BST 中插入了值。因此，树的顺序遍历将按"名称"的升序返回节点。

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

Answer 1

将 TreeSet 与比较器一起使用，该比较器根据名称升序排序并从左到右遍历节点，如下所示：

您可以使用recursion version

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

或Queue version

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

Answer 2

这应该有效：

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(对节点进行排序和查找。