红黑树-按排序顺序返回所有大于X的值

Question

我的项目中确实需要这个功能。也就是说，我有一个红黑树，我需要写一个函数来按排序顺序返回所有高于X的值。

示例：

给定以下RBT

https://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/500px-Red-black_tree_example.svg.png

函数越大(6(应返回[6，8，11，13，15，17，22，25，27]

函数较大(11(应返回[13,15,17,22,25,27]

有什么建议吗？在我已经找到节点X的情况下，递归是什么？

Answer 1

对树进行有序遍历，当发现一个大于给定值的值时，将其推送到结果数组并返回。

更新以进行优化：

如果当前节点的值为<比目标边界值大。仅当左子树的值为>=时才检查该子树目标边界值。

以下是Javascript代码的工作示例。

/**
* Function to create a tree node with null left and right child
* @param {Number} val
* @return {Node} tree node
* */
function Node(val) {
this.value = val;
this.left = null;
this.right = null;
}
// Constructing the tree
const root = new Node(13);
root.left = new Node(8);
root.left.left = new Node(1);
root.left.left.right = new Node(6);
root.left.right = new Node(11);
root.right = new Node(17);
root.right.left = new Node(15);
root.right.right = new Node(25);
root.right.right.left = new Node(22);
root.right.right.right = new Node(27);
/**
* In-order traversal of a  binary tree.
* While processing the current node, we will check and push the value to result array
* @param {Node} node
* @param {Number} contraint value
* @param {Number[]} result array
* @return {Void}
* */
function inorder(node, val, result) {
if (node == null) return;
/** 
* We don't have to check the left subtree of the current node if the value 
* of the current node is < than target boundary value. Only check left
* subtree if its value is >= target boundary value.
* */
if(node.value >= val) {
inorder(node.left, val, result);
}

if (node.value > val) {
result.push(node.value);
}
inorder(node.right, val, result);
}
/**
* @param {Node} root
* @param {Number} value
* @return {Number[]} result
* */
function getValuesAfter(root, value) {
const result = new Array();
inorder(root, value, result);
return result;
}
console.log("Sorted values after 6:");
const result6 = getValuesAfter(root, 6);
console.log(result6.join(', '));
console.log("Sorted values after 11:");
const result11 = getValuesAfter(root, 11);
console.log(result11.join(', '));

console.log("Sorted values after 22:");
const result22 = getValuesAfter(root, 22);
console.log(result22.join(', '));