二叉搜索树的搜索分为单个元素的搜索和范围搜索。
class TreeNode {
int value;
TreeNode left;
TreeNode right;
}
单个元素的搜索：
递归版本：
TreeNode search(TreeNode root, final int key) {
if (root == null) {
return null;
}
if (key < root.value) {
return search(root.left, key);
} else if (key > root.value) {
return search(root.right, key);
} else {
return root;
}
}
递推版本：
TreeNode search(TreeNode root, final int key) {
while (root != null) {
if (key < root.value) {
root = root.left;
} else if (key > root.value) {
root = root.right;
} else {
return root;
}
}
return null;
}
范围搜索：请查找区间[p ,q ]之间的全部数据。
如果把搜索二叉树做中序遍历，那么得到的结果是所有节点都是顺序排列的。只要选择在区间之内的即可。
void search(TreeNode root, final int p, final int q) {
if (root == null) {
return;
}
search(root.left, p, q);
if (root.value >= p && root.value <= q) {
System.out.println(root.value);
}
search(root.right, p, q);
}
2020-02-24
按区间搜索的代码，虽然是顺序打印，但是没有利用二叉搜索树的特性，这跟普通二叉树的中序遍历没有什么区别。
void search(BinaryTreeNode root, final int p, final int q) {
if (root == null) {
return;
}
if (root.value >= p) {
search(root.left, p, q);
}
if (root.value >= p && root.value <= q) {
System.out.println(root.value);
}
if (root.value <= q) {
search(root.right, p, q);
}
}
