1 樹
1.1 定義
結(jié)合圖看，可以比較直觀地發(fā)現(xiàn)，
樹(Tree)是元素的集合，每棵樹由多個節(jié)點（node）組成，用以儲存元素。某些節(jié)點之間存在著一定的關(guān)系，用連線表示，連線稱為邊（edge）或者鏈接。邊的上端點成為父節(jié)點，下端稱為子節(jié)點。
每個節(jié)點可以有多個子節(jié)點，而該節(jié)點則是相應(yīng)子節(jié)點的父節(jié)點。但是每個節(jié)點只能有一個父節(jié)點（只有一個例外，也就是根節(jié)點，它沒有父節(jié)點），如圖中第一棵樹的 S 節(jié)點即為根節(jié)點。而沒有子節(jié)點的節(jié)點則稱為葉子節(jié)點或葉節(jié)點，如上圖中第一棵樹的 A、R、X 節(jié)點。E、X 的父節(jié)點是一個節(jié)點，所以它們被稱為兄弟節(jié)點。
通過上面的觀察和分析，這里給出一種相對嚴格的樹的定義。
- 樹是元素的集合
- 該集合可以為空。此時樹中沒有元素，稱之為
空樹（empty tree）。- 如果該集合不為空，那么該集合至少含有一個根節(jié)點以及 0 個或多個子樹。根節(jié)點與它的子樹的根節(jié)點用一個
邊（edge）或鏈接相連。
1.2 特征（三個特殊概念）
關(guān)于樹，有三個比較相似，容易搞混的概念：高度（Height）、深度（Depth）、層（Level）。它們的定義如下。
- 節(jié)點的高度 = 節(jié)點到葉子結(jié)點的
最長路徑（邊數(shù)）- 節(jié)點的深度 = 根節(jié)點到這個節(jié)點所經(jīng)歷的
邊的個數(shù)- 節(jié)點的層數(shù) = 節(jié)點的深度 + 1
- 樹的高度 = 根節(jié)點的高度
單看定義有點抽象，結(jié)合圖來看會比較好理解。我們可以結(jié)合生活中對高度、深度的概念來看，這樣理解起來就很方便了。比如，對于高度，生活中我們往往是自下而上來度量，比如第 5 樓、第 10 樓，起點都是地面。對于樹這種數(shù)據(jù)結(jié)構(gòu)中的高度也是一樣的類比，從最底層開始進行計數(shù)，并且計數(shù)的起點是 0。
深度這個概念在生活中則是自上而下度量的，比如形容水深，是從水平面開始度量的。對于樹這種數(shù)據(jù)結(jié)構(gòu)而言也是如此，從根節(jié)點開始度量，計數(shù)起點從 0 開始（有些書中是從 1 開始，應(yīng)該都可以，看你怎么定義和使用了，問題不大）。
層數(shù)跟深度的計算類似，不過計數(shù)的起點是 1，也就是說跟節(jié)點位于第一層。
2 二叉樹
2.1 定義
二叉樹是一種特殊的數(shù)據(jù)結(jié)構(gòu)，顧名思義，二叉樹只有兩個叉，也就是兩個子節(jié)點：左子節(jié)點和右子節(jié)點。其中，左子節(jié)點是左子樹的根節(jié)點，右子節(jié)點是右子樹的根節(jié)點。當然，這并不是說，二叉樹一定要求每個節(jié)點都必須有兩個子節(jié)點，有的節(jié)點只有左子節(jié)點，而有的節(jié)點只有右子節(jié)點。
還是老慣例，結(jié)合圖看。在這個圖里面，有兩個比較特殊的二叉樹，分別是編號 2 和 3 的這兩個。其中，編號 2 的二叉樹中，葉節(jié)點全都在最底層，除了葉節(jié)點之外，每個節(jié)點都于左右兩個子節(jié)點，這種二叉樹就叫
滿二叉樹。而編號為 3 的二叉樹中，葉子結(jié)點在最底下兩層，其中，最后一層的節(jié)點都靠左排列，并且，除了最后一層，其他層的節(jié)點數(shù)都要達到最大，這種二叉樹叫做完全二叉樹。2.2 二叉樹的三種遍歷方法
二叉樹經(jīng)典的遍歷方法一共有三種，分別是前序遍歷、中序遍歷和后序遍歷。其中，前、中、后序，表示的是節(jié)點與它的左右子樹節(jié)點遍歷打印的先后順序。
前序遍歷（也叫先序遍歷）：若二叉樹為空，則空操作，否則，對于二叉樹中的任意節(jié)點，先訪問這個節(jié)點，然后再訪問它的左子樹，最后打印它的右子樹。中序遍歷：若二叉樹為空，則空操作，否則，對于二叉樹中的任意節(jié)點，先訪問它的左子樹，然后再訪問這個節(jié)點本身，最后訪問它的右子樹。后序遍歷：若二叉樹為空，則空操作，否則，對于二叉樹中的任意節(jié)點，先訪問它的左子樹，然后訪問它的右子樹，最后訪問這個節(jié)點本身。
| 遍歷方式 | 遍歷結(jié)果 |
|---|---|
| 前序遍歷 | S->E->B->A->C->P->O->R->X |
| 中序遍歷 | A->B->C->E->O->P->R->S->X |
| 后序遍歷 | A->C->B->O->R->P->E->X->S |
2.3 樹與二叉樹的區(qū)別
- 二叉樹的每個節(jié)點最多只能有兩個節(jié)點，而樹則無限制
- 二叉樹中節(jié)點的子樹分為左子樹和右子樹，即使某個節(jié)點只有一棵樹，也必須要指明這棵樹是左子樹還是右子樹，也就是說，二叉樹是有序的
- 樹不能為空，至少含有一個節(jié)點，而一棵二叉樹可以為空
3 二叉查找樹
3.1 定義
二叉查找樹（Binary Search Tree，BST）是一種特殊的二叉樹，一棵二叉搜索樹（BST）是一棵二叉樹，其中，每個節(jié)點的值都要大于其左子樹中任意節(jié)點的值而小于右子樹中任意節(jié)點的值。
3.2 基本操作
3.2.1 查找
如果要在二叉查找樹中查找一個節(jié)點 X，我們可以分為一下幾步。
- 如果二叉查找樹為空，則返回空操作，否則，執(zhí)行一下操作；
- 先取根節(jié)點，如果節(jié)點 X 等于根節(jié)點，則返回；
- 如果節(jié)點小于根節(jié)點，則遞歸查找左子樹；
- 如果節(jié)點大于根節(jié)點，則遞歸查找右子樹。
3.2.2 插入
在二叉樹中插入一個節(jié)點，一般都是插入到葉節(jié)點上，所以只需從根結(jié)點開始，依次遍歷比較要插入的數(shù)據(jù)和節(jié)點的大小關(guān)系。
二叉查找樹有一個很重要的特性就是插入的實現(xiàn)難度和查找差不多。當查找的節(jié)點不存在于二叉查找樹中并且結(jié)束于一條空鏈時，我們要做的就是將鏈接（邊）指向一個含有被查找節(jié)點的新節(jié)點。說得有點拗口，其實可以細分為以下幾步。
- 如果樹是空的，則直接將新節(jié)點插入，否則，執(zhí)行下面步驟。
- 要插入的數(shù)據(jù)比根節(jié)點數(shù)據(jù)大，則到右子樹中插入新數(shù)據(jù)，如果右子樹為空，則將新數(shù)據(jù)直接插入到右子節(jié)點的位置；不為空，則繼續(xù)遍歷右子樹，查找插入位置。
- 要插入的數(shù)據(jù)比根節(jié)點數(shù)據(jù)小，則到左子樹中插入數(shù)據(jù)，如果左子樹為空，則直接將新數(shù)據(jù)插入到左子節(jié)點的位置；不為空，則繼續(xù)遍歷左子樹，查找插入的位置。
3.2.3 刪除
二叉樹的刪除相對于查找和插入要復(fù)雜一些，針對要刪除節(jié)點的子節(jié)點個數(shù)的不同，一般分為三種情況來處理。
- 第一種情況，如果要刪除的節(jié)點沒有子節(jié)點，直接將父節(jié)點指向要刪除節(jié)點的指針指向 null。比如途中要刪除的節(jié)點 55。
- 第二種情況，如果要刪除的節(jié)點只有一個節(jié)點，即只有左子節(jié)點或右子節(jié)點，則將父節(jié)點指向要刪除節(jié)點的指針指向要刪除節(jié)點的子節(jié)點即可。比如途中要刪除的節(jié)點
13。- 第三種情況，如果要刪除的節(jié)點有兩個子節(jié)點，則需要先找到這個節(jié)點右子樹中的最小節(jié)點或者左子樹中的最大節(jié)點，將其替換到要刪除的節(jié)點上。然后刪除這個右子樹中的最小節(jié)點或左子樹中的最大節(jié)點，這樣就可以利用
1、2 兩條規(guī)則來刪除了。比如圖中要刪除的節(jié)點 18。
3.2.4 查找最大、最小節(jié)點
查找最大、最小節(jié)點比較簡單，比如要查找二叉查找樹的最大節(jié)點時，如果二叉查找樹為空，則返回空操作，如果不為空，則判斷是否只有一個節(jié)點（即只有根節(jié)點），如果是則返回根節(jié)點，否則到右子樹中遞歸查找。同理，查找最小節(jié)點類似，只是到左子樹中查找而已。
代碼
廢話不多說，上代碼吧，結(jié)合代碼看會比較清晰。
public class BinarySearchTree {
private Node tree;
/**
* 查找
* @param data
* @return
*/
public Node find(int data) {
Node p = tree;
while (p != null) {
if (data < p.data) p = p.left;
else if (data > p.data) p = p.right;
else return p;
}
return null; //沒有找到
}
/**
* 插入
* @param data
*/
public void insert(int data) {
if (tree == null) {
tree = new Node(data);
return;
}
Node p = tree;
while (p != null) {
if (data > p.data) {
if (p.right == null) {
p.right = new Node(data);
return;
}
p = p.right;
} else { //data < p.data
if (p.left == null) {
p.left = new Node(data);
return;
}
p = p.left;
}
}
}
/**
* 刪除
* @param data
*/
public void delete(int data) {
Node p = tree; //p 指向要刪除的結(jié)點，初始化指向根節(jié)點
Node pp = null; //pp 記錄的是 p 的父節(jié)點
while (p != null && p.data != data) {
pp = p;
if (data > p.data) p = p.right;
else p = p.left;
}
if (p == null) return; //沒有找到
//要刪除的節(jié)點有兩個子節(jié)點
if (p.left != null && p.right != null) {//查找右子樹中最小的節(jié)點
Node minP = p.right;
Node minPP = p; //minPP 表示 minP 的父節(jié)點
while (minP.left != null) {
minPP = minP;
minP = p.left;
}
p.data = minP.data; //將 minP 的數(shù)據(jù)替換到 p 中
p = minP; //下面就變成了刪除 minP 了,要結(jié)合整個刪除函數(shù)來看
pp = minPP;
}
//刪除的是葉子節(jié)點或者僅有一個子節(jié)點
Node child; //p 的子節(jié)點
if (p.left != null) child = p.left;
else if (p.right != null) child = p.right;
else child = null;
if (pp == null) tree = child; // 刪除的是根節(jié)點
else if (pp.left == p) pp.left = child;
else pp.right = child;
}
/**
* 查找最小節(jié)點
* @return
*/
public Node findMin() {
if (tree == null) return null;
Node p = tree;
while (p.left != null) {
p = p.left;
}
return p;
}
/**
* 查找最大節(jié)點
* @return
*/
public Node findMax() {
if (tree == null) return null;
Node p = tree;
while (p.right != null) {
p = p.right;
}
return p;
}
private static class Node {
private int data;
private Node left;
private Node right;
public Node(int data) {
this.data = data;
}
}
}
本文主要參考來源：
算法(第 4 版)
極客時間專欄《數(shù)據(jù)結(jié)構(gòu)與算法之美》
樹與二叉樹
紙上談兵：樹，二叉樹，二叉搜索樹
