在理解二分搜索樹之前认然，我們先來看看二叉樹是什么。
1.1 二叉樹
二叉樹也是一種動態(tài)的數(shù)據(jù)結構酌伊。每個節(jié)點只有兩個叉腾窝，也就是兩個孩子節(jié)點，分別叫做左孩子居砖，右孩子虹脯，而沒有一個孩子的節(jié)點叫做葉子節(jié)點。每個節(jié)點最多有一個父親節(jié)點奏候，最多有兩個孩子節(jié)點(也可以沒有孩子節(jié)點或者只有一個孩子節(jié)點)循集。47左半邊的所有節(jié)點組合起來形成了47的左子樹，47右半邊所有節(jié)點結合起來形成了47的右子樹蔗草。如下圖所示：
綜合一下咒彤，涉及到的概念有：
根節(jié)點：二叉樹的起始節(jié)點，唯一沒有父親節(jié)點的節(jié)點咒精；
父親節(jié)點：每個節(jié)點只有一個父親節(jié)點蔼紧。如上圖47就是35的父親節(jié)點；
左右孩子節(jié)點：每個節(jié)點至多擁有兩個孩子節(jié)點狠轻，分別叫左孩子，右孩子彬犯；
左子樹右子樹：每個節(jié)點左邊或者右邊部分所有節(jié)點組合成的樹結構向楼。
1.2 二分搜索樹
1.2.1 性質
第一查吊，二分搜索樹是一顆二叉樹，滿足二叉樹的所有定義湖蜕；
第二逻卖，二分搜索樹每個節(jié)點的左子樹的值都小于該節(jié)點的值，每個節(jié)點右子樹的值都大于該節(jié)點的值昭抒。
第三评也，任意節(jié)點的每顆子樹都滿足二分搜索樹的定義。
1.2.2 意義
當我們看到二分搜索樹的定義時灭返，是否會去聯(lián)系這樣定義的意義何在呢盗迟？其實，二分搜索樹是在給數(shù)據(jù)做整理熙含，因為左右子樹的值和根節(jié)點存在大小關系罚缕，所以在查找元素時，我們于根節(jié)點進行對比后怎静，就能每次近乎一半的去除掉查找范圍邮弹，這就大大的加快了我們的查詢速度，插入元素時也是一樣蚓聘。
在圖1-2中腌乡，如果要查找元素55，那么和根節(jié)點47對比后夜牡，發(fā)現(xiàn)55比47大与纽，于是就往47右孩子60中去查詢，接著發(fā)現(xiàn)55比60小氯材，就往60左孩子中查詢渣锦，于是就找到了這個元素。想象一下氢哮，如果是一個鏈表袋毙，那么將一個一個查詢下去，速度可想而知冗尤。
其實在生活中听盖，這樣的例子也比比皆是，我們去超市買東西裂七，超市也把一二三樓賣的是啥寫的很清楚皆看，假如三樓賣的是生鮮果蔬，而我們要買今天的菜背零，那么我們就直接去三樓腰吟，一樓和二樓我們就可以不用去找了，大大加快了我們選購商品的速度。圖書館找書也是這樣的例子毛雇。所以二分搜索樹的意義也就在此嫉称，很多時候數(shù)據(jù)結構其實來源于生活，于生活中解決實際問題灵疮，這就是技術的力量和價值的體現(xiàn)织阅。
但是，為了達到這樣的高效性震捣，樹結構由此也需要每個節(jié)點之間具備可比較性荔棉。而鏈表數(shù)據(jù)結構就沒有這類要求，所以還是那句話蒿赢，有得必有失润樱。
到此我們就可以輕松定義出來二分搜索樹的基本代碼如下：
public class BST<E extends Comparable<E>> {
private class Node {
public E e;
public Node left, right;
public Node(E e) {
this.e = e;
left = right = null;
}
}
private int size;
private Node root;
}
1.3 添加元素
我們一起來看看在一個樹中插入元素的動畫演示過程，如下圖元素65插入樹結構所示诉植，元素在插入時祥国，不斷跟當前根節(jié)點進行對比，以來選擇插入到左子樹還是右子樹晾腔。
通過動畫舌稀，我們對樹結構插入操作有了一個大致了解。現(xiàn)在我們來一步一步實現(xiàn)添加過程灼擂，將復雜問題簡單化：
1.3.1 第一步
當前狀態(tài)：無節(jié)點壁查。
當然是從一棵空樹開始，這個時候來一個元素剔应，這時當然是賦值給root根節(jié)點睡腿。很自然，我們就想到如下代碼：
public void add(E e) {
if (root == null) {
root = new Node(e);
size++;
} else {
}
}
1.3.2 第二步
當前狀態(tài)：有節(jié)點峻贮，但節(jié)點左孩子或右孩子為空或左右孩子都為空席怪。
這一步，我們已經(jīng)有了根節(jié)點了纤控，那么將在else中寫邏輯挂捻。由下面動畫我們知道，這時需要判斷兩個條件：
第一船万，插入元素與當前節(jié)點大小的比較刻撒；
第二，程序當前所在節(jié)點下左右節(jié)點是否為空耿导，如果為空声怔，那么就把添加的節(jié)點插入在這個位置上。
接下來舱呻，我們將用遞歸的方式進行元素的添加醋火，我們先解決在某一節(jié)點上添加元素這個子問題。那么下面代碼塊中 add(root, e);這句代碼把根節(jié)點傳入，就是在根節(jié)點上添加元素胎撇，那么代碼如下：
public void add(E e) {
if (root == null) {
root = new Node(e);
size++;
} else {
add(root, e);
}
}
// 在node為根節(jié)點的樹中介粘，添加元素e
private void add(Node node, E e) {
if (node.e.compareTo(e) == 0) {
return;
}
// 添加到左孩子的位置，
// 條件：添加的元素小于node節(jié)點的元素晚树，node節(jié)點的元素的左孩子為空
if (e.compareTo(node.e) < 0 && node.left == null) {
node.left = new Node(e);
size++;
return;
}
// 添加到右孩子的位置
if (e.compareTo(node.e) > 0 && node.right == null) {
node.right = new Node(e);
size++;
return;
}
}
1.3.3 第三步
當前狀態(tài)：有節(jié)點，左右孩子都不為空雅采。
如果當前節(jié)點左右孩子都不為空爵憎，那么就遞歸的把當前節(jié)點的左孩子或右孩子傳遞進add方法。如下：
public void add(E e) {
if (root == null) {
root = new Node(e);
size++;
} else {
add(root, e);
}
}
private void add(Node node, E e) {
if (node.e.compareTo(e) == 0) {
return;
}
if (e.compareTo(node.e) < 0 && node.left == null) {
node.left = new Node(e);
size++;
return;
}
if (e.compareTo(node.e) > 0 && node.right == null) {
node.right = new Node(e);
size++;
return;
}
// 遞歸調用婚瓜，如果當前節(jié)點左右節(jié)點不為空宝鼓，則進入下一輪遞歸的調用。
if (e.compareTo(node.e) < 0) {
add(node.left, e);
} else {
add(node.right, e);
}
}
換一種思考方式
我們如果仔細觀察上面的邏輯就會發(fā)現(xiàn)巴刻，只要添加元素愚铡，那么這個位置肯定是空節(jié)點，用遞歸的話胡陪，我們的循環(huán)終止條件就可以用當前位置是否為空來判斷沥寥，代碼瞬間簡單了許多，如下：
public void add(E e) {
root = addAnother(root, e);
}
// 返回插入新節(jié)點后柠座，二分搜索樹的根
private Node addAnother(Node node, E e) {
if (node == null) {
size++;
return new Node(e);
}
if (e.compareTo(node.e) < 0) {
node.left = addAnother(node.left, e);
} else if (e.compareTo(node.e) > 0) {
node.right = addAnother(node.right, e);
}
return node;
}
1.4 樹的遍歷
樹的遍歷分為前序遍歷邑雅，中序遍歷，后序遍歷妈经，層序遍歷淮野。我們依次來講一講。
1.4.1 前序遍歷
前序遍歷吹泡，就是我們在遞歸調用前骤星，先做我們的邏輯（這里的邏輯就是打印一下當前元素），前序遍歷代碼如下：
private void preOrder(Node node) {
if (node == null) {
return;
}
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
我們以一個節(jié)點為例子爆哑，如節(jié)點后還有節(jié)點洞难，遞歸會循環(huán)處理。以下樹結構最終打印的結果就是47泪漂，35廊营，60。
1.4.2 中序遍歷與后續(xù)遍歷
那么接下來就是中序遍歷萝勤，中序遍歷就是把對元素的操作操作放在了中間露筒，先不斷遞歸左孩子，然后對元素進行操作敌卓，最后遞歸右孩子慎式。所以很容易的推理出來，中序遍歷是對元素從小到大的排序遍歷。這個性質可以作為判斷二分搜索樹的一個條件瘪吏。
同理可以推出還有后續(xù)遍歷癣防，這里就不再贅述了。
1.4.3 層序遍歷
最后我們一起來聊聊層序遍歷掌眠，顧名思義蕾盯，層序遍歷就是對樹結構一層一層的遍歷。要做到這一點蓝丙，我們可以很方便的想到利用隊列來實現(xiàn)這一過程级遭。我們每次從隊列中取出一個元素時，接著就把該元素的左右兩孩子推入隊列中渺尘，然后依次取出元素挫鸽，以此來做到按層把元素遍歷一遍。
一起來看看動畫爸爸給我們的演示鸥跟，最直觀丢郊。
由動畫爸爸很容易看出，依次打印的順序分別為：47医咨，35枫匾，60，32腋逆，45婿牍，55，65惩歉，完美完成層序遍歷等脂。
然后我來奉上代碼媽媽：
public void levelOrder() {
Queue<Node> q = new LinkedList<>();
// 把根節(jié)點放入隊列
q.add(root);
while (!q.isEmpty()) {
// 移除并返回隊列中的第一個節(jié)點
Node front = q.remove();
System.out.print(front.e + " ");
// 把移除元素的左右孩子推出隊列
if (front.left != null) {
q.add(front.left);
}
if (front.right != null) {
q.add(front.right);
}
}
}
1.5 刪除元素
1.5.1 后繼節(jié)點
接下來，我們聊聊元素的刪除撑蚌。在此之前上遥，我們先得引入一個概念，元素的前驅或者后繼節(jié)點争涌。
后繼節(jié)點：一個節(jié)點右子樹中粉楚，最小的節(jié)點為該節(jié)點的后繼節(jié)點。后繼節(jié)點是比該節(jié)點所有大的元素中最小的元素亮垫。
之所以要引入這個概念模软，原因是在刪除元素時，我們需要找一個元素替代被刪除位置的元素饮潦，但是由于二分搜索樹的特性燃异，不能隨便找元素過來代替，必須得找一個和被刪除元素最接近的元素來替代其位置继蜡。所以找前驅或后繼替代都可以回俐。
比如說逛腿，如下圖，47的后繼節(jié)點就是55仅颇，右子樹中最小的元素单默。
1.5.2 刪除元素的過程
我們分情況討論，待刪除元素可能有以下三種情形忘瓦。
第一種搁廓，只有左孩子；
第二種政冻，只有右孩子枚抵；
第三種，左右孩子都有明场；（當然還有一種情況就是為葉子節(jié)點，那么直接刪除即可）
同理很容易就能推出右子樹為空時的刪除過程李丰。
接下來我們來看看左右子樹不為空的情況苦锨。這種情況動畫演示比較簡單，我們看看整體的過程趴泌。
第一步，找到待刪除元素；
第二步碌嘀，找到待刪除元素的后繼節(jié)點便锨；
第三步，把待刪除元素的左子樹賦值給后繼節(jié)點的左子樹吉捶，把待刪除元素的右子樹最小元素刪除后夺鲜，賦值給后繼節(jié)點的右子樹。
整體代碼如下：
public void remove(E e) {
root = remove(root, e);
}
private Node remove(Node node, E e) {
if (node == null) {
return null;
}
if (e.compareTo(node.e) < 0) {
node.left = remove(node.left, e);
return node;
} else if (e.compareTo(node.e) > 0) {
node.right = remove(node.right, e);
return node;
} else { // 找到了待刪除元素
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
// 后繼節(jié)點
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
return successor;
}
}
