五、二叉樹
一、二叉樹入門
之前我們實作的符号表中，不難看出，符号表的增删查操作，随着元素個數N的增多，其耗時也是線性增多的，時
間複雜度都是O(n),為了提高運算效率，接下來我們學習樹這種資料結構。
1.1 樹的基本定義
樹是我們計算機中非常重要的一種資料結構，同時使用樹這種資料結構，可以描述現實生活中的很多事物，例如家
譜、機關的組織架構、等等。
樹是由n（n>=1）個有限結點組成一個具有層次關系的集合。把它叫做“樹”是因為它看起來像一棵倒挂的樹，也就
是說它是根朝上，而葉朝下的。
樹具有以下特點：
1.每個結點有零個或多個子結點；
2.沒有父結點的結點為根結點；
3.每一個非根結點隻有一個父結點；
4.每個結點及其後代結點整體上可以看做是一棵樹，稱為目前結點的父結點的一個子樹；
1.2 樹的相關術語
結點的度：
一個結點含有的子樹的個數稱為該結點的度；
葉結點：
度為0的結點稱為葉結點，也可以叫做終端結點
分支結點：
度不為0的結點稱為分支結點，也可以叫做非終端結點
結點的層次：
從根結點開始，根結點的層次為1，根的直接後繼層次為2，以此類推
結點的層序編号：
将樹中的結點，按照從上層到下層，同層從左到右的次序排成一個線性序列，把他們編成連續的自然數。
樹的度：
樹中所有結點的度的最大值
樹的高度(深度)：
樹中結點的最大層次
森林：
m（m>=0）個互不相交的樹的集合，将一顆非空樹的根結點删去，樹就變成一個森林；給森林增加一個統一的根
結點，森林就變成一棵樹
孩子結點：
一個結點的直接後繼結點稱為該結點的孩子結點
雙親結點(父結點)：
一個結點的直接前驅稱為該結點的雙親結點
兄弟結點：
同一雙親結點的孩子結點間互稱兄弟結點
1.3 二叉樹的基本定義
二叉樹就是度不超過2的樹(每個結點最多有兩個子結點)
滿二叉樹：
一個二叉樹，如果每一個層的結點樹都達到最大值，則這個二叉樹就是滿二叉樹。
完全二叉樹：
葉節點隻能出現在最下層和次下層，并且最下面一層的結點都集中在該層最左邊的若幹位置的二叉樹
1.4 二叉查找樹的建立
1.4.1二叉樹的結點類
根據對圖的觀察，我們發現二叉樹其實就是由一個一個的結點及其之間的關系組成的，按照面向對象的思想，我們
設計一個結點類來描述結點這個事物。
結點類API設計：
代碼實作：
private static class Node<Key, Value> {
public Key key;
public Value value;
public Node left;
public Node right;
public Node(Key key, Value value, Node left, Node right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
1.4.2 二叉查找樹API設計
1.4.3 二叉查找樹實作
插入方法put實作思想：
- 如果目前樹中沒有任何一個結點，則直接把新結點當做根結點使用
- 如果目前樹不為空，則從根結點開始：
2.1 如果新結點的key小于目前結點的key，則繼續找目前結點的左子結點；
2.2 如果新結點的key大于目前結點的key，則繼續找目前結點的右子結點；
2.3 如果新結點的key等于目前結點的key，則樹中已經存在這樣的結點，替換該結點的value值即可
查詢方法get實作思想：
從根節點開始：
- 如果要查詢的key小于目前結點的key，則繼續找目前結點的左子結點；
- 如果要查詢的key大于目前結點的key，則繼續找目前結點的右子結點；
- 如果要查詢的key等于目前結點的key，則樹中傳回目前結點的value。
删除方法delete實作思想：
- 找到被删除結點；
- 找到被删除結點右子樹中的最小結點minNode
- 删除右子樹中的最小結點
-
讓被删除結點的左子樹稱為最小結點minNode的左子樹，讓被删除結點的右子樹稱為最小結點minNode的右
子樹
- 讓被删除結點的父節點指向最小結點minNode
代碼：
public class BinaryTree<Key extends Comparable<Key>, Value> {
// 記錄根節點
private Node root;
// 記錄樹中元素的個數
private int N;
// 擷取樹中元素的個數
public int size() {
return N;
}
// 像樹中添加元素key-value
public void put(Key key, Value value) {
root = put(root, key, value);
}
// 向指定樹x中添加key-value，并傳回添加元素後新的樹
private Node put(Node x, Key key, Value value) {
// 如果x子樹為空
if (x == null) {
N++;
return new Node(key, value, null, null);
}
// 如果x子樹不為空
// 比較x結點的鍵，和key的大小
int cmp = key.compareTo((Key) x.key);
if (cmp > 0) {
// 如果key>x結點的key，則繼續找x結點的右子樹
x.right = put(x.right, key, value);
} else if (cmp < 0) {
// 如果key<x結點的key，則繼續找x結點的左子樹
x.left = put(x.left, key, value);
} else {
// 如果key=x結點的key，則替換x結點的值為value即可
x.value = value;
}
return x;
}
// 查詢樹中指定key對應的value
public Value get(Key key) {
return get(root, key);
}
// 從指定的樹x中，查找key對應的value
private Value get(Node x, Key key) {
// x樹為空
if (x == null) {
return null;
}
// x樹不為空
// 比較x結點的鍵，和key的大小
int cmp = key.compareTo((Key) x.key);
if (cmp > 0) {
// 如果key>x結點的key，則繼續找x結點的右子樹
return get(x.right, key);
} else if (cmp < 0) {
// 如果key<x結點的key，則繼續找x結點的左子樹
return get(x.left, key);
} else {
// 如果key=x結點的key,就是找到了，傳回x結點的值即可
return (Value) x.value;
}
}
// 删除樹中key對應的value
public void delete(Key key) {
delete(root, key);
}
// 删除指定樹x中的key對應的value，并傳回删除後的新樹
public Node delete(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo((Key) x.key);
if (cmp > 0) {
// 如果key>x結點的key，則繼續找x結點的右子樹
x.right = delete(x.right, key);
} else if (cmp < 0) {
// 如果key<x結點的key，則繼續找x結點的左子樹
x.left = delete(x.left, key);
} else {
// 讓元素個數-1
N--;
// 如果key=x結點的key,完成真正的删除結點
// 找到右子樹中最小的結點
if (x.right == null) {
return x.left;
}
if (x.left == null) {
return x.right;
}
Node minNode = x.right;
while (minNode.left != null) {
minNode = minNode.left;
}
// 删除右子樹中最小的結點,也就是找到的minNode
Node n = x.right;
while (n.left != null) {
if (n.left.left == null) {
n.left = null;
} else {
// 變換n結點
n = n.left;
}
}
// 讓删除結點的父結點與删除結點的右結點相連接配接（連接配接大的一方）
n.left = minNode.right;
// 讓x結點的左子樹成為minNode的左子樹
minNode.left = x.left;
// 讓x結點的右子樹成為minNode的右子樹
minNode.right = x.right;
// 讓x結點的父結點指向minNode,因為前面
// x.left = delete(x.left, key);
// x.right = delete(x.right, key); 是以傳回x使得父節點下一個結點變為minNode
x = minNode;
}
return x;
}
private static class Node<Key, Value> {
public Key key;
public Value value;
public Node left;
public Node right;
public Node(Key key, Value value, Node left, Node right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
}
public static void main(String[] args) {
//建立二叉查找樹對象
BinaryTree<Integer, String> tree = new BinaryTree<>();
//測試插入
tree.put(1,"張三");
tree.put(7,"李四");
tree.put(3,"王五");
System.out.println("插入完畢後元素的個數："+tree.size());
//測試擷取
System.out.println("鍵3對應的元素是："+tree.get(3));
//測試删除
tree.delete(3);
System.out.println("删除後的元素個數："+tree.size());
System.out.println("删除後鍵3對應的元素:"+tree.get(3));
}
輸出：
插入完畢後元素的個數：3
鍵3對應的元素是：王五
删除後的元素個數：2
删除後鍵3對應的元素:null
1.4.4 二叉查找樹其他便捷方法
1.4.4.1 查找二叉樹中最小的鍵
在某些情況下，我們需要查找出樹中存儲所有元素的鍵的最小值，比如我們的樹中存儲的是學生的排名和姓名數
據，那麼需要查找出排名最低是多少名？這裡我們設計如下兩個方法來完成：
/*
找出樹中最小的鍵
*/
public Key min() {
return (Key) min(root).key;
}
/*
找出指定樹x中，最小鍵所在的結點
*/
private Node min(Node x) {
if (x.left != null) {
return min(x.left);
} else {
return x;
}
}
1.4.4.2 查找二叉樹中最大的鍵
在某些情況下，我們需要查找出樹中存儲所有元素的鍵的最大值，比如比如我們的樹中存儲的是學生的成績和學生
的姓名，那麼需要查找出最高的分數是多少？這裡我們同樣設計兩個方法來完成：
/*
找出樹中最大的鍵
*/
public Key max() {
return (Key) max(root).key;
}
/*
找出指定樹x中，最小大鍵所在的結點
*/
private Node max(Node x) {
if (x.right != null) {
return max(x.right);
} else {
return x;
}
}
1.5 二叉樹的基礎周遊
很多情況下，我們可能需要像周遊數組數組一樣，周遊樹，進而拿出樹中存儲的每一個元素，由于樹狀結構和線性
結構不一樣，它沒有辦法從頭開始依次向後周遊，是以存在如何周遊，也就是按照什麼樣的搜尋路徑進行周遊的問
題。
我們把樹簡單的畫作上圖中的樣子，由一個根節點、一個左子樹、一個右子樹組成，那麼按照根節點什麼時候被訪
問，我們可以把二叉樹的周遊分為以下三種方式：
- 前序周遊；
先通路根結點，然後再通路左子樹，最後通路右子樹
- 中序周遊；
先通路左子樹，中間通路根節點，最後通路右子樹
- 後序周遊；
先通路左子樹，再通路右子樹，最後通路根節點
如果我們分别對下面的樹使用三種周遊方式進行周遊，得到的結果如下：
1.5.1 前序周遊
我們在4.4中建立的樹上，添加前序周遊的API：
public Queue<Key> preErgodic()：
使用前序周遊，擷取整個樹中的所有鍵
private void preErgodic(Node x,Queue<Key> keys)：
使用前序周遊，把指定樹x中的所有鍵放入到keys隊
列中
實作過程中，我們通過前序周遊，把,把每個結點的鍵取出，放入到隊列中傳回即可。
實作步驟：
1.把目前結點的key放入到隊列中;
2.找到目前結點的左子樹，如果不為空，遞歸周遊左子樹
3.找到目前結點的右子樹，如果不為空，遞歸周遊右子樹
代碼：
/*
使用前序周遊，擷取整個樹中的所有鍵
*/
public Queue<Key> preErgodic() {
Queue<Key> keys = new Queue<>();
preErgodic(root, keys);
return keys;
}
/*
使用前序周遊，把指定樹x中的所有鍵放入到keys隊列中
*/
private void preErgodic(Node x, Queue<Key> keys) {
if (x == null) {
return;
}
// 把x結點的key放到keys中
keys.enqueue((Key) x.key);
// 遞歸周遊x結點的左子樹
if (x.left != null) {
preErgodic(x.left, keys);
}
// 遞歸周遊x結點的右子樹
if (x.right != null) {
preErgodic(x.right, keys);
}
}
1.5.2 中序周遊
我們在4.4中建立的樹上，添加前序周遊的API：
public Queue<Key> midErgodic()：
使用中序周遊，擷取整個樹中的所有鍵
private void midErgodic(Node x,Queue<Key> keys)：
使用中序周遊，把指定樹x中的所有鍵放入到keys隊
列中
實作步驟：
1.找到目前結點的左子樹，如果不為空，遞歸周遊左子樹
2.把目前結點的key放入到隊列中;
3.找到目前結點的右子樹，如果不為空，遞歸周遊右子樹
代碼：
/*
使用中序周遊，擷取整個樹中的所有鍵
*/
public Queue<Key> midErgodic() {
Queue<Key> keys = new Queue<>();
midErgodic(root, keys);
return keys;
}
/*
使用中序周遊，把指定樹x中的所有鍵放入到keys隊列中
*/
private void midErgodic(Node x, Queue<Key> keys) {
if (x == null) {
return;
}
// 先遞歸把左子樹中的鍵放到keys中
if (x.left != null) {
midErgodic(x.left, keys);
}
// 把目前結點x的鍵放到keys中
keys.enqueue((Key) x.key);
// 在遞歸把右子樹中的鍵放到keys中
if (x.right != null) {
midErgodic(x.right, keys);
}
}
1.5.3 後序周遊
我們在4.4中建立的樹上，添加前序周遊的API：
public Queue<Key> afterErgodic()：
使用後序周遊，擷取整個樹中的所有鍵
private void afterErgodic(Node x,Queue<Key> keys)：
使用後序周遊，把指定樹x中的所有鍵放入到keys隊列中
實作步驟：
1.找到目前結點的左子樹，如果不為空，遞歸周遊左子樹
2.找到目前結點的右子樹，如果不為空，遞歸周遊右子樹
3.把目前結點的key放入到隊列中;
代碼：
/*
使用後序周遊，擷取整個樹中的所有鍵
*/
public Queue<Key> afterErgodic() {
Queue<Key> keys = new Queue<>();
afterErgodic(root, keys);
return keys;
}
/*
使用後序周遊，把指定樹x中的所有鍵放入到keys隊列中
*/
private void afterErgodic(Node x, Queue<Key> keys) {
if (x == null) {
return;
}
// 先遞歸把左子樹中的鍵放到keys中
if (x.left!=null){
afterErgodic(x.left,keys);
}
// 在遞歸把右子樹中的鍵放到keys中
if (x.right!=null){
afterErgodic(x.right,keys);
}
// 把目前結點x的鍵放到keys中
keys.enqueue((Key) x.key);
}
1.6 二叉樹的層序周遊
所謂的層序周遊，就是從根節點（第一層）開始，依次向下，擷取每一層所有結點的值，有二叉樹如下：
那麼層序周遊的結果是：EBGADFHC
我們在4.4中建立的樹上，添加層序周遊的API：
public Queue<Key> layerErgodic()：
使用層序周遊，擷取整個樹中的所有鍵
實作步驟：
- 建立隊列，存儲每一層的結點；
-
使用循環從隊列中彈出一個結點：
2.1 擷取目前結點的key；
2.2 如果目前結點的左子結點不為空，則把左子結點放入到隊列中
2.3 如果目前結點的右子結點不為空，則把右子結點放入到隊列中
代碼：
/**
* 層序周遊
* @return
*/
public Queue<Key> layerErgodic(){
// 定義兩個隊列。分别存儲樹中的鍵和樹中的結點
Queue<Key> keys = new Queue<>();
Queue<Node> nodes = new Queue<>();
// 預設，往隊列中放入根結點
nodes.enqueue(root);
while (!nodes.isEmpty()){
// 從隊列中彈出一個結點，把key放入到keys中
Node n = nodes.dequeue();
keys.enqueue((Key) n.key);
// 判斷目前結點還有沒有左子節點，如果有，則放入到nodes中
if (n.left!=null){
nodes.enqueue(n.left);
}
// 判斷目前結點還有沒有右子節點，如果有，則放入到nodes中
if (n.right!=null){
nodes.enqueue(n.right);
}
}
return keys;
}
1.7 二叉樹的最大深度問題
需求：
給定一棵樹，請計算樹的最大深度（樹的根節點到最遠葉子結點的最長路徑上的結點數）
上面這棵樹的最大深度為4。
實作：
我們在1.4中建立的樹上，添加如下的API求最大深度：
public int maxDepth()：計算整個樹的最大深度
private int maxDepth(Node x):計算指定樹x的最大深度
實作步驟：
- 如果根結點為空，則最大深度為0；
- 計算左子樹的最大深度；
- 計算右子樹的最大深度；
- 目前樹的最大深度=左子樹的最大深度和右子樹的最大深度中的較大者+1
代碼：
// 擷取整個樹的最大深度
public int maxDepth() {
return maxDepth(root);
}
// 擷取指定樹x的最大深度
public int maxDepth(Node x) {
if (x == null) {
return 0;
}
// 總的深度
int max = 0;
// 左子樹深度
int maxL = 0;
// 右子樹深度
int maxR = 0;
// 計算x左子樹的最大深度
if (x.left != null) {
maxL = maxDepth(x.left);
}
// 計算x右子樹的最大深度
if (x.right != null) {
maxR = maxDepth(x.right);
}
// 取二者較大的
max = maxL > maxR ? maxL + 1 : maxR + 1;
return max;
}