408答疑

---

---

二、樹、森林

樹的基本概念

樹的定義和特性

樹的定義

樹是一個遞歸的概念，由 $n(n\ge 0)$ 個結點的有限集組成。當 $n=0$ 時，稱為空樹。在任意一棵非空樹中應滿足：

1. 有且僅有一個特定的稱為根的結點。
2. 當 $n>1$ 時，其余結點可分為 $m(m>0)$ 個互不相交的有限集 $T_1,T_2,?,T_m$，其中每個集合本身又是一棵樹，并且稱為根的子樹。

樹的特性

樹作為邏輯結構，同時也是一種分層結構，具有以下兩個特點：

1. 樹的根結點沒有前驅，除根結點外的所有結點有且只有一個前驅。
2. 樹中所有結點都可以有零個或多個后繼。

樹適用于表示具有層次結構的數據。樹中的某個結點（除根結點外）最多只和上一層的一個結點（其父結點）有直接關系，根結點沒有直接上層結點，因此在 $n$ 個結點的樹中有 $n?1$ 條邊。而樹中每個結點與其下一層的零個或多個結點（其孩子結點）都有直接關系。

基本術語

樹的基本術語和概念

祖先、子孫、雙親、孩子、兄弟和堂兄弟

• 祖先：從根結點到某一結點的唯一路徑上的所有其他結點。
  • 結點$K$的祖先是從根$A$到$K$的唯一路徑上的所有其他結點。
• 子孫：某一結點的子樹中所有結點。
  • 如結點$B$是$K$的祖先，而$K$是$B$的子孫，結點$B$的子孫包括$E,F,K,L$。
• 雙親：某一結點的直接前驅，即指向該結點的結點。
• 孩子：某一結點的直接后繼，即該結點指向的結點。
  • 路徑上最接近$K$的結點$E$稱為$K$的雙親，$K$為$E$的孩子。
• 兄弟：有相同雙親的結點。
• 堂兄弟：在同一層的結點互為堂兄弟。
  • 有相同雙親的結點稱為兄弟（如$K$和$L$）。
  • 雙親在同一層的結點互為堂兄弟（如$G$與$E$、$F$、$H$、$I$、$J$）。
• 根$A$是樹中唯一沒有雙親的結點。

結點的層次、度、深度和高度

• 層次：從樹根開始定義，根結點為第1層，它的孩子為第2層，以此類推。
• 結點的度：一個結點的孩子個數稱為該結點的度。
  • 如結點$B$的度為2，結點$D$的度為3。
• 深度：結點所在的層次。
• 高度：以該結點為根的子樹的高度。

樹的度和高度

• 樹的度：樹中結點的最大度數稱為樹的度。
  • 上圖中樹的度為3。
• 樹的高度：樹的高度（或深度）是樹中結點的最大層數。
  • 上圖中樹的高度為4。

分支結點和葉結點

• 分支結點：度大于0的結點稱為分支結點（也稱非終端結點）。
• 葉結點：度為0（沒有孩子結點）的結點稱為葉結點（也稱終端結點）。

有序樹和無序樹

• 有序樹：樹中結點的各子樹從左到右是有次序的，不能互換。
• 無序樹：樹中結點的各子樹從左到右沒有次序，可以互換。
  • 假設上圖為有序樹，若將子結點位置互換，則變成一棵不同的樹。

路徑和路徑長度

• 路徑：樹中兩個結點之間的路徑是由這兩個結點之間所經過的結點序列構成的。
  • 因為樹中的分支是有向的，即從雙親指向孩子，所以樹中的路徑是從上向下的，同一雙親的兩個孩子之間不存在路徑。
• 路徑長度：路徑上所經過的邊的個數。

森林的基本術語和概念

森林的定義

• 森林：是 $m(m\ge 0)$ 棵互不相交的樹的集合。

森林與樹的關系

• 森林的概念與樹的概念十分相近，因為只要把樹的根結點刪去就成了森林。反之，只要給 $m$ 棵獨立的樹加上一個結點，并把這 $m$ 棵樹作為該結點的子樹，則森林就變成了樹。

樹的性質

1. 樹的結點數 $n$ 等于所有結點的度數之和加1。

   • 結點的度數是指該結點的孩子數量，每個結點與其每個孩子都由唯一的邊相連，因此樹中所有結點的度數之和等于樹中的邊數之和。
   • 樹中的結點（除根外）都有唯一的雙親，因此結點數 $n$ 等于邊數之和加1，即所有結點的度數之和加1。

2. 度為 $m$ 的樹中第 $i$ 層上至多有 $m^{i?1}$ 個結點 ($i\ge 1$)。

   • 第1層至多有1個結點（根結點），第2層至多有 $m$ 個結點，第3層至多有 $m^2$ 個結點，以此類推。
   • 使用數學歸納法可推出第 $i$ 層至多有 $m^{i?1}$ 個結點。

3. 高度為 $h$ 的 $m$ 叉樹至多有 $\frac{m^h?1}{m?1}$ 個結點。

   • 當各層結點數達到最大時，樹中至多有 $1+m+m^2+?+m^{h?1}=\frac{m^h?1}{m?1}$ 個結點。

4. 度為 $m$、具有 $n$ 個結點的樹的最小高度 $h$ 為 $?{\log }_m(n(m?1)+1)?$。

   • 為使樹的高度最小，在前 $h?1$ 層中，每層的結點數都要達到最大，前 $h?1$ 層最多有 $\frac{(m^{h?1}?1)}{(m?1)}$ 個結點，前 $h$ 層最多有 $\frac{(m^h?1)}{(m?1)}$ 個結點。
   • 因此 $\frac{(m^{h?1}?1)}{(m?1)}<n\le \frac{(m^h?1)}{(m?1)}$，即 $h?1<{\log }_m(n(m?1)+1)\le h$，解得 $h_{\text{min}}=?{\log }_m(n(m?1)+1)?$。

5. 度為 $m$、具有 $n$ 個結點的樹的最大高度 $h$ 為 $n?m+1$。

   • 樹的度為 $m$，因此至少有一個結點有 $m$ 個孩子，它們處于同一層。
   • 為使樹的高度最大，其他層可僅有一個結點，因此最大高度（層數）為 $n?m+1$。
   • 由此，也可逆推出高度為 $h$、度為 $m$ 的樹至少有 $h+m?1$ 個結點。

總結

• 樹中的結點數等于所有結點的度數之和加1。
• 度為 $m$ 的樹中第 $i$ 層上至多有 $m^{i?1}$ 個結點。
• 高度為 $h$ 的 $m$ 叉樹至多有 $\frac{m^h?1}{m?1}$ 個結點。
• 具有 $n$ 個結點的 $m$ 叉樹的最小高度為 $?{\log }_m(n(m?1)+1)?$。

樹的存儲結構

概述

樹的存儲方式有多種，既可采用順序存儲結構，又可采用鏈式存儲結構，但無論采用何種存儲方式，都要求能唯一地反映樹中各結點之間的邏輯關系。這里介紹3種常用的存儲結構。

雙親表示法

• 定義：這種存儲結構采用一組連續空間來存儲每個結點，同時在每個結點中增設一個偽指針，指示其雙親結點在數組中的位置。
• 特點：根結點下標為0，其偽指針域為-1。雙親表示法利用了每個結點（根結點除外）只有唯一雙親的性質，可以很快得到每個結點的雙親結點，但求結點的孩子時則需要遍歷整個結構。
• 圖示：如下圖所示，展示了樹的雙親表示法及其指針圖示。

注意事項

• 順序存儲結構與鏈式存儲結構：樹的順序存儲結構中，數組下標代表結點的編號，下標中所存的內容指示了結點之間的關系。而在二叉樹的順序存儲結構中，數組下標既代表了結點的編號，又指示了二叉樹中各結點之間的關系。
• 存儲結構選擇：二叉樹屬于樹，因此二叉樹也可用樹的存儲結構來存儲，但樹卻不都能用二叉樹的存儲結構來存儲。

孩子表示法和孩子兄弟表示法

孩子表示法

• 定義：孩子表示法是將每個結點的孩子結點視為一個線性表，且以單鏈表作為存儲結構，則 $n$ 個結點就有 $n$ 個孩子鏈表（葉結點的孩子鏈表為空表）。
• 特點：$n$ 個頭指針又組成一個線性表，為便于查找，可采用順序存儲結構。
• 圖示：下圖的是樹的孩子表示法。

孩子兄弟表示法

• 定義：孩子兄弟表示法也稱二叉樹表示法，即以二叉鏈表作為樹的存儲結構。每個結點包括三部分內容：結點值、指向結點第一個孩子結點的指針，以及指向結點下一個兄弟結點的指針（沿此域可以找到結點的所有兄弟結點）。
• 圖示：下圖的是樹的孩子兄弟表示法。
• 優點：孩子兄弟表示法比較靈活，其最大的優點是可以方便地實現樹轉換為二叉樹的操作，易于查找結點的孩子等，但缺點是從當前結點查找其雙親結點比較麻煩。

存儲結構選擇

• 孩子表示法：尋找孩子的操作非常方便，而尋找雙親的操作則需要遍歷 $n$ 個結點中孩子鏈表指針域所指向的 $n$ 個孩子鏈表。
• 孩子兄弟表示法：若為每個結點增設一個 parent 域指向其父結點，則查找結點的父結點也很方便。

樹、森林與二叉樹的轉換

樹轉為二叉樹

轉換規則

樹轉換為二叉樹的規則是：每個結點的左指針指向它的第一個孩子，右指針指向它在樹中的相鄰右兄弟，這個規則又稱為“左孩子右兄弟”。由于根結點沒有兄弟，因此轉換得到的二叉樹沒有右子樹。

轉換方法

1. 在兄弟結點之間加一連線：將樹中每個結點的兄弟結點通過連線連接起來。
2. 保留第一個孩子的連線：對每個結點，只保留它與第一個孩子的連線，而與其他孩子的連線全部抹掉。
3. 旋轉樹結構：以樹根為軸心，順時針旋轉45°。

轉換性質

• 二叉樹和樹都可以用二叉鏈表作為存儲結構。
• 從物理結構上看，樹的孩子兄弟表示法與二叉樹的二叉鏈表表示法是相同的，因此可以用同一存儲結構的不同解釋將一棵樹轉換為二叉樹。

轉換示例

下圖展示了樹與二叉樹的對應關系，通過上述轉換規則和方法，可以將樹轉換為二叉樹。

森林轉為二叉樹

將森林轉換為二叉樹的規則與樹類似。先將森林中的每棵樹轉換為二叉樹，由于任意一棵樹對應的二叉樹的右子樹必空，森林中各棵樹的根也可視為兄弟關系，將第二棵樹對應的二叉樹當作第一棵二叉樹根的右子樹……以此類推，就可以將森林轉換為二叉樹。

轉換方法

1. 將森林中的每棵樹轉換成相應的二叉樹。
2. 每棵樹的根也可視為兄弟關系，在每棵樹的根之間加一根連線。
3. 以第一棵樹的根為軸心順時針旋轉45°。

二叉樹轉換為森林

二叉樹轉換為森林的規則：若二叉樹非空，則二叉樹的根及其左子樹為第一棵樹的二叉樹形式，所以將根的右鏈斷開。二叉樹根的右子樹又可視為一個由除第一棵樹外的森林轉換后的二叉樹，應用同樣的方法，直到最后只剩一棵沒有右子樹的二叉樹為止，最后將每棵二叉樹依次轉換成樹，就得到了原森林。

二叉樹轉換為樹或森林是唯一的。

樹和森林的遍歷

樹的遍歷

遍歷定義

樹的遍歷是指用某種方式訪問樹中的每個結點，且僅訪問一次。主要有兩種方式：

先根遍歷

• 若樹非空，先訪問根結點。
• 再依次遍歷根結點的每棵子樹，遍歷子樹時仍遵循先根后子樹的規則。
• 其遍歷序列與這棵樹相應二叉樹的先序序列相同。

后根遍歷

• 若樹非空，先依次遍歷根結點的每棵子樹，遍歷子樹時仍遵循先子樹后根的規則。
• 再訪問根結點。
• 其遍歷序列與這棵樹相應二叉樹的中序序列相同。

遍歷序列

• 下圖的樹的先根遍歷序列為 $ABEFCDG$，后根遍歷序列為 $EFBCGDA$。
• 另外，樹也有層次遍歷，與二叉樹的層次遍歷思想基本相同，即按層序依次訪問各結點。

森林的遍歷

先序遍歷森林

按照森林和樹相互遞歸的定義，可得到森林的兩種遍歷方法。先序遍歷森林的規則如下：

1. 訪問森林中第一棵樹的根結點。
2. 先序遍歷第一棵樹中根結點的子樹森林。
3. 先序遍歷除去第一棵樹之后剩余的樹構成的森林。

中序遍歷森林

中序遍歷森林的規則如下：

1. 中序遍歷森林中第一棵樹的根結點的子樹森林。
2. 訪問第一棵樹的根結點。
3. 中序遍歷除去第一棵樹之后剩余的樹構成的森林。
   下圖的森林的先序遍歷序列為 $ABCDEFGHIJ$，中序遍歷序列為 $BCDAFEHIG$。

森林與二叉樹遍歷方法的對應關系

當森林轉換成二叉樹時，其第一棵樹的子樹森林轉換成左子樹，剩余樹的森林轉換成右子樹，可知森林的先序和中序遍歷即為其對應二叉樹的先序和中序遍歷。

下表樹和森林的遍歷與二叉樹遍歷的對應關系

樹	森林	二叉樹
先根遍歷	先序遍歷	先序遍歷
后根遍歷	中序遍歷	中序遍歷

注意事項

部分教材也將森林的中序遍歷稱為后序遍歷，稱中序遍歷是相對其二叉樹而言的，稱后序遍歷是因為根確實是最后才訪問的，若遇到這兩種稱謂，則可理解為同一種遍歷方法。

四、參考資料

鮑魚科技課件

b站免費王道課后題講解:

網課全程班:

26王道考研書