数据结构-二叉查找树（查找，插入，删除，遍历）
一、什么是二叉查找树
二叉查找树是一颗空树，或者是具有一下性质的二叉树：
1.若根结点的左子树不为空，那么左子树上所有结点的值都小于根节点的值
2.若根结点的右子树不为空，那么右子树上所有结点的值都小于根节点的值
3.根节点的左子树和右子树也是二叉查找树
下图就是一颗二叉查找树，每个结点的值都大于他的左子树的所有结点的值，每个结点的值都小于他的右子树所有结点的值。
图一
下图也是一个二叉查找树，虽然他是一个斜树，树的高度等于结点的数量，但是他也符合二叉查找树的定义（只是搜索的效率很低）。
图二
二、二叉查找树的作用
从名字就可以看出，我们构造二叉查找树的作用是高效地查找、插入和删除。
2.1 查找
比如，我们在图一所示的二叉查找树中查找数字5是否存在，查找的步骤如下：
1、5和结点④比较，5大于4，下一步我们要搜索结点④的右子树（根据二叉查找树的定义，一个结点值小于他的右子树上所有结点的值）
2、5和结点⑥比较，5小于6，下一步我们要搜索结点⑥的左子树
3、5等于结点5，查找成功
2.2 插入
我们依然用图一作为例子，这次我们要在图一所示的二叉树中插入一个7，步骤如下：
1、7和根结点④比较，7大于4，下一步搜索右子树
2、7和结点⑥比较，7大于6，下一步搜索右子树
3、7和结点⑧比较，7小于8，下一步搜索左子树
4、8的左子树为空，那么这里就是7应该插入的位置，将7插入到8的左子树中。
如下如所示
图三-插入结点
2.3删除结点
删除结点比较复杂，我们需要分为四种情况。
我们以下图为例来分析这四种情况
图四
2.3.1 待删除的结点既没有左子树有没有右子树
用图四作为例子，我们需要删除结点9，步骤如下
1、我们首先要找到结点9的父节点8（如果要删除的结点没有父节点，也就是要删除的结点就是根结点，那么直接将树设置为空树即可）。
2、我们将结点9从其父节点8的右子树上删除。
图五
2.3.2 待删除的结点只有左子树
用图四作为例子，我们要删除结点15，它只有左子树，删除的步骤如下
1、找到待删除的结点15
2、将结点15的左子结点的值12赋值给结点15
3、将结点结点12的左子树和右子树分别设置为待删除结点的左子树和右子树
如下图所示：
图六
2.3.3 待删除的结点只有右子树
用图四作为例子，我们要删除结点5，和2.3.2类似，步骤如下
1、找到待删除的结点5
2、将结点5的右子结点的值8赋值给结点5
3、将结点结点8的左子树和右子树分别设置为待删除结点的左子树和右子树
2.3.3 待删除的结点有左子树又有右子树
首先我们应该知道，二叉查找树中序遍历时结点的值递增的（大家可以自己想一下为什么）。
用图四作为例子，我们要删除结点10，为了保持二叉查找树的性质，我们需要找到中序遍历中10的左边一个结点或者右边一个结点来替代10的位置，这里我们选择中序遍历中10的左边一个结点。删除的步骤如下
1、首先找到待删除的结点
2、找到中序遍历中10的左边的那个结点9和该节点的父节点8
3、删除结点9
4、将结点10的值替换为9
如下图所示
图七
2.4 时间复杂度分析
当二位查找树是一颗完全二叉树时，树的高度是log(n) + 1，那么查找，插入，删除的时间复杂度都是log(n)。
但是如果二叉查找树不平衡，更机端的情况下变为一个斜树，如图二所示，那么时间复杂度就会退化为O(n)。
三、代码
这里我使用java来写二叉查找树的搜索，插入，删除。其他语言思路一样。
我创建了一个类BinarySearchTree，类中有一个静态内部类TreeNode用来表示二叉树的结点，类中有一个TreeNode类型成员变量head用来保存二叉查找树的根节点。
思路在第二章已经说明，这里就不多解释了。
大家多练练手，明白其中的原理即可。
package MyBinarySearchTree;
import java.util.Stack;
public class BinarySearchTree {
/**
* 在二叉搜索树中搜索是否存在指定的结点，如果存在指定结点，返回该结点，否则返回该结点在二叉树中所处位置的父节点
* @param head
* @param key
* @return
*/
public TreeNode head = null; //根节点
/**
* 设置根节点的值
* @param val
*/
public void setHeadValue(int val) {
if (head == null) {
head = new TreeNode();
head.value = val;
} else {
head.value = val;
}
}
/**
* 在二叉搜索树中搜索指定结点
* @param key
* @return
*/
public boolean search(int key) {
TreeNode res = search(head, null, key);
if (res != null && res.value == key) {
return true;
} else {
return false;
}
}
/**
* 输入根节点，父节点，和要查找的值，找到指定结点，如果该节点存在？返回该结点：否则返回该结点的父节点
* @param myHead
* @param father
* @param key
* @return
*/
private TreeNode search(TreeNode myHead, TreeNode father, int key) {
if (myHead == null) {
return father;
} else if (myHead.value == key) {
return myHead;
} else if (myHead.value > key) {
return search(myHead.left, myHead, key);
} else {
return search(myHead.right, myHead, key);
}
}
/**
* 插入结点，返回结点引用
* @param head
* @param key
* @return
*/
public TreeNode insert(int key) {
TreeNode res = null;
if (head == null) { //如果树为空，创建根节点，返回
head = new TreeNode();
head.value = key;
res = head;
} else {
res = search(head, null, key); //搜索该节点
if (res.value != key) { //如果二叉搜索树中不存在该结点，进行插入
TreeNode newNode = new TreeNode();
newNode.value = key;
if (newNode.value > res.value) {
res.right = newNode;
} else {
res.left = newNode;
}
res = newNode;
}
}
return res;
}
/**
* 删除指定结点，如果存在该结点，返回true,否则返回false
* @param key
* @return
*/
public boolean delete(int key) {
if (head == null) {
return false;
}
TreeNode parent = null;
TreeNode cur = head;
while (cur != null) { //找到要删除的结点和其父节点
if (cur.value == key) {
break;
} else if (cur.value > key){
parent = cur;
cur = cur.left;
} else {
parent = cur;
cur = cur.right;
}
}
if (cur == null) { //如果不存在该结点，不需要删除，返回
return false;
} else { //二叉搜索树中存在该结点
if (cur.left == null && cur.right == null) { //要删除的结点的左右子树都为空
if (parent == null) { //要删除的结点就是根节点，并且其没有子结点，将根节点设置为null
head = null;
} else { //从parent中删除该结点
if (parent.left == cur) {
parent.left = null;
} else {
parent.right = null;
}
}
} else if (cur.left == null) { //要删除的结点的左子树为空，要删除结点的右结点顶替
cur.value = cur.right.value;
cur.left = cur.right.left;
cur.right = cur.right.right;
} else if (cur.right == null) { //要删除的结点的右子树为空，要删除结点的左结点顶替
cur.value = cur.left.value;
cur.right = cur.left.right;
cur.left = cur.left.left;
} else { //要删除的结点的所有子树都不为空，找到中序遍历的前一个结点，替换并删除。
TreeNode temp = cur;
parent = cur;
cur = cur.left;
while (cur.right != null) {
parent = cur;
cur = cur.right;
}
temp.value = cur.value;
if (parent.left == cur) {
parent.left = cur.left;
} else {
parent.right = cur.left;
}
}
return true;
}
}
/**
* 中序遍历
*/
public void midSearch() {
TreeNode cur = head;
Stack<TreeNode> stack = new Stack<TreeNode>();
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
System.out.println(cur.value);
cur = cur.right;
}
}
/**
* 二叉树结点
* @author TinyMonster
*
*/
public static class TreeNode {
int value = 0;
TreeNode left = null;
TreeNode right = null;
}
/*
*
*/
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.setHeadValue(4);
tree.insert(2);
tree.insert(1);
tree.insert(3);
tree.insert(6);
tree.insert(5);
tree.insert(7);
tree.midSearch();
System.out.println("-----查找结点7-----");
System.out.println(tree.search(7));
System.out.println("-----删除结点7-----");
tree.delete(7);
tree.midSearch();
System.out.println("-----删除结点4-----");
tree.delete(4);
tree.midSearch();
}
}
