二叉查找树（Binary Search Tree），也称有序二叉树或排序二叉树，是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于 它的根节点的值
- 若任意节点的右子树不空，则右子树上所有节点的值均大于 它的根节点的值
- 任意节点的左右子树也分别为二叉查找树
-
没有键值相等的节点
如下图，这是个普通的二叉树：
普通二叉树
在此基础上，加上节点之间的大小关系，就是二叉查找树：
二叉查找树
Java实现二叉查找树的基本操作
定义
首先定义一个二叉树节点类，主要包含三个成员变量，两个指向左右节点的left，right；一个用于排序的键值data。
package cn.ihep.tree;
public class BinaryTreeNode {
public int data;
public BinaryTreeNode left;
public BinaryTreeNode right;
public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
遍历二叉查找树
根据二叉查找树的性质，我们容易知道对二叉查找树进行中序遍历可以得到一个递增序列。
// 遍历输出二叉排序中的内容（中序输出）
public void selectOutput(BinaryTreeNode root) {
if (root != null) {
this.selectOutput(root.left);
System.out.print(root.data + " ");
this.selectOutput(root.right);
}
}
插入
在一个二叉查找树中插入一个键值key，原理很容易理解，拿key和当前节点的键值对比，如果key小于当前节点的键值，就把key插到当前节点的左子树中，依次递归去寻找查找位置。
// 插入节点
public void addNode(BinaryTreeNode root, int data) {
if (root == null)
root = new BinaryTreeNode(data, null, null);
else {
if (root.data > data) {
// left tree
if (root.left == null) {
root.left = new BinaryTreeNode(data, null, null);
} else {
root = root.left;
addNode(root, data);
}
} else if (root.data < data) {
// right tree
if (root.right == null) {
root.right = new BinaryTreeNode(data, null, null);
} else {
root = root.right;
addNode(root, data);
}
} else {
System.out.println("原二叉查找树已有该值，无法插入。。。");
}
}
}
初始化一棵二叉查找树
初始化一棵二叉查找树，我们可以用在数组排列的时候，或者查找值的时候，先构建一个二叉查找树，那么这个序列就有序了，然后我们再去根据其它算法进行查找，效率可能会更高。（但我总觉得构建一个二叉查找树挺麻烦的呀）
// 初始化二叉查找树
public BinaryTreeNode initBinarySearchTree(int[] nums) {
this.root = new BinaryTreeNode(nums[0], null, null);
for (int i = 1; i < nums.length; i++) {
addNode(root, nums[i]);
}
return this.root;
}
删除
二叉查找树的删除是比较麻烦的，我们可以看下面这张图：
image.png
如果，我们要删除的节点没有子节点，直接将父节点指向该节点的link置为null即可；
当删除的节点只有1个子节点时，将该子节点替换为要删除的节点即可，如下图：（图中还显示更新节点数量了，我这里没有设置节点数量的字段，可忽略）
image.png
但是，当删除的节点有2个子节点时，问题就比较复杂了：
我们可以采取两种方法，第一，把待删除节点的左子树中的最大值替换掉删除节点；第二，把待删除节点的右子树中的最小值替换掉删除节点。（我这里将右子树中最小值作为替换点）
/**
*
* @param root
* @param key：删除该节点
* @return：返回删除后的二叉查找树的根节点
*/
public BinaryTreeNode deleteNode(BinaryTreeNode root, int key) {
BinaryTreeNode s;
if (root.data > key)
root.left = deleteNode(root.left, key);
else if (root.data < key)
root.right = deleteNode(root.right, key);
else {
// 找到要删除的值
if (root.left != null && root.right != null) {
s = root.right;
while (s.left != null) {
s = s.left;
}
root.data = s.data;
root.right = deleteNode(root.right, s.data);
} else {
root = (root.left != null) ? root.left : root.right;
}
}
return root;
}
总结：
二叉查找树的运行时间和树的形状有关，树的形状又和元素插入顺序有关。在最好的情况下，节点完全平衡，从根节点到最底层叶子节点只有lgN个节点。在最差的情况下，根节点到最底层叶子节点会有N个节点。
最后，附上整个测试源码：（BinarySearchTree的定义见本文第一段代码）
package cn.ihep.tree;
/**
* 二叉查找树的实现 -- 查找、插入、删除
*
* @author xiaoming
*
*/
public class BinarySearchTree {
public BinaryTreeNode root;
// 初始化二叉查找树
public BinaryTreeNode initBinarySearchTree(int[] nums) {
this.root = new BinaryTreeNode(nums[0], null, null);
for (int i = 1; i < nums.length; i++) {
addNode(root, nums[i]);
}
return this.root;
}
// 插入节点
public void addNode(BinaryTreeNode root, int data) {
if (root == null)
root = new BinaryTreeNode(data, null, null);
else {
if (root.data > data) {
// left tree
if (root.left == null) {
root.left = new BinaryTreeNode(data, null, null);
} else {
root = root.left;
addNode(root, data);
}
} else if (root.data < data) {
// right tree
if (root.right == null) {
root.right = new BinaryTreeNode(data, null, null);
} else {
root = root.right;
addNode(root, data);
}
} else {
System.out.println("原二叉查找树已有该值，无法插入。。。");
}
}
}
// 遍历输出二叉排序中的内容（中序输出）
public void selectOutput(BinaryTreeNode root) {
if (root != null) {
this.selectOutput(root.left);
System.out.print(root.data + " ");
this.selectOutput(root.right);
}
}
/**
*
* @param root
* @param key：删除该节点
* @return：返回删除后的二叉查找树的根节点
*/
public BinaryTreeNode deleteNode(BinaryTreeNode root, int key) {
BinaryTreeNode s;
if (root.data > key)
root.left = deleteNode(root.left, key);
else if (root.data < key)
root.right = deleteNode(root.right, key);
else {
// 找到要删除的值
if (root.left != null && root.right != null) {
s = root.right;
while (s.left != null) {
s = s.left;
}
root.data = s.data;
root.right = deleteNode(root.right, s.data);
} else {
root = (root.left != null) ? root.left : root.right;
}
}
return root;
}
public static void main(String[] args) {
int[] nums = { 89, 1, 0, -3, 56, 234, 123, 55, 33, 11, 324 };
BinarySearchTree bst = new BinarySearchTree();
bst.initBinarySearchTree(nums);
bst.selectOutput(bst.root);
// 删除value
System.out.println();
bst.deleteNode(bst.root, 324);
bst.selectOutput(bst.root);
}
}
