十二、二叉树
大綱：
- 樹、二叉樹
- 二叉查找樹
- 平衡二叉查找樹、紅黑樹
- 遞歸樹
一、樹（Tree）
1、樹的相關概念
（1）節點
其中，每個元素稱為“節點”；用來連接相鄰節點之間的關系，成為“父子關系”。其他概念：“父節點、子節點、兄弟節點，根節點，葉子節點或葉節點”
==》A 節點就是 B 節點的父節點，B 節點是 A 節點的子節點。B、C、D 這三個節點的父節點是同一個節點，所以它們之間互稱為兄弟節點。我們把沒有父節點的節點叫作根節點，也就是圖中的節點 E。我們把沒有子節點的節點叫作葉子節點或者葉節點，比如圖中的 G、H、I、J、K、L 都是葉子節點。
（2）高度( Height )、深度( Depth )、層( Level )
不要混淆！
- 節點的高度 = 節點到葉子節點的最長路徑（邊數）
- 節點的深度 = 根節點到該節點所經歷的邊的個數
- 節點的層數 = 節點的深度 + 1
- 樹的高度 = 根節點的 高度
示例：
二、二叉樹(Binary Tree)
最常用 的樹結構
1、相關概念
（1）二叉樹
二叉樹：每個節點最多有兩個叉，也就是兩個子節點（左子結點、右子節點）。二叉樹并不要求每個節點都有兩個子節點，有的節點可以只有一個左子結點（或右子節點），有的節點沒有子節點。
（2）滿二叉樹
特點：葉子節點全都在最底層，除葉子節點外，每個結點都有左右兩個子節點。
（3）完全二叉樹
完全二叉樹：葉子節點都在最底下兩層，最后一層的葉子節點都靠左排列，并且除了最后一層，其他層的節點個數都要達到最大。
注意區分：
2、二叉樹的表示(存儲)
兩種存儲方法：
①基于指針或引用的二叉鏈式存儲法；
②基于數組的順序存儲方法。
（1）鏈式存儲法——常用
每個節點有三個字段，分別存儲：數據、指向左右子節點的指針。
==》只要通過根節點，就可以通過左右節點的指針，將整棵樹串起來。
（2）順序存儲法
一般情況下，為了方便計算子節點，根節點會存儲在下標為 1 的位置。
- 將根節點存儲在下標 i = 1 的位置，其左節點存儲在下標 2 * i = 2 的位置，右子節點存儲在 2 * i + 1 = 3的位置。
- 依次類推：
- 若結點 X 存儲在數組中下標為 i 的位置，
- 其左節點下標： 2 * i
- 其右節點下標： 2 * i + 1
- 其父節點下標：i / 2
（3）分析
若二叉樹為完全二叉樹，則數組存儲是最節省內存的一種方式（不需要存儲額外的左右子節點的指針）
==》堆——本質：完全二叉樹，最常用的存儲方式就是數組。
3、二叉樹遍歷
（1）方法
三種方法：前序遍歷、中序遍歷、后序遍歷
==》節點與它的左右子樹節點遍歷的先后順序：中代表該節點，左代表其左子樹，右代表其右子樹。
- 前序遍歷：中、左、右
- 中序遍歷：左、中、右
- 后序遍歷：左、右、中
（2）代碼實現
關鍵點：遞歸代碼 《== 遞歸公式
前序遍歷的遞推公式： preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)中序遍歷的遞推公式： inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)后序遍歷的遞推公式： postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r遞歸代碼：
==》遍歷時間復雜度：O(n)
三、二叉查找樹
特點：支持動態數據集合的快速插入、刪除、查找操作。
1、二叉查找樹（Binary Search Tree）
二叉查找樹是二叉樹中最常用的一種類型，也稱二叉搜索樹。可以快速插入、刪除、查找操作。
結構要求：樹中的任何一個節點，其左子樹的每個節點的值，都要小于該節點的值，而右子樹節點的值都大于這個節點的值。
2、查找操作
目標：查找一個結點
過程：先取根節點，若它等于要查找的數據，則返回；若要查找的數據的值比根節點小，則在左子樹中遞歸查找；若要查找的數據的值比根節點大，則在右子樹中遞歸查找。
3、插入操作
類似查找操作，新插入的數據一般都在葉子節點上
==》只需要從根節點開始，依次比較要插入的數據和節點的大小關系。
過程：若要插入的數據比節點的數據大，并且節點的右子樹為空，則將新數據直接插入到右子節點的位置；若不為空，則遞歸遍歷右子樹，查找插入位置。同理，若要插入的數據比節點的數據小，并且節點的左子樹為空，則將新數據直接插入到左子節點的位置；若不為空，則遞歸遍歷左子樹，查找插入位置。
4、刪除操作
針對要刪除節點的子節點個數的不同，分以下三種情況處理。
- 若要刪除的節點沒有子節點，則只需之間將其父節點中，指向要刪除節點的指針置為null。
- 若要刪除的節點只有一個子節點（只有左子節點或右子節點），只需要更新父節點中，指向要刪除節點的指針，讓其指向要刪除節點的子節點即可。
- 若要刪除的節點有兩個子節點。首先，需要找到該節點的右子樹中最小節點，將它替換到要刪除的節點上，然后再刪除這個最小節點（∵最小節點無左子節點）。
實際：非常簡單、取巧的方法——單純地將要刪除的節點標記為“已刪除”，但并不真正從樹中將這個節點去掉。
==》雖較浪費內存空間，但刪除操作就變得簡單多了，且并沒有增加插入、查找操作代碼實現的難度。
5、其他操作
還支持快速查找最大節點、最小節點、前驅節點和后繼節點。
中序遍歷二叉查找樹
==》輸出：有序的數據序列，時間復雜度為 O(n)
==》也稱：二叉排序樹
四、支持重復數據的二叉查找樹
實際中常在二叉查找樹中存儲的是包含很多字段的對象。并利用某個字段作為鍵值(key)來構建二叉查找樹。對象中的其他字段稱為衛星數據。
1、插入操作
在二叉查找樹中存儲兩個對象鍵值相同的方法：
- 二叉查找樹中每個節點不僅存儲一個數據
==》通過鏈表和支持動態擴容的數組等數據結構，把值相同的數據都存儲在同一個節點上。 - 每個節點仍存儲一個數據。在查找插入位置的過程中，若遇到一個節點的值與要插入數據的值相同，則將這個要插入的數據放在這個節點的右子樹，即，將新插入的數據當作大于這個節點的值來處理。
2、查找操作
當要查找數據時，若遇到值相同的節點，不停止查找操作，而繼續在右子樹中查找，知直到遇到葉子節點，才停止。
==》可將鍵值等于要查找值得所有節點都找出來。
3、刪除操作
過程：首先找到每個要刪除的節點，然后按照前面的刪除操作方法依次刪除節點。
五、時間復雜度分析
不同的二叉查找樹形態各式各樣
==》影響查找、插入、刪除操作的執行效率
情況一：最糟糕——退化為鏈表（根節點的左右子樹極度不平衡）
==》查找的時間復雜度：O(n)
情況二：最理想——完全二叉樹（或滿二叉樹）
==》插入、刪除和查找的時間復雜度：O(height)
==》求一棵包含n個節點的完全二叉樹的高度？
完全二叉樹的高度小于等于 log2n。
==》需要構建一種不管怎么刪除、插入數據，在任何時候，都能保持任意節點左右子樹都比較平衡的二叉查找樹——平衡二叉查找樹
平衡二叉查找樹的高度接近 logn，所以插入、刪除、查找操作的時間復雜度也比較穩定，是 O(logn)。
六、思考
問題：既然有了這么高效的散列表，使用二叉樹的地方是不是都可以替換成散列表呢？有沒有哪些地方是散列表做不了，必須要用二叉樹來做的呢？
- 散列表中的數據是無序存儲的，如果要輸出有序的數據，需要先進行排序。而對于二叉查找樹來說，我們只需要中序遍歷，就可以在 O(n) 的時間復雜度內，輸出有序的數據序列。
- 散列表擴容耗時很多，而且當遇到散列沖突時，性能不穩定，盡管二叉查找樹的性能不穩定，但是在工程中，我們最常用的平衡二叉查找樹的性能非常穩定，時間復雜度穩定在 O(logn)。
- 籠統地來說，盡管散列表的查找等操作的時間復雜度是常量級的，但因為哈希沖突的存在，這個常量不一定比 logn 小，所以實際的查找速度可能不一定比 O(logn) 快。加上哈希函數的耗時，也不一定就比平衡二叉查找樹的效率高。
- 散列表的構造比二叉查找樹要復雜，需要考慮的東西很多。比如散列函數的設計、沖突解決辦法、擴容、縮容等。平衡二叉查找樹只需要考慮平衡性這一個問題，而且這個問題的解決方案比較成熟、固定。
- 為了避免過多的散列沖突，散列表裝載因子不能太大，特別是是基于開放尋址法解決沖突的散列表，不然會浪費一定的存儲空間。
總結
