1、每課一貼：一個人去買鸚鵡，看到一只鸚鵡前標：此鸚鵡會兩門語言，售價二百元。另一只鸚鵡前則標有：此鸚鵡會四門語言，售價四百元。該買哪只呢？兩只都毛色光鮮，非常靈活可愛。這人轉啊轉，拿不定主意。結果突然發現一只老掉了牙的鸚鵡，毛色暗淡散亂，標價八百元。這人趕緊將老板叫來：這只鸚鵡是不是會說八門語言？店主說：不。這人奇怪了：那為什么又老又丑，又沒有能力，會值這個數呢？店主回答：因為另外兩只鸚鵡叫這只鸚鵡老板。這故事告訴我們，真正的領導人，不一定自己能力有多強，只要懂信任，懂放權，懂珍惜，就能團結比自己更強的力量，從而提升自己的身價。相反許多能力非常強的人卻因為過于完美主義，事必躬親，什么人都不如自己

2、，最后只能做最好的攻關人員，銷售代表，成不了優秀的領導人。 數據結構課程的內容數據結構課程的內容第第6章章 樹和二叉樹（樹和二叉樹（ Tree & Binary Tree ）6.1 樹的基本知識樹的基本知識6.2 二叉樹二叉樹6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 樹和森林樹和森林6.5 赫夫曼樹及其應用赫夫曼樹及其應用特點：非線性結構，一個直接前驅，但可能有多個特點：非線性結構，一個直接前驅，但可能有多個直接后繼直接后繼1:n1:n）6.1 樹的基本知識樹的基本知識1. 樹的定義樹的定義2. 若干術語若干術語3. 邏輯結構邏輯結構4.存儲結構存儲結構5. 樹的運算

3、樹的運算1. 樹的定義樹的定義注注1：過去許多書籍中都定義樹為：過去許多書籍中都定義樹為n1，曾經有，曾經有“空樹不是空樹不是樹樹的說法，但現在樹的定義已修改。的說法，但現在樹的定義已修改。注注2：樹的定義具有遞歸性，即樹中還有樹。：樹的定義具有遞歸性，即樹中還有樹。由一個或多個由一個或多個(n0)(n0)結點組成的有限集合結點組成的有限集合T T，有，有且僅有一個結點稱為根且僅有一個結點稱為根rootroot），當），當n1n1時，其余的時，其余的結點分為結點分為m(m0)m(m0)個互不相交的有限集合個互不相交的有限集合T1,T2T1,T2，TmTm。每個集合本身又是棵樹，被稱作這個根的子

4、樹。每個集合本身又是棵樹，被稱作這個根的子樹 。2. 若干術語若干術語即上層的那個結點即上層的那個結點(直接前驅直接前驅) parent即下層結點的子樹即下層結點的子樹 (直接后繼直接后繼) child同一雙親下的同層結點孩子之間互稱兄弟同一雙親下的同層結點孩子之間互稱兄弟sibling即雙親位于同一層的結點但并非同一雙親即雙親位于同一層的結點但并非同一雙親cousin即從根到該結點所經分支的所有結點即從根到該結點所經分支的所有結點即該結點下層子樹中的任一結點即該結點下層子樹中的任一結點ABCGEIDHFJMLK 根根 葉子葉子 森林森林有序樹有序樹無序樹無序樹即根結點即根結點(沒有前驅沒有前

5、驅)即終端結點即終端結點(沒有后繼沒有后繼)指指m棵不相交的樹的集棵不相交的樹的集合合(例如刪除例如刪除A后的子樹個數后的子樹個數)雙親雙親孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孫子孫結點各子樹從左至右有序，不能互換左為第一）結點各子樹從左至右有序，不能互換左為第一）結點各子樹可互換位置。結點各子樹可互換位置。2. 若干術語續）若干術語續）即樹的數據元素即樹的數據元素結點掛接的子樹數結點掛接的子樹數有幾個直接后繼就是有幾個直接后繼就是幾度，亦稱幾度，亦稱“次數次數”）結點結點結點的度結點的度結點的層次結點的層次終端結點終端結點分支結點分支結點樹的度樹的度樹的深度樹的深度(或高度或高度)ABCG

6、EIDHFJMLK從根到該結點的層數根結點算第一層）從根到該結點的層數根結點算第一層）即度為即度為0的結點，即葉子的結點，即葉子除樹根以外的結點也稱為內部結點）除樹根以外的結點也稱為內部結點）所有結點度中的最大值所有結點度中的最大值Max各結點的度各結點的度）指所有結點中最大的層數指所有結點中最大的層數Max各結點的層次各結點的層次）問：右上圖中的結點數問：右上圖中的結點數 ；樹的度；樹的度 ；樹的深度；樹的深度13133 34 4樹的表示法有幾種：樹的表示法有幾種：圖形表示法圖形表示法嵌套集合表示法嵌套集合表示法廣義表表示法廣義表表示法目錄表示法目錄表示法左孩子右兄弟表示法左孩子右兄弟表示法

7、樹的抽象數據類型定義參見教材樹的抽象數據類型定義參見教材P118-119圖形表示法：圖形表示法：老師老師學生學生其他人員其他人員9999級級20002000級級 20192019級級20192019級級三峽大學電氣學院三峽大學電氣學院計算機系計算機系電子系電子系自控系自控系葉子葉子根根子樹子樹廣義表表示法廣義表表示法( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )根作為由子樹森林組成的表的名字寫在表的左邊根作為由子樹森林組成的表的名字寫在表的左邊ABCGEIDHFJMLK左孩子右兄弟表示法左孩子右兄弟表示法數據數據左孩子左孩

8、子 右兄弟ABCGEIDHFJMLK 樹的抽象數據類型定義樹的抽象數據類型定義ADT Tree數據對象數據對象D:數據關系數據關系R:基本操作基本操作 P：ADT Tree若若D為空集，則稱為空樹；為空集，則稱為空樹；/允許允許n=0若若D中僅含一個數據元素，則中僅含一個數據元素，則R為空集；為空集；其他情況下的其他情況下的R存在二元關系：存在二元關系： root 唯一唯一 /關于根的說明關于根的說明 DjDk= /關于子樹不相交的說明關于子樹不相交的說明 /關于數據元素的說明關于數據元素的說明D是具有相同特性的數據元素的集合。是具有相同特性的數據元素的集合。/至少有至少有15個個3. 樹的邏

9、輯結構樹的邏輯結構 ( (特點特點) )： 一對多一對多1:n1:n），有多個直接后繼如家譜），有多個直接后繼如家譜樹、目錄樹等等），但只有一個根結點，樹、目錄樹等等），但只有一個根結點，且子樹之間互不相交。且子樹之間互不相交。 4. 樹的存儲結構樹的存儲結構 討論討論1：樹是非線性結構，該怎樣存儲？：樹是非線性結構，該怎樣存儲？仍然有順序存儲、鏈式存儲等方式。仍然有順序存儲、鏈式存儲等方式。 討論討論3：樹的鏈式存儲方案應該怎樣制定？：樹的鏈式存儲方案應該怎樣制定？可規定為：從上至下、從左至右將樹的結點依次存入內存。可規定為：從上至下、從左至右將樹的結點依次存入內存。重大缺陷：復原困難不能唯

10、一復原就沒有實用價值）。重大缺陷：復原困難不能唯一復原就沒有實用價值）。討論討論2：樹的順序存儲方案應該怎樣制定？：樹的順序存儲方案應該怎樣制定？可用多重鏈表：一個前趨指針，可用多重鏈表：一個前趨指針，n n個后繼指針。個后繼指針。細節問題：樹中結點的結構類型樣式該如何設計？細節問題：樹中結點的結構類型樣式該如何設計？ 即應該設計成即應該設計成“等長等長還是還是“不等長不等長”？缺點：等長結構太浪費每個結點的度不一定相同）；缺點：等長結構太浪費每個結點的度不一定相同）； 不等長結構太復雜要定義好多種結構類型）。不等長結構太復雜要定義好多種結構類型）。解決思路：先研究最簡單、最有規律的樹，然后設

11、法把解決思路：先研究最簡單、最有規律的樹，然后設法把一般的樹轉化為這種簡單的樹。一般的樹轉化為這種簡單的樹。討論討論4：計算機如何實現各種不同進制的運算？：計算機如何實現各種不同進制的運算？ 實現思路：先研究最簡單、最有規律的二進制運算規律，實現思路：先研究最簡單、最有規律的二進制運算規律，然后設法把各種不同進制的運算轉化二進制運算。然后設法把各種不同進制的運算轉化二進制運算。討論討論5：樹的存儲可否借鑒這種思路呢？：樹的存儲可否借鑒這種思路呢？5. 樹的運算樹的運算 要明確：要明確：1. 普通樹即多叉樹若不轉化為二叉樹，則運普通樹即多叉樹若不轉化為二叉樹，則運算很難實現。算很難實現。2. 二

12、叉樹的運算仍然是插入、刪除、修改、查找、二叉樹的運算仍然是插入、刪除、修改、查找、排序等，但這些操作必須建立在對樹結點能夠排序等，但這些操作必須建立在對樹結點能夠“遍歷遍歷的基礎上！的基礎上！ （遍歷（遍歷指每個結點都被訪問且僅訪問一次，指每個結點都被訪問且僅訪問一次，不遺漏不重復）。不遺漏不重復）。本章重點：二叉樹的表示和實現本章重點：二叉樹的表示和實現6.2 6.2 二叉樹二叉樹為何要重點研究每結點最多只有兩個為何要重點研究每結點最多只有兩個 “ “叉叉” ” 的樹？的樹？二叉樹的結構最簡單，規律性最強；二叉樹的結構最簡單，規律性最強；可以證明，所有樹都能轉為唯一對應的二叉樹，不失一般性。

13、可以證明，所有樹都能轉為唯一對應的二叉樹，不失一般性。1. 二叉樹的定義二叉樹的定義2. 二叉樹的性質二叉樹的性質3. 二叉樹的存儲結構二叉樹的存儲結構（二叉樹的運算見（二叉樹的運算見6.3節）節）定義：是定義：是nn0個結點的有限集合，由一個根結點以及兩個結點的有限集合，由一個根結點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成 。邏輯結構：邏輯結構： 一對二一對二1：2） 基本特征基本特征: 每個結點最多只有兩棵子樹不存在度大于每個結點最多只有兩棵子樹不存在度大于2的結點）；的結點）； 左子樹和右子樹次序不能顛倒有序樹）。左子樹和右子

14、樹次序不能顛倒有序樹）。基本形態：基本形態： 5種種/2種種討論討論1 1：第：第i i層的結點數至多是多少？層的結點數至多是多少？ 性質性質1: 1: 在二叉樹的第在二叉樹的第i i層上至多有層上至多有2i-12i-1個結點個結點i0i0）。）。性質性質2: 2: 深度為深度為k k的二叉樹至多有的二叉樹至多有2k-12k-1個結點個結點k0k0）。）。2i-12i-1個個提問：第提問：第i i層上至少有層上至少有 個結點？個結點？1 1討論討論2 2：深度為：深度為k k的二叉樹，至多有多少個結點？的二叉樹，至多有多少個結點？ 2k-12k-1提問：深度為提問：深度為k k時至少有時至少有

15、 個結點？個結點？k k討論討論3 3：二叉樹的葉子數和度為：二叉樹的葉子數和度為2 2的結點數之間有關系嗎？的結點數之間有關系嗎？性質性質3: 3: 對于任何一棵二叉樹，若對于任何一棵二叉樹，若2 2度的結點數有度的結點數有n2n2個，個，則葉子數則葉子數n0n0必定為必定為n2n21 1 （即（即n0=n2+1n0=n2+1）ABCGEIDHFJ滿二叉樹：一棵深度為滿二叉樹：一棵深度為k k 且有且有2k -12k -1個結點的二叉樹。個結點的二叉樹。 （特點：每層都（特點：每層都“充溢了結點）充溢了結點）完全二叉樹：深度為完全二叉樹：深度為k k 的，有的，有n n個結點個結點的二叉樹，

16、當且僅當其每一個結點都與的二叉樹，當且僅當其每一個結點都與深度為深度為k k 的滿二叉樹中編號從的滿二叉樹中編號從1 1至至n n的結的結點一一對應。點一一對應。AOBCGEKDJFIHNML深度為深度為4 4的滿二叉樹的滿二叉樹深度為深度為4 4的完全二叉樹的完全二叉樹ABCGEIDHFJ為何要研究這兩種特殊形式？為何要研究這兩種特殊形式？因為它們在順序存儲方式下可以復原！因為它們在順序存儲方式下可以復原！ 完全二叉樹的特點就是，只有最后一層完全二叉樹的特點就是，只有最后一層葉子不滿，且全部集中在左邊。葉子不滿，且全部集中在左邊。 這其實是順序二叉樹的含義。這其實是順序二叉樹的含義。對于兩種

17、特殊形式的二叉樹滿二叉樹和完全二叉樹），對于兩種特殊形式的二叉樹滿二叉樹和完全二叉樹），還特別具備以下還特別具備以下2 2個性質：個性質：性質性質4: 4: 具有具有n n個結點的完全二叉樹的深度必為個結點的完全二叉樹的深度必為log2nlog2n1 1證明：根據性質證明：根據性質2 2，深度為，深度為k k的二叉樹最多只有的二叉樹最多只有2k-12k-1個結點，且個結點，且完全二叉樹的定義是與同深度的滿二叉樹前面編號相同，即它完全二叉樹的定義是與同深度的滿二叉樹前面編號相同，即它的總結點數的總結點數n n位于位于k k層和層和k-1k-1層滿二叉樹容量之間，即：層滿二叉樹容量之間，即：2k-

18、1-1n2k-1 2k-1-1n2k-1 或或2k-1n2k2k-1n2k，三邊同時取對數，于是有：三邊同時取對數，于是有：k-1log2nk k-1log2nk 因為因為k k是整數，所以是整數，所以k= k= log2nlog2n+1+1性質性質5: 5: 對完全二叉樹，若從上至下、從左至右編號，對完全二叉樹，若從上至下、從左至右編號，則編號為則編號為i i 的結點，其左孩子編號必為的結點，其左孩子編號必為2i2i，其右孩，其右孩子編號必為子編號必為2i2i1 1；其雙親的編號必為；其雙親的編號必為i/2i/2i i1 1 時時為根為根, ,除外）。除外）。 證明：對于第證明：對于第k k

19、層的中編號為層的中編號為i i的元素，的元素，在第在第k k層中前面有層中前面有x xi-2k-1i-2k-1個元素個元素在第在第k k層中后面有層中后面有y y2k-12k-11 1x x個元素，個元素，則其左孩子編號是：則其左孩子編號是：i+y+2x+1=i+2k-1-1-x+2x+1=i+2k-1+x=i+2k-1+i-2k-1=2ii+y+2x+1=i+2k-1-1-x+2x+1=i+2k-1+x=i+2k-1+i-2k-1=2i則其右孩子編號是：則其右孩子編號是：i+y+2x+2=2ii+y+2x+2=2i1 1對 于 左 右 孩 子 ， 其 雙 親 節 點 編 號 必 然 為對 于

20、 左 右 孩 子 ， 其 雙 親 節 點 編 號 必 然 為 i / 2 i / 2 (2i+1)/2=2i/2=i(2i+1)/2=2i/2=i3. 3. 深度為深度為9 9的二叉樹中至少有的二叉樹中至少有 個結點。個結點。 ) )9 9 ) )8 8 ) ) ) )9 91 12.2.深度為深度為k k 的二叉樹的結點總數，最多為的二叉樹的結點總數，最多為 個。個。 ) )k-1 k-1 ) log2k ) log2k ) ) k k ) )k k課堂練習：課堂練習：1. 1. 樹中各結點的度的最大值稱為樹的樹中各結點的度的最大值稱為樹的 。 ) ) 高度高度 ) ) 層次層次 ) ) 深

21、度深度 ) ) 度度課堂討論：課堂討論： 二叉樹是不是樹的特殊情況？二叉樹是不是樹的特殊情況？答：不是！雖然二叉樹也屬于一種樹結構，但它是另外單獨定答：不是！雖然二叉樹也屬于一種樹結構，但它是另外單獨定義的一種樹，并非一般樹的特例。它的子樹有順序規定，分為義的一種樹，并非一般樹的特例。它的子樹有順序規定，分為左子樹和右子樹。不能隨意顛倒。左子樹和右子樹。不能隨意顛倒。：滿二叉樹和完全二叉樹有什么區別？：滿二叉樹和完全二叉樹有什么區別？答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前n-n-1 1層是滿的，但最底層卻允許在右邊缺少連續若干個

22、結點。滿層是滿的，但最底層卻允許在右邊缺少連續若干個結點。滿二叉樹是完全二叉樹的一個特例。二叉樹是完全二叉樹的一個特例。課堂討論：課堂討論：Q2: Q2: 設一棵完全二叉樹具有設一棵完全二叉樹具有10001000個結點，則它有個結點，則它有 個葉個葉子結點，有子結點，有 個度為個度為2 2的結點，有的結點，有 個結點只有非空左子個結點只有非空左子樹，有樹，有 個結點只有非空右子樹。個結點只有非空右子樹。4894894884881 10 0Q1Q1：為什么要研究滿二叉樹和完全二叉樹這兩種特殊形式？：為什么要研究滿二叉樹和完全二叉樹這兩種特殊形式？A1A1：因為只有這兩種形式可以實現順序存儲！：因為只有這兩種形式可以實現順序存儲！由于最后一層葉子數為由于最后一層葉子數為489489個，是奇數，說明有個，是奇數，說明有1 1個結點只有非空個結點只有非空左子樹；而完全二叉樹中不可能出現非空右子樹左子樹；而完全二叉樹中不可能出現非空右子樹(0(0個個) )。A2A2：易求出總層數和末層葉子數。總層數：易求出總層數和末層葉子數。總層數k=k=log2nlog2n1 1 =10;=10;且前且前9 9層總結點數為層總