一、樹的基本概念

1.1樹的定義

• 樹是 N(N>=0) 個(gè)結(jié)點(diǎn)的有限集合，N = 0 時(shí)，稱為空樹，這是一種特殊的情況。
• 樹適合表示具有層次結(jié)構(gòu)的數(shù)據(jù)。
• 樹中的某個(gè)結(jié)點(diǎn)（除根結(jié)點(diǎn)外）最多只和上一層的一個(gè)結(jié)點(diǎn)（即其父結(jié)點(diǎn)）有直接關(guān)系，根結(jié)點(diǎn)沒有直接上層結(jié)點(diǎn)，因此在 n 個(gè)結(jié)點(diǎn)的樹中有 n-1 條邊，而樹中每個(gè)結(jié)點(diǎn)預(yù)期下一節(jié)點(diǎn)的零個(gè)或多個(gè)結(jié)點(diǎn)（即其子女結(jié)點(diǎn)）有直接關(guān)系。

• 在任意一顆非空樹中應(yīng)滿足：
• 有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)。
• 當(dāng) N > 1 時(shí)，其余結(jié)點(diǎn)可分為 m(m>0) 個(gè)互不相交的有限集合 T1，T2，T3，···，Tm，其中每一個(gè)集合本身又是一棵樹，并且稱為根節(jié)點(diǎn)的子樹。

• 樹的結(jié)構(gòu)是遞歸的，是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，樹作為一種邏輯結(jié)構(gòu)，同時(shí)也是以一種分層結(jié)構(gòu)，具有以下兩種特點(diǎn)：
• 樹的根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)。
• 樹中所有的根結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)。

1.2 基本術(shù)語

• 考慮某個(gè)結(jié)點(diǎn) K，根 A 到結(jié)點(diǎn) K 的唯一路徑上的任意節(jié)點(diǎn)，稱為結(jié)點(diǎn) K 的祖先結(jié)點(diǎn)。若結(jié)點(diǎn) B 是結(jié)點(diǎn) K 的祖先結(jié)點(diǎn)，則結(jié)點(diǎn) K 是結(jié)點(diǎn) B 的子孫結(jié)點(diǎn)。路徑上最接近結(jié)點(diǎn) K 的結(jié)點(diǎn) E 稱為 K 的雙親結(jié)點(diǎn)，而 K 為結(jié)點(diǎn) E 的孩子結(jié)點(diǎn)。根結(jié)點(diǎn) A 是樹中唯一沒有雙親的結(jié)點(diǎn)，有相同雙親的結(jié)點(diǎn)稱為兄弟節(jié)點(diǎn)，如若結(jié)點(diǎn) K 與結(jié)點(diǎn) L 有相同的結(jié)點(diǎn) E ，則稱 K 和 L 為兄弟結(jié)點(diǎn)。
• 樹中一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)稱為該結(jié)點(diǎn)的度，樹中結(jié)點(diǎn)的最大度數(shù)稱為樹的度。
• 度大于 0 的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)（又稱非終端結(jié)點(diǎn)）；度為 0 （沒有子女結(jié)點(diǎn)）的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)（又稱終端結(jié)點(diǎn)）。在分支結(jié)點(diǎn)中，每個(gè)結(jié)點(diǎn)的分支數(shù)就是該結(jié)點(diǎn)的度。
• 結(jié)點(diǎn)的層次是從樹根開始定義，根結(jié)點(diǎn)為第 1 層（有些教材將根結(jié)點(diǎn)定義為第 0 層），它的子結(jié)點(diǎn)為第 2 層，以此類推。
• 結(jié)點(diǎn)的深度是從根結(jié)點(diǎn)開始自頂向下逐層累加的。
• 結(jié)點(diǎn)的高度是從葉結(jié)點(diǎn)開始自底向上逐層累加的。
• 樹的高度（又稱深度）是樹中結(jié)點(diǎn)的最大層數(shù)。
• 有序樹和無序樹：樹中結(jié)點(diǎn)的子樹從左到右是有序的，不能交換，這樣的樹叫做有序樹，有序樹中，一個(gè)結(jié)點(diǎn)其子結(jié)點(diǎn)按從左到右順序出現(xiàn)是有關(guān)聯(lián)的。反之則稱為無序樹。
• 路徑和路徑長度：樹中兩個(gè)結(jié)點(diǎn)之間的路徑是由這兩個(gè)結(jié)點(diǎn)之間所經(jīng)過的結(jié)點(diǎn)序列構(gòu)成的，而路徑長度是路徑上所經(jīng)過的邊的個(gè)數(shù)。
• 注意：由于樹中的分支是有向的，即從雙親結(jié)點(diǎn)指向孩子結(jié)點(diǎn)，所以樹中的路徑是從上到下的，同一雙親結(jié)點(diǎn)的兩個(gè)孩子結(jié)點(diǎn)之間不存在路徑。
• 森林：森林是 m(m>=0) 棵互不相交的樹的集合。森林的概念與樹十分相似，只要把樹的根結(jié)點(diǎn)刪去就成了森林。反之，只要給 n 棵獨(dú)立的樹加上一個(gè)結(jié)點(diǎn)，并把這 n 棵樹作為該結(jié)點(diǎn)的子樹，則森林就成了樹。

1.3 樹的性質(zhì)

• 樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加 1。
• 度為 m 的樹中第 i 層上至多有 m^(i-1) 個(gè)結(jié)點(diǎn)（ i>=1）。
• 高度為 h 的 m 叉樹至多有（ m^h - 1）/（ m -1 ）個(gè)結(jié)點(diǎn)。
• 具有 n 個(gè)結(jié)點(diǎn)的 m 叉樹的最小高度為 [ log m（ n*(m-1) + 1 ）]。

二、二叉樹的概念

2.1 二叉樹的定義

• 二叉樹是另一種樹形結(jié)構(gòu)，其特點(diǎn)是每個(gè)節(jié)點(diǎn)至多只有兩棵子樹（即二叉樹中不存在度大于 2 的結(jié)點(diǎn)），而且，二叉樹的子樹有左右之分，其次序不能顛倒。

• 與樹相似，二叉樹也以遞歸的形式定義，二叉樹是 n(n>=0) 個(gè)結(jié)點(diǎn)的有限集合：
• 1）或者為空二叉樹，即 n = 0;
• 2）或者是由一個(gè)根結(jié)點(diǎn)和兩個(gè)互不相交的被稱為根的左子樹和右子樹組成，左子樹和右子樹分別是一棵二叉樹。
• 二叉樹是有序樹，將其左右子樹顛倒，就成為了另一棵不同的二叉樹。即使樹中結(jié)點(diǎn)只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。

• 二叉樹與度為 2 的有序樹的區(qū)別：
• 1）度為 2 的樹至少有 3 個(gè)結(jié)點(diǎn)，而二叉樹可以為空。
• 2）度為 2 的有序樹的孩子結(jié)點(diǎn)就無須區(qū)分其左右次序，而二叉樹無論其孩子數(shù)是否為 2 均需確認(rèn)其左右次序，也就是說二叉樹的結(jié)點(diǎn)次序不是相對于另一個(gè)節(jié)點(diǎn)而言，而是確定的。

2.2 幾個(gè)特殊的二叉樹

• 滿二叉樹：一棵高度為 h，并且含有 2^h - 1 個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹，即樹中的每一層都含有最多的結(jié)點(diǎn)。滿二叉樹的葉子結(jié)點(diǎn)都集中在二叉樹的最下一層，并且除葉子結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)的度數(shù)均為 2。
• 可以對滿二叉樹按層序進(jìn)行編號：約定編號從根結(jié)點(diǎn)（根結(jié)點(diǎn)編號為 1）起，自上而下，自左向右。這樣每個(gè)結(jié)點(diǎn)對應(yīng)一個(gè)編號，對于編號為 i 的結(jié)點(diǎn)，如果有雙親，則雙親為 [ i/2 ] ，如果有左孩子，則左孩子為 2i，右孩子為 2i + 1。

• 完全二叉樹：設(shè)一個(gè)高度為 h，有 n 個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與高度為 h 的滿二叉樹中編號為 1~n 的結(jié)點(diǎn)一一對應(yīng)，稱為完全二叉樹。
• 若 i<=[n/2]，則結(jié)點(diǎn) i 為分支結(jié)點(diǎn)，否則為葉子結(jié)點(diǎn)。
• 葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)，對于最大層次中的葉子結(jié)點(diǎn)，都依次排列在該層最左邊的位置上。
• 如果有度為 1 的結(jié)點(diǎn)，只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子而無右孩子。
• 按層序編號后，一旦出現(xiàn)某個(gè)結(jié)點(diǎn)（其編號為 i ）為葉子結(jié)點(diǎn)或只有左孩子，則編號大于 i 的結(jié)點(diǎn)均為葉子結(jié)點(diǎn)。
• 若 n 為奇數(shù)，則每個(gè)分支結(jié)點(diǎn)都有左孩子和右孩子；若 n 為偶數(shù)，則編號最大的分支結(jié)點(diǎn)（編號為 n/2）只有左孩子，沒有有子女，其余分支結(jié)點(diǎn)左、右子女都有。

• 二叉排序樹：一棵空心樹，或者是具有性質(zhì)的二叉樹：左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字；右子樹上的所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字。左子樹和右子樹又各是一棵二叉排序樹。

• 平衡二叉樹：樹上任一結(jié)點(diǎn)的左子樹和右子樹的深度之差不超過 1。

2.3 二叉樹的性質(zhì)

• 非空二叉樹上葉子結(jié)點(diǎn)數(shù)等于度為 2 的結(jié)點(diǎn)數(shù)加 1，即 N0 = N2 + 1;
• N0 + N1 + N2 = N1 + N2 + N2 + 1;
• 非空二叉樹的第 K 層上至多有 2^(k-1) 個(gè)結(jié)點(diǎn)（K>=1)。
• 高度為 H 的二叉樹至多有 2^H - 1 個(gè)結(jié)點(diǎn)（H>=1)。
• 具有 N(N>0) 個(gè)結(jié)點(diǎn)的完全二叉樹的高度為 [log(N+1)] 或 [log N] + 1。

• 對完全二叉樹按從上到下、從左到右的順序依次編號 1，2，···，N，則有以下關(guān)系：
• 1）當(dāng) i>1 時(shí)，結(jié)點(diǎn) i 的雙親結(jié)點(diǎn)編號為 [i/2]，即當(dāng) i 為偶數(shù)時(shí)，其雙親結(jié)點(diǎn)的編號為 i/2，它是雙親結(jié)點(diǎn)的左孩子。
• 2）當(dāng) 2i<=N 時(shí)，結(jié)點(diǎn) i 的左孩子編號為 2i，否則無有孩子。
• 3）當(dāng) 2i<=N 時(shí)，結(jié)點(diǎn) i 的右孩子編號為 2i+1，否則無右孩子。
• 4）結(jié)點(diǎn) i 所在層次（深度）為 [log i] + 1。

三、二叉樹的存儲(chǔ)結(jié)構(gòu)

3.1 順序存儲(chǔ)結(jié)構(gòu)

• 二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是一組地址連續(xù)的存儲(chǔ)單元依次自上至下，自左至右存儲(chǔ)完全二叉樹上的結(jié)點(diǎn)元素，即將完全二叉樹上編號 i 的結(jié)點(diǎn)元素存儲(chǔ)在某個(gè)數(shù)組下標(biāo)為 i-1 的分量中，然后通過一些方法確定結(jié)點(diǎn)在邏輯上的父子和兄弟關(guān)系。
• 依據(jù)一般的二叉樹，完全二叉樹和滿二叉樹采用順序存儲(chǔ)比較合適，樹中結(jié)點(diǎn)的序號可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系，這樣即能最大程度的節(jié)省空間，又可以利用數(shù)組元素的下標(biāo)值確定結(jié)點(diǎn)在二叉樹中的位置，以及節(jié)點(diǎn)之間的關(guān)系。
• 但對于一般的二叉樹，為了讓數(shù)組下標(biāo)能反映二叉樹中結(jié)點(diǎn)之間的邏輯關(guān)系，只能添加一些并不存在的空結(jié)點(diǎn)讓其每個(gè)結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)相對照，再存儲(chǔ)到一維數(shù)組的相應(yīng)分量中。然而，在最壞的情況下，一個(gè)高度為 H 且只有 H 個(gè)結(jié)點(diǎn)的單支數(shù)卻需要占據(jù)接近 2^H-1 個(gè)存儲(chǔ)單元。

3.2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

• 二叉鏈表至少包含 3 個(gè)域：數(shù)據(jù)域 data、左指針域 lchild、右指針域 rchild。
• 在含有 n 個(gè)結(jié)點(diǎn)的二叉鏈表中含有 n+1 個(gè)空鏈域。

四、二叉樹的遍歷

4.1 二叉樹的遍歷

• 先序遍歷、中序遍歷、后序遍歷、遞歸算法與非遞歸算法的轉(zhuǎn)換、層序遍歷、由遍歷序列構(gòu)造二叉樹。