一、什么是二叉查找樹
二叉查找樹是一顆空樹握联，或者是具有一下性質(zhì)的二叉樹：
1.若根結(jié)點的左子樹不為空桦沉，那么左子樹上所有結(jié)點的值都小于根節(jié)點的值
2.若根結(jié)點的右子樹不為空每瞒，那么右子樹上所有結(jié)點的值都小于根節(jié)點的值
3.根節(jié)點的左子樹和右子樹也是二叉查找樹
下圖就是一顆二叉查找樹，每個結(jié)點的值都大于他的左子樹的所有結(jié)點的值永部，每個結(jié)點的值都小于他的右子樹所有結(jié)點的值独泞。
下圖也是一個二叉查找樹，雖然他是一個斜樹苔埋，樹的高度等于結(jié)點的數(shù)量，但是他也符合二叉查找樹的定義（只是搜索的效率很低）蜒犯。
二组橄、二叉查找樹的作用
從名字就可以看出，我們構(gòu)造二叉查找樹的作用是高效地查找罚随、插入和刪除玉工。
2.1 查找
比如，我們在圖一所示的二叉查找樹中查找數(shù)字5是否存在淘菩，查找的步驟如下：
1遵班、5和結(jié)點④比較，5大于4潮改，下一步我們要搜索結(jié)點④的右子樹（根據(jù)二叉查找樹的定義狭郑，一個結(jié)點值小于他的右子樹上所有結(jié)點的值）
2、5和結(jié)點⑥比較汇在，5小于6翰萨，下一步我們要搜索結(jié)點⑥的左子樹
3、5等于結(jié)點5糕殉，查找成功
2.2 插入
我們依然用圖一作為例子亩鬼，這次我們要在圖一所示的二叉樹中插入一個7，步驟如下：
1阿蝶、7和根結(jié)點④比較雳锋，7大于4，下一步搜索右子樹
2羡洁、7和結(jié)點⑥比較玷过，7大于6，下一步搜索右子樹
3焚廊、7和結(jié)點⑧比較冶匹，7小于8，下一步搜索左子樹
4咆瘟、8的左子樹為空嚼隘，那么這里就是7應(yīng)該插入的位置，將7插入到8的左子樹中袒餐。
如下如所示
2.3刪除結(jié)點
刪除結(jié)點比較復(fù)雜飞蛹，我們需要分為四種情況谤狡。
我們以下圖為例來分析這四種情況
2.3.1 待刪除的結(jié)點既沒有左子樹有沒有右子樹
用圖四作為例子，我們需要刪除結(jié)點9卧檐，步驟如下
1墓懂、我們首先要找到結(jié)點9的父節(jié)點8（如果要刪除的結(jié)點沒有父節(jié)點，也就是要刪除的結(jié)點就是根結(jié)點霉囚，那么直接將樹設(shè)置為空樹即可）捕仔。
2、我們將結(jié)點9從其父節(jié)點8的右子樹上刪除盈罐。
2.3.2 待刪除的結(jié)點只有左子樹
用圖四作為例子榜跌，我們要刪除結(jié)點15，它只有左子樹盅粪，刪除的步驟如下
1钓葫、找到待刪除的結(jié)點15
2、將結(jié)點15的左子結(jié)點的值12賦值給結(jié)點15
3票顾、將結(jié)點結(jié)點12的左子樹和右子樹分別設(shè)置為待刪除結(jié)點的左子樹和右子樹
如下圖所示：
2.3.3 待刪除的結(jié)點只有右子樹
用圖四作為例子础浮，我們要刪除結(jié)點5，和2.3.2類似奠骄，步驟如下
1豆同、找到待刪除的結(jié)點5
2、將結(jié)點5的右子結(jié)點的值8賦值給結(jié)點5
3戚揭、將結(jié)點結(jié)點8的左子樹和右子樹分別設(shè)置為待刪除結(jié)點的左子樹和右子樹
2.3.3 待刪除的結(jié)點有左子樹又有右子樹
首先我們應(yīng)該知道诱告，二叉查找樹中序遍歷時結(jié)點的值遞增的（大家可以自己想一下為什么）。
用圖四作為例子民晒，我們要刪除結(jié)點10精居，為了保持二叉查找樹的性質(zhì)，我們需要找到中序遍歷中10的左邊一個結(jié)點或者右邊一個結(jié)點來替代10的位置潜必，這里我們選擇中序遍歷中10的左邊一個結(jié)點靴姿。刪除的步驟如下
1、首先找到待刪除的結(jié)點
2磁滚、找到中序遍歷中10的左邊的那個結(jié)點9和該節(jié)點的父節(jié)點8
3佛吓、刪除結(jié)點9
4、將結(jié)點10的值替換為9
如下圖所示
2.4 時間復(fù)雜度分析
當(dāng)二位查找樹是一顆完全二叉樹時垂攘，樹的高度是log(n) + 1维雇，那么查找，插入晒他，刪除的時間復(fù)雜度都是log(n)吱型。
但是如果二叉查找樹不平衡，更機端的情況下變?yōu)橐粋€斜樹陨仅，如圖二所示津滞，那么時間復(fù)雜度就會退化為O(n)铝侵。
三、代碼
這里我使用java來寫二叉查找樹的搜索触徐，插入咪鲜，刪除。其他語言思路一樣撞鹉。
我創(chuàng)建了一個類BinarySearchTree疟丙，類中有一個靜態(tài)內(nèi)部類TreeNode用來表示二叉樹的結(jié)點，類中有一個TreeNode類型成員變量head用來保存二叉查找樹的根節(jié)點鸟雏。
思路在第二章已經(jīng)說明隆敢，這里就不多解釋了。
大家多練練手崔慧，明白其中的原理即可。
package MyBinarySearchTree;
import java.util.Stack;
public class BinarySearchTree {
/**
* 在二叉搜索樹中搜索是否存在指定的結(jié)點穴墅，如果存在指定結(jié)點惶室，返回該結(jié)點，否則返回該結(jié)點在二叉樹中所處位置的父節(jié)點
* @param head
* @param key
* @return
*/
public TreeNode head = null; //根節(jié)點
/**
* 設(shè)置根節(jié)點的值
* @param val
*/
public void setHeadValue(int val) {
if (head == null) {
head = new TreeNode();
head.value = val;
} else {
head.value = val;
}
}
/**
* 在二叉搜索樹中搜索指定結(jié)點
* @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;
}
}
/**
* 輸入根節(jié)點玄货，父節(jié)點皇钞，和要查找的值，找到指定結(jié)點松捉，如果該節(jié)點存在夹界？返回該結(jié)點：否則返回該結(jié)點的父節(jié)點
* @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);
}
}
/**
* 插入結(jié)點，返回結(jié)點引用
* @param head
* @param key
* @return
*/
public TreeNode insert(int key) {
TreeNode res = null;
if (head == null) { //如果樹為空隘世，創(chuàng)建根節(jié)點可柿，返回
head = new TreeNode();
head.value = key;
res = head;
} else {
res = search(head, null, key); //搜索該節(jié)點
if (res.value != key) { //如果二叉搜索樹中不存在該結(jié)點，進行插入
TreeNode newNode = new TreeNode();
newNode.value = key;
if (newNode.value > res.value) {
res.right = newNode;
} else {
res.left = newNode;
}
res = newNode;
}
}
return res;
}
/**
* 刪除指定結(jié)點丙者，如果存在該結(jié)點复斥，返回true,否則返回false
* @param key
* @return
*/
public boolean delete(int key) {
if (head == null) {
return false;
}
TreeNode parent = null;
TreeNode cur = head;
while (cur != null) { //找到要刪除的結(jié)點和其父節(jié)點
if (cur.value == key) {
break;
} else if (cur.value > key){
parent = cur;
cur = cur.left;
} else {
parent = cur;
cur = cur.right;
}
}
if (cur == null) { //如果不存在該結(jié)點，不需要刪除械媒，返回
return false;
} else { //二叉搜索樹中存在該結(jié)點
if (cur.left == null && cur.right == null) { //要刪除的結(jié)點的左右子樹都為空
if (parent == null) { //要刪除的結(jié)點就是根節(jié)點目锭，并且其沒有子結(jié)點，將根節(jié)點設(shè)置為null
head = null;
} else { //從parent中刪除該結(jié)點
if (parent.left == cur) {
parent.left = null;
} else {
parent.right = null;
}
}
} else if (cur.left == null) { //要刪除的結(jié)點的左子樹為空纷捞，要刪除結(jié)點的右結(jié)點頂替
cur.value = cur.right.value;
cur.left = cur.right.left;
cur.right = cur.right.right;
} else if (cur.right == null) { //要刪除的結(jié)點的右子樹為空痢虹，要刪除結(jié)點的左結(jié)點頂替
cur.value = cur.left.value;
cur.right = cur.left.right;
cur.left = cur.left.left;
} else { //要刪除的結(jié)點的所有子樹都不為空，找到中序遍歷的前一個結(jié)點主儡，替換并刪除奖唯。
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;
}
}
/**
* 二叉樹結(jié)點
* @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("-----查找結(jié)點7-----");
System.out.println(tree.search(7));
System.out.println("-----刪除結(jié)點7-----");
tree.delete(7);
tree.midSearch();
System.out.println("-----刪除結(jié)點4-----");
tree.delete(4);
tree.midSearch();
}
}
