上節(jié)課進(jìn)一步研究了鏈表及其具有的一種固有屬性--遞歸返弹，并遞歸實(shí)現(xiàn)了鏈表元素的刪除操作。本節(jié)課學(xué)習(xí)另外一種高效的數(shù)據(jù)結(jié)構(gòu)--樹爪飘。
1. 二分搜索樹
樹是一種天然的組織結(jié)構(gòu)义起，在實(shí)際生活中非常常見，比如：
- 文件夾的存儲(chǔ)結(jié)構(gòu)
- 公司的人員組織架構(gòu)
很多數(shù)據(jù)使用樹結(jié)構(gòu)存儲(chǔ)以后师崎，出奇的高效默终。樹結(jié)構(gòu)主要包括以下幾種：
- 二分搜索樹
- 平衡二叉樹
- 紅黑樹
- 線段樹等等
本節(jié)課學(xué)習(xí)二分搜索樹，提到二分搜索樹就不得不提二叉樹犁罩。二叉樹與鏈表一樣齐蔽，是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，它也是由節(jié)點(diǎn)組成床估，但二叉樹節(jié)點(diǎn)包含了兩個(gè)地址變量含滴，分別指向節(jié)點(diǎn)的左子樹和右子樹：
// 二叉樹的節(jié)點(diǎn)
class Node{
E e;
Node left;
Node right;
}
二叉樹具有很強(qiáng)的辨識(shí)性，特點(diǎn)明顯：
- 有且只有一個(gè)根節(jié)點(diǎn)
- 每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子
- 每個(gè)節(jié)點(diǎn)最多有一個(gè)父親
另外丐巫，同鏈表一樣谈况，二叉樹具有天然的遞歸屬性：
- 每個(gè)節(jié)點(diǎn)的左子樹也是二叉樹
-
每個(gè)節(jié)點(diǎn)的右子樹也是二叉樹
Recursion
需要注意的是，二叉樹不一定是滿的
二分搜索樹是二叉樹的一種递胧，在二分搜索樹中：
- 每個(gè)節(jié)點(diǎn)的值大于其左子樹的所有節(jié)點(diǎn)值
- 每個(gè)節(jié)點(diǎn)的值小于其右子樹的所有節(jié)點(diǎn)值
- 每個(gè)子樹也是一個(gè)二分搜索樹
注意鸦做，二分搜索樹存儲(chǔ)的元素必須具有可比較性∥阶牛基于這些內(nèi)容泼诱，我們可以給出二分搜索樹的一個(gè)基本結(jié)構(gòu)：
public class BST<E extends Comparable<E>> {
private class Node{
public E e;
public Node left;
public Node right;
public Node(E e) {
this.e = e;
left = null;
right = null;
}
}
private Node root; // 樹的根節(jié)點(diǎn)
private int size; // 樹中所有節(jié)點(diǎn)的數(shù)量
public BST() {
root = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public int getSize() {
return size;
}
}
注意，泛型聲明時(shí)必須具有可比較性赊锚。
2. 增加治筒、查找和遍歷
2.1 添加元素
向二分搜索樹中添加元素，需要保持二分搜索樹的順序性舷蒲，可以采用遞歸寫法和非遞歸寫法耸袜。遞歸寫法相對(duì)較簡(jiǎn)單，只要處理好邊界點(diǎn)和添加邏輯即可：
- 當(dāng)根節(jié)點(diǎn)為空時(shí)牲平，直接創(chuàng)建新節(jié)點(diǎn)堤框，添加到根節(jié)點(diǎn)中
- 當(dāng)添加元素大于根結(jié)點(diǎn)元素時(shí)，向以根結(jié)點(diǎn)的右子樹為根節(jié)點(diǎn)的二分搜索樹中添加
- 當(dāng)添加元素小于根節(jié)點(diǎn)元素時(shí)，向以根結(jié)點(diǎn)的左子樹為根節(jié)點(diǎn)的二分搜索樹中添加
// 公有方法添加元素
public void addElement(E e) {
// 調(diào)用私有添加方法向根結(jié)點(diǎn)所在樹添加元素
root = addElement(root, e);
}
// 私有方法蜈抓，向以node結(jié)點(diǎn)為根的二分搜索樹中添加元素
// 返回添加元素后的根節(jié)點(diǎn)
private Node addElement(Node node,E e) {
if(node==null) {
node = new Node(e);
size++;
return node;
}
if(e.compareTo(node.e)<0) {
// 遞歸實(shí)現(xiàn)启绰，添加元素小于node，向node的左子樹中添加元素
node.left = addElement(node.left,e);
}
if(e.compareTo(node.e)>0) {
// 遞歸實(shí)現(xiàn)沟使，添加元素大于node委可，向node的右子樹中添加元素
node.right = addElement(node.right,e);
}
return node;
}
添加元素的非遞歸寫法，與之前鏈表的寫法相似腊嗡，從實(shí)用性角度來(lái)看着倾，非遞歸寫法并不常用，這里不做研究燕少。
2.2 查找元素
二分搜索樹中不存在索引的概念卡者，因此查找操作是指查詢二分搜索樹中是否包含某個(gè)元素。遞歸實(shí)現(xiàn)起來(lái)客们，也是非常簡(jiǎn)單的：
- 如果節(jié)點(diǎn)元素等于要查找的元素虎眨，則直接返回true
- 如果節(jié)點(diǎn)元素為空，返回false
- 如果節(jié)點(diǎn)元素大于要查找的元素镶摘，到節(jié)點(diǎn)的左子樹中繼續(xù)查找
- 如果節(jié)點(diǎn)元素小于要查找的元素，到節(jié)點(diǎn)的右子樹中繼續(xù)查找
// 查看二分搜索樹中是否包含元素e
public boolean contains(E e){
// 調(diào)用私有方法
return contains(root,e);
}
// 查看以node 為根的二分搜索樹中是否包含元素e
private boolean contains(Node node,E e) {
if(node==null) {
return false;
}
if(e.equals(node.e))
return true;
if(e.compareTo(node.e)<0) {
return contains(node.left,e);
}
else
return contains(node.right,e);
}
2.3 深度優(yōu)先遍歷
在二分搜索樹中岳守，一個(gè)非常重要的操作就是遍歷凄敢。遍歷就是把所有節(jié)點(diǎn)都訪問(wèn)一遍。在二分搜索樹中湿痢，有三種遍歷方法涝缝，以訪問(wèn)根結(jié)點(diǎn)是在訪問(wèn)左子樹和右子樹的之前、之后和之間來(lái)進(jìn)行劃分：
-
前序遍歷：根節(jié)點(diǎn)在訪問(wèn)節(jié)點(diǎn)的左子樹和右子樹之前訪問(wèn)：
function traverse(node): if(node==null) return; 訪問(wèn)該節(jié)點(diǎn) traverse(node.left) traverse(node.right)前序遍歷是最自然譬重，也是最常用的一種遍歷方式：
// 前序遍歷二分搜索樹 public void preOrder() { preOrder(root); } // 前序遍歷以node為根的二分搜索樹 private void preOrder(Node node) { if(node==null) { return; } System.out.println(node.e); preOrder(node.left); preOrder(node.right); } -
中序遍歷：根節(jié)點(diǎn)在訪問(wèn)節(jié)點(diǎn)的左子樹和右子樹之間進(jìn)行訪問(wèn)：
function traverse(node): if(node==null) return; traverse(node.left) 訪問(wèn)該節(jié)點(diǎn) traverse(node.right)結(jié)合二分搜索樹的結(jié)構(gòu)特性拒逮，可以發(fā)現(xiàn)，中序遍歷可以將樹中的元素從小到大排列一遍臀规，因此二分搜索樹也是一種有序的數(shù)據(jù)結(jié)構(gòu)滩援。
// 中序遍歷 public void inOrder() { inOrder(root); } private void inOrder(Node node) { if(node==null) { return; } inOrder(node.left); System.out.println(node.e); inOrder(node.right); } -
后序遍歷：根節(jié)點(diǎn)在訪問(wèn)節(jié)點(diǎn)的左子樹和右子樹之后進(jìn)行訪問(wèn)
function traverse(node): if(node==null) return; traverse(node.left) traverse(node.right) 訪問(wèn)該節(jié)點(diǎn)代碼實(shí)現(xiàn)：
// 后序遍歷 public void postOrder() { postOrder(root); } private void postOrder(Node node) { if(node==null) { return; } postOrder(node.left); postOrder(node.right); System.out.println(node.e); }
下面，利用之前介紹的關(guān)于棧的知識(shí)塔嬉，研究二分搜索樹前序遍歷的非遞歸實(shí)現(xiàn)玩徊。前序遍歷的過(guò)程，可以用一個(gè)壓棧和彈棧的流程表示出來(lái)：
- 對(duì)已在棧內(nèi)的根結(jié)點(diǎn)谨究，訪問(wèn)到該節(jié)點(diǎn)時(shí)恩袱，將該節(jié)點(diǎn)彈棧，然后立刻將其右節(jié)點(diǎn)和左節(jié)點(diǎn)依次壓入棧內(nèi)
- 當(dāng)某個(gè)子樹為空時(shí)胶哲，不進(jìn)行壓棧操作
- 當(dāng)棧內(nèi)元素為空時(shí)畔塔，遍歷結(jié)束
// 前序遍歷，非遞歸寫法
public void preOderNR() {
if(root==null) {
return;
}
Stack<Node> stack = new Stack();
stack.push(root);
while(!stack.isEmpty()) {
Node node = stack.pop();
System.out.println(node.e);
if(node.right!=null) {
stack.push(node.right);
}
if(node.left!=null) {
stack.push(node.left);
}
}
}
2.4 層序遍歷
前面介紹的幾種遍歷方法均屬于深度優(yōu)先遍歷，本節(jié)介紹一種層序遍歷方法澈吨，即逐層訪問(wèn)樹的元素把敢，這種遍歷方式也叫做廣度優(yōu)先遍歷。這里借助隊(duì)列先進(jìn)先出的結(jié)構(gòu)特性來(lái)實(shí)現(xiàn)二分搜索樹的層序遍歷棚辽。
- 每次訪問(wèn)到一個(gè)節(jié)點(diǎn)時(shí)（出隊(duì)）技竟，將該節(jié)點(diǎn)的左孩子和右孩子依次入隊(duì)
- 當(dāng)某個(gè)孩子為空時(shí)，不進(jìn)行入隊(duì)操作
- 當(dāng)隊(duì)列內(nèi)元素為空時(shí)屈藐，遍歷結(jié)束
// 層序遍歷榔组，廣度優(yōu)先遍歷
public void levelOrder() {
if(root==null) {
return;
}
Queue<Node> queue = new LinkedList<>();
// 根節(jié)點(diǎn)入隊(duì)
queue.add(root);
// 隊(duì)列不為空時(shí)
while(!queue.isEmpty()) {
// 隊(duì)首元素出隊(duì)，記為cur節(jié)點(diǎn)
Node cur = queue.remove();
System.out.println(cur.e);
// cur節(jié)點(diǎn)的左孩子不為空時(shí)联逻，入隊(duì)
if(cur.left!=null) {
queue.add(cur.left);
}
// cur節(jié)點(diǎn)的右孩子不為空時(shí)搓扯，入隊(duì)
if(cur.right!=null) {
queue.add(cur.right);
}
}
}
樹的層序優(yōu)先遍歷通常能夠更快地找到問(wèn)題的解，常用于在路徑規(guī)劃中尋找最短路徑包归。
3. 二分搜索樹刪除節(jié)點(diǎn)
3.1 刪除最大值和最小值
本節(jié)討論如何從二分搜索樹中刪除元素锨推，先從最簡(jiǎn)單的情況開始：刪除二分搜索樹的最大值和最小值」溃基于二分搜索樹的結(jié)構(gòu)特性换可，最大值位于二分搜索樹的最右邊，最小值位于二分搜索樹的最左邊厦幅。因此沾鳄，刪除最大值和最小值可以很容易使用遞歸方法來(lái)實(shí)現(xiàn)：
-
刪除最小值
// 刪除二分搜索樹中的最小值,返回刪除后的根結(jié)點(diǎn) public Node removeMin(){ // 如果根節(jié)點(diǎn)為空，拋異常（可選操作） if(root==null) { throw new IllegalArgumentException("Remove failed. The tree is empty."); } // 刪除根節(jié)點(diǎn)所在樹的最小值，并返回刪除后的根結(jié)點(diǎn) root = removeMin(root); return root; } // 從以node 為根的二分搜索樹中刪除最小值,返回刪除后的根結(jié)點(diǎn) private Node removeMin(Node node) { // 如果節(jié)點(diǎn)左孩子為空，說(shuō)明該節(jié)點(diǎn)即為最小值洽蛀，直接刪除 if(node.left==null) { node = node.right; size--; } // 如果節(jié)點(diǎn)左孩子不為空痪寻，遞歸從以左孩子為根結(jié)點(diǎn)的二分搜索樹中刪除最小值，并返回刪除后的根節(jié)點(diǎn) else { node.left = removeMin(node.left); } return node; } -
刪除最大值（與刪除最小值類似）
// 刪除二分搜索樹中的最大值,返回刪除后的根結(jié)點(diǎn) public Node removeMax(){ if(root==null) throw new IllegalArgumentException("Remove failed. The tree is empty."); else { root = removeMax(root); return root; } } // 從以node 為根的二分搜索樹中刪除最大值,返回刪除后的根結(jié)點(diǎn) private Node removeMax(Node node) { if(node.right==null) { node = node.left; size--; } else { node.right =removeMax(node.right); } return node; }
3.2 刪除最大值和最小值的第二種方法
上述刪除操作，沒(méi)能返回刪除的元素值，不實(shí)用。這里介紹第二種刪除方法篙骡，即先找到二分搜索樹中的最大值和最小值所在節(jié)點(diǎn)，然后刪除該節(jié)點(diǎn)丈甸。
-
查找最小值
// 找到二分搜索樹中的最小值 public E minimum(){ if(size==0) throw new IllegalArgumentException("The tree is empty."); else { // 調(diào)用私有最小值函數(shù) // 找到以root為根節(jié)點(diǎn)的二分搜索樹中的最小值所在節(jié)點(diǎn) Node minNode = minimum(root); return minNode.e; } } // 找到以node 為結(jié)點(diǎn)的二分搜索樹的最小值所在結(jié)點(diǎn) private Node minimum(Node node) { // 如果node節(jié)點(diǎn)的左孩子為空医增，表明node即為最小值所在節(jié)點(diǎn) if(node.left==null) { return node; } else // node節(jié)點(diǎn)的左孩子不為空，則遞歸查找node節(jié)點(diǎn)左子樹中的最小值所在節(jié)點(diǎn) return minimum(node.left); } -
移除最小值的第二種方法（實(shí)際上不能稱之為第二種方法老虫，只加入了查找最小值操作）
// 移除最小值所在節(jié)點(diǎn),返回移除的元素 public E removeMin2(){ if(size==0) { throw new IllegalArgumentException("The tree is empty."); } // 找到以root為根節(jié)點(diǎn)的二分搜索樹的最小值所在節(jié)點(diǎn) Node res = minimum(root); // 調(diào)用私有移除方法 // 移除以root結(jié)點(diǎn)為根的二分搜索樹的最小值所在節(jié)點(diǎn)叶骨，返回移除后的根結(jié)點(diǎn) root = removeMin2(root); return res.e; } // 移除以node結(jié)點(diǎn)為根的二分搜索樹的最小值，返回移除后的根結(jié)點(diǎn) public Node removeMin2(Node node) { if(node.left==null) { node = node.right; size--; } else node.left = removeMin2(node.left); return node; } -
查找最大值
// 找到二分搜索樹中的最大值 public E maxmum(){ if(size==0) throw new IllegalArgumentException("The tree is empty."); else { // 調(diào)用私有最大值函數(shù) // 找到以root為根節(jié)點(diǎn)的二分搜索樹中的最大值所在節(jié)點(diǎn) Node maxNode = maxmum(root); return maxNode.e; } } // 找到以node 為結(jié)點(diǎn)的二分搜索樹的最大值所在結(jié)點(diǎn) private Node maxmum(Node node) { // 如果node節(jié)點(diǎn)的右孩子為空祈匙，表明node即為最大值所在節(jié)點(diǎn) if(node.right==null) { return node; } else // node節(jié)點(diǎn)的右孩子不為空忽刽，則遞歸查找node節(jié)點(diǎn)右子樹中的最大值所在節(jié)點(diǎn) return maxmum(node.right); } -
刪除最大值的“第二種方法”
// 移除最大值的第二種實(shí)現(xiàn)天揖，返回移除的元素 public E removeMax2() { if(size==0) throw new IllegalArgumentException("The tree is empty."); Node delNode = maxmum(root); root = removeMax2(root); return delNode.e; } // 移除以node為根的二分搜索樹的最大值，返回移除后的根結(jié)點(diǎn) private Node removeMax2(Node node) { if(node.right==null) { node = node.left; size--; } else { node.right = removeMax2(node.right); } return node; }
3.3 移除二分搜索樹中的任意元素
前面介紹的移除最大值和最小值都比較簡(jiǎn)單跪帝，困難的是移除二分搜索樹中的任意元素今膊。實(shí)際上，可以分為三種情況來(lái)處理：
-
刪除只有左孩子的節(jié)點(diǎn)
對(duì)只有左孩子的節(jié)點(diǎn)伞剑，直接返回該節(jié)點(diǎn)的左子樹即可
node=node.left -
刪除只有右孩子的節(jié)點(diǎn)
對(duì)只有右孩子的節(jié)點(diǎn)斑唬，直接返回該節(jié)點(diǎn)的右子樹即可
node=node.right -
刪除左右都有孩子的節(jié)點(diǎn)
對(duì)左右都有孩子的節(jié)點(diǎn)，最主要的問(wèn)題是黎泣，刪除該節(jié)點(diǎn)后恕刘，使用哪一個(gè)節(jié)點(diǎn)來(lái)替代該節(jié)點(diǎn)的位置，且能保證二分搜索樹的結(jié)構(gòu)不變抒倚。目前褐着，廣泛采用的是Hibbard在1962年提出的Hibbard刪除法：1）首先從待刪除節(jié)點(diǎn)delNode的右子樹中，找到最小值所在節(jié)點(diǎn)sNode(sNode = minimum(delNode.right))托呕；
minimum(delNode.right)=24
2）將sNode的左子樹賦值為delNode的左子樹(sNode.left = delNode.left)含蓉；
3）將sNode的右子樹賦值為delNode右子樹中刪除sNode以后的二分搜索樹(sNode.right = delMin(delNode.right))；
4） 刪除delNode節(jié)點(diǎn)(delNode.left = delNode.right = null; delNode = sNode)
Java代碼實(shí)現(xiàn)：
// 移除二分搜索樹中的任意元素e
public void removeElement(E e) {
// 如果樹為空项郊，則拋異常（可選擇操作）
if(size==0)
throw new IllegalArgumentException("The tree is empty.");
// 調(diào)用私有方法馅扣，從以root為根的二分搜索樹中刪除元素e
root = removeElement(root,e);
}
// 從以node為根結(jié)點(diǎn)的二分搜索樹種刪除元素e，返回刪除后的根結(jié)點(diǎn)
private Node removeElement(Node node,E e) {
// 如果node為空着降，表明沒(méi)有找到該元素
if(node==null) {
return null;
}
// 1. 如果node節(jié)點(diǎn)就是要?jiǎng)h除的元素
// 分三種情況分別處理
if(e.equals(node.e)) {
// 1）待刪除結(jié)點(diǎn)左子樹為空的情況
if(node.left==null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
// 2）待刪除結(jié)點(diǎn)右子樹為空的情況
if(node.right==null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
// 3）待刪除結(jié)點(diǎn)左右子樹均不為空的情況
// 找到待刪除節(jié)點(diǎn)右子樹中的最小值作為新的節(jié)點(diǎn)
Node minNode = minimum(node.right);
// 新節(jié)點(diǎn)的右子樹為待刪除節(jié)點(diǎn)右子樹中刪掉最小值的樹
minNode.right = removeMin2(node.right);
// 新節(jié)點(diǎn)的左子樹為待刪除節(jié)點(diǎn)的左子樹
minNode.left = node.left;
// 待刪除節(jié)點(diǎn)的左右子樹清空
node.left = node.right = null;
// 返回新節(jié)點(diǎn)作為根節(jié)點(diǎn)
return minNode;
}
// 2. 如果要?jiǎng)h除的元素小于node節(jié)點(diǎn)的元素差油，向node的左子樹遞歸
else if(e.compareTo(node.e)<0) {
node.left = removeElement(node.left,e);
return node;
}
else { // 3. e.compareTo(node.e)>0
node.right = removeElement(node.right,e);
return node;
}
}
4. 總結(jié)
本節(jié)課主要學(xué)習(xí)了二分搜索樹這樣一種高效的數(shù)據(jù)結(jié)構(gòu)。從二分搜索樹的基本結(jié)構(gòu)出發(fā)鹊碍，介紹了如何使用遞歸法向二分搜索樹中添加元素、查找元素以及二分搜索樹的前序食绿、中序和后序遍歷的遞歸實(shí)現(xiàn)侈咕。借助之前棧的相關(guān)知識(shí)，實(shí)現(xiàn)了二分搜索樹前序遍歷的非遞歸實(shí)現(xiàn)器紧；借助隊(duì)列的相關(guān)知識(shí)又實(shí)現(xiàn)了二分搜索樹的層序遍歷耀销。最后，介紹了如何從二分搜索樹中刪除元素铲汪，包括最小值熊尉、最大值以及任意指定的元素。主要難點(diǎn)在于如何刪除任意元素掌腰，這里又細(xì)分了三種情況進(jìn)行處理：待刪除節(jié)點(diǎn)只有右孩子狰住、只有左孩子以及左右都有孩子。對(duì)于左右都有孩子的情況齿梁，采用Hibbard刪除法催植，從右孩子中找到最小值節(jié)點(diǎn)作為新的根節(jié)點(diǎn)肮蛹。下節(jié)課學(xué)習(xí)集合與映射這兩種數(shù)據(jù)結(jié)構(gòu)，并深入分析二分搜索樹的時(shí)間復(fù)雜度创南。
