《漫畫算法: 小灰的算法之旅》第三章 樹
樹和二叉樹
樹和圖是典型的非線性數(shù)據(jù)結(jié)構(gòu)
樹：從“根”衍生出許多“枝干”，再從每個“枝干”衍生出許多更小的“枝干”，最后衍生出更多的“葉子”
樹(tree)是n(n>=0)個節(jié)點的有限集。
當(dāng)n=0時，稱為空樹。
在任意一個非空樹中，有如下特點：
有且僅有一個特定的，稱為根(root)的節(jié)點
當(dāng)n>1時，其余節(jié)點可分為m(m>0)個互不相交的有限集，每一個集合本身又是一個樹，并稱為根的子樹
樹的最大層級數(shù)，稱為樹的高度或深度。上圖樹的高度為4
二叉樹(binary tree): 這種樹的每個節(jié)點最多有2個孩子節(jié)點
滿二叉樹：一個二叉樹的所有非葉子節(jié)點都存在左孩子和右孩子，并且所有葉子節(jié)點都在同一層級上
完全二叉樹: 對一個有n個節(jié)點的二叉樹，按層級順序編號，則所有節(jié)點的編號為從1到n。如果這個樹所有節(jié)點和同樣深度的滿二叉樹的編號為從1到n的節(jié)點位置相同，則這個二叉樹為完全二叉樹。
二叉樹可以用 鏈?zhǔn)酱鎯Y(jié)構(gòu) 或者 數(shù)組 來進行存儲
鏈?zhǔn)酱鎯Y(jié)構(gòu)：
二叉樹的每一個節(jié)點包含3個部分，一是存儲數(shù)據(jù)的data變量，二是指向左孩子的left指針，三是指向右孩子的right指針，一個節(jié)點最多可以指向左右兩個孩子節(jié)點
數(shù)組存儲結(jié)構(gòu)：
使用數(shù)組存儲時，會按照層級順序把二叉樹的節(jié)點放到數(shù)組中對應(yīng)的位置上。如果某一個節(jié)點的左孩子或右孩子空缺，則數(shù)組的相應(yīng)位置也空出來。
假設(shè)一個父節(jié)點的下標(biāo)是parent， 那么它的左孩子節(jié)點的下標(biāo)就是2×parent+1；
右孩子節(jié)點的下標(biāo)就是2×parent +2
假設(shè)一個左孩子節(jié)點的下標(biāo)是leftChild，那么它的父節(jié)點下標(biāo)就是(leftChild-1) / 2；
右孩子節(jié)點的下標(biāo)是rightChild，那么他的父節(jié)點下標(biāo)就是(rightChild-2) / 2
二叉樹主要應(yīng)用在 查找操作 和 維持相對順序 這兩個方面
1.查找
二叉查找樹(binary search tree): 也叫二叉排序樹(binary sort tree)
二叉查找樹在二叉樹的基礎(chǔ)上增加了以下幾個條件：
* 如果左子樹不為空，則左子樹上所有節(jié)點的值均小于根節(jié)點的值
* 如果右子樹不為空，則右子樹上所有節(jié)點的值均大于根節(jié)點的值
* 左子樹、右子樹也都是二叉查找樹
例如查找值為4的節(jié)點，步驟如下：
對于一個節(jié)點分布相對均衡的二叉查找樹來說，如果節(jié)點總數(shù)是n，那么搜索節(jié)點的時間復(fù)雜度就是O(logn)，和樹的深度是一樣的
2. 維持相對順序
如何解決這個問題呢？這就涉及二叉樹的自平衡了；
二叉樹自平衡的方式有多種，如紅黑樹、AVL樹、樹堆等；
除二叉查找樹以外，二叉堆也維持著相對的順序；
不過二叉堆的條件要寬松一些，只要求父節(jié)點的值比它的左右孩子的值都大
二叉樹的遍歷
遍歷是一個線性操作。
二叉樹，是典型的非線性數(shù)據(jù)結(jié)構(gòu)，遍歷時需要把非線性關(guān)聯(lián)的節(jié)點轉(zhuǎn)化成一個線性的序列
從節(jié)點之間位置關(guān)系的角度來看，二叉樹的遍歷方式有4種：
前序遍歷
中序遍歷
后序遍歷
層序遍歷
從更宏觀的角度來看，二叉樹的遍歷歸結(jié)為兩大類：
深度優(yōu)先遍歷(前序遍歷、中序遍歷、后序遍歷)
廣度優(yōu)先遍歷(層序遍歷)
深度優(yōu)先遍歷：
1. 前序遍歷
二叉樹的前序遍歷，輸出順序是根節(jié)點、左子樹、右子樹
2. 中序遍歷
輸出順序是左子樹、根節(jié)點、右子樹
3. 后序遍歷
輸出順序是左子樹、右子樹、根節(jié)點
絕大多數(shù)可以用遞歸解決的問題，其實都可以用另一種數(shù)據(jù)結(jié)構(gòu)來解決，這種數(shù)據(jù)結(jié)構(gòu)就是棧
。因為遞歸和棧都有回溯的特性。
使用棧來完成二叉樹的前序遍歷：
節(jié)點4既沒有左孩子，也沒有右孩子，我們需要回溯到上一個節(jié)點2；
讓舊的棧頂元素4出棧，就可以重新訪問節(jié)點2，得到節(jié)點2的右孩子節(jié)點5；
此時節(jié)點2已經(jīng)沒有利用價值（已經(jīng)訪問過左孩子和右孩子），節(jié)點2出棧，節(jié)點5入棧；
節(jié)點5既沒有左孩子，也沒有右孩子，我們需要再次回溯，一直回溯到節(jié)點1，所以讓節(jié)點5出棧；
根節(jié)點1的右孩子是節(jié)點3，節(jié)點1出棧，節(jié)點3入棧；
節(jié)點3的右孩子是節(jié)點6，節(jié)點3出棧，節(jié)點6入棧；
節(jié)點6既沒有左孩子，也沒有右孩子，所以節(jié)點6出棧，此時棧為空，遍歷結(jié)束
廣度優(yōu)先遍歷
層序遍歷: 二叉樹按照從根節(jié)點到葉子節(jié)點的層次關(guān)系，一層一層橫向遍歷各個節(jié)點。
什么是二叉堆
二叉堆本質(zhì)上是一種完全二叉樹，分為最大堆和最小堆。
最大堆的任何一個父節(jié)點的值，都大于或等于它左孩子或右孩子節(jié)點的值。
最小堆的任何一個父節(jié)點的值，都小于或等于它左孩子或右孩子節(jié)點的值。
二叉堆的根節(jié)點叫作堆頂；
最大堆的堆頂是整個堆中的最大元素；
最小堆的堆頂是整個堆中的最小元素
二叉堆有：1.插入節(jié)點 2.刪除節(jié)點 3.構(gòu)建二叉堆
堆的自我調(diào)整: 把一個不符合堆性質(zhì)的完全二叉樹，調(diào)整成一個堆
1. 插入節(jié)點
目前的是最小堆；
當(dāng)在二叉堆中插入節(jié)點時，插入位置是完全二叉樹的最后一個位置。
2. 刪除節(jié)點
從二叉堆刪除節(jié)點的過程和插入節(jié)點的過程正好相反，所刪除的是處于堆頂?shù)墓?jié)點；
刪除最小堆的堆頂節(jié)點1
3. 構(gòu)建二叉堆
把一個無序的完全二叉樹調(diào)整為二叉堆，本質(zhì)就是讓所有非葉子節(jié)點依次“下沉”。
然后輪到節(jié)點1，如果節(jié)點1大于它的左孩子、右孩子節(jié)點中最小的一個，則節(jié)點1“下沉”。事實上，節(jié)點1小于它的左孩子、右孩子，所以不用改變。
堆的插入和刪除操作，時間復(fù)雜度為O(logn);
構(gòu)建堆的時間復(fù)雜度，時間復(fù)雜度為O(n)
二叉堆的代碼實現(xiàn)
假設(shè)父節(jié)點的下標(biāo)是parent，那么它的左孩子的下標(biāo)就是2×parent+1；
右孩子的下標(biāo)就是2×parent+2
什么是優(yōu)先隊列
優(yōu)先隊列
最大優(yōu)先隊列，無論入隊順序如何，都是當(dāng)前最大的元素優(yōu)先出隊。
最小優(yōu)先隊列，無論入隊順序如何，都是當(dāng)前最小的元素優(yōu)先出隊
優(yōu)先隊列的實現(xiàn)
可以用最大堆來實現(xiàn)最大優(yōu)先隊列
每一次入隊操作就是堆的插入操作，每一次出隊操作就是刪除堆頂節(jié)點
入隊操作：
出隊操作：
二叉堆節(jié)點“上浮”和“下沉”的時間復(fù)雜度都是O(logn)，所以優(yōu)先隊列入隊和出隊的時間復(fù)雜度也是O(logn)
小結(jié)
什么是樹？
樹是n個節(jié)點的有限集，有且僅有一個特定的稱為根的節(jié)點。當(dāng)n>1時，其余節(jié)點可分為m個互不相交的有限集，每一個集合本身又是一個樹，稱為根的子樹。
什么是二叉樹？
二叉樹是樹的一種特殊形式，每一個節(jié)點最多有兩個孩子節(jié)點。
二叉樹包含完全二叉樹和滿二叉樹兩種特殊形式。
二叉樹的遍歷方式有幾種？
根據(jù)節(jié)點之間的位置關(guān)系，可以分為前序遍歷、中序遍歷、后序遍歷、層序遍歷這4種方式；從更宏觀的角度劃分，可以劃分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩大類。
什么是二叉堆？
二叉堆是一種特殊的完全二叉樹，分為最大堆和最小堆。
在最大堆中，任何一個父節(jié)點的值，都大于或等于它的左孩子、右孩子節(jié)點的值。
在最小堆中，任何一個父節(jié)點的值，都小于或等于它的左孩子、右孩子節(jié)點的值。
什么是優(yōu)先隊列？
優(yōu)先隊列分為最大優(yōu)先隊列和最小優(yōu)先隊列。
在最大優(yōu)先隊列中，無論入隊順序如何，當(dāng)前最大的元素都會優(yōu)先出隊，這是基于最大堆實現(xiàn)的。
在最小優(yōu)先隊列中，無論入隊順序如何，當(dāng)前最小的元素都會優(yōu)先出隊，這是基于最小堆實現(xiàn)的。
