第5章-樹和二叉樹課件

1、樹的邏輯結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)樹、森林與二叉樹的轉(zhuǎn)換哈夫曼樹第 5 章 樹和二叉樹本章的主要內(nèi)容是樹的定義樹：n（n0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n0時(shí)，稱為空樹；任意一棵非空樹滿足以下條件： 有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)； 當(dāng)n1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m（m0）個(gè)互不相交的有限集合T1,T2, ,Tm，其中每個(gè)集合又是一棵樹，并稱為這個(gè)根結(jié)點(diǎn)的子樹。5.1 樹的邏輯結(jié)構(gòu)樹的定義是采用遞歸方法(a) 一棵樹結(jié)構(gòu) (b)一個(gè)非樹結(jié)構(gòu) (c)一個(gè)非樹結(jié)構(gòu) 5.1 樹的邏輯結(jié)構(gòu)樹的定義ACBGFEDHIACBGFDACBGFDE樹的應(yīng)用舉例文件結(jié)構(gòu)5.1 樹的邏

2、輯結(jié)構(gòu)My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic樹的基本術(shù)語結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)。樹的度：樹中各結(jié)點(diǎn)度的最大值。5.1 樹的邏輯結(jié)構(gòu)CGBDEFKLHMIJA5.1 樹的邏輯結(jié)構(gòu)葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。CGBDEFKLHMIJA樹的基本術(shù)語孩子、雙親：樹中某結(jié)點(diǎn)子樹的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)；兄弟：具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。 5.1 樹的邏輯結(jié)構(gòu)CGBDEFKLHMIJA樹的基本術(shù)語路徑：如果樹的結(jié)點(diǎn)序列n1, n

3、2, , nk有如下關(guān)系：結(jié)點(diǎn)ni是ni+1的雙親（1=ik），則把n1, n2, , nk稱為一條由n1至nk的路徑；路徑上經(jīng)過的邊的個(gè)數(shù)稱為路徑長度。 CGBDEFKLHMIJA5.1 樹的邏輯結(jié)構(gòu)樹的基本術(shù)語祖先、子孫：在樹中，如果有一條路徑從結(jié)點(diǎn)x到結(jié)點(diǎn)y，那么x就稱為y的祖先，而y稱為x的子孫。5.1 樹的邏輯結(jié)構(gòu)CGBDEFKLHMIJA樹的基本術(shù)語結(jié)點(diǎn)所在層數(shù)：根結(jié)點(diǎn)的層數(shù)為1；對(duì)其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第k層，則其孩子結(jié)點(diǎn)在第k+1層。樹的深度：樹中所有結(jié)點(diǎn)的最大層數(shù)，也稱高度。1層2層4層3層高度4CGBDEFKLHMIJC5.1 樹的邏輯結(jié)構(gòu)樹的基本術(shù)語CBDEFKLHJA

4、71234568910層序編號(hào)：將樹中結(jié)點(diǎn)按照從上層到下層、同層從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù)。5.1 樹的邏輯結(jié)構(gòu)樹的基本術(shù)語有序樹、無序樹：如果一棵樹中結(jié)點(diǎn)的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹 5.1 樹的邏輯結(jié)構(gòu)樹的基本術(shù)語ACBGFEDACBGFEDCBDEFKLHJ森林：m (m0)棵互不相交的樹的集合。 5.1 樹的邏輯結(jié)構(gòu)樹的基本術(shù)語A同構(gòu)：對(duì)兩棵樹，若通過對(duì)結(jié)點(diǎn)適當(dāng)?shù)刂孛涂梢允惯@兩棵樹完全相等（結(jié)點(diǎn)對(duì)應(yīng)相等，結(jié)點(diǎn)對(duì)應(yīng)關(guān)系也相等），則稱這兩棵樹同構(gòu)。5.1 樹的邏輯結(jié)構(gòu)樹的基本術(shù)語ACBGFEDDA

5、ECFBG樹結(jié)構(gòu)和線性結(jié)構(gòu)的比較線性結(jié)構(gòu)樹結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素根結(jié)點(diǎn)（只有一個(gè)）無前驅(qū)無雙親最后一個(gè)數(shù)據(jù)元素葉子結(jié)點(diǎn)(可以有多個(gè))無后繼無孩子其它數(shù)據(jù)元素其它結(jié)點(diǎn)一個(gè)前驅(qū),一個(gè)后繼一個(gè)雙親,多個(gè)孩子一對(duì)一 一對(duì)多5.1 樹的邏輯結(jié)構(gòu)樹的抽象數(shù)據(jù)類型定義ADT TreeData 樹是由一個(gè)根結(jié)點(diǎn)和若干棵子樹構(gòu)成， 樹中結(jié)點(diǎn)具有相同數(shù)據(jù)類型及層次關(guān)系Operation InitTree 前置條件：樹不存在 輸入：無 功能：初始化一棵樹 輸出：無 后置條件：構(gòu)造一個(gè)空樹5.1 樹的邏輯結(jié)構(gòu) DestroyTree 前置條件：樹已存在 輸入：無 功能：銷毀一棵樹 輸出：無 后置條件：釋放該樹占用的存儲(chǔ)空

6、間 Root 前置條件：樹已存在 輸入：無 功能：求樹的根結(jié)點(diǎn) 輸出：樹的根結(jié)點(diǎn)的信息 后置條件：樹保持不變 樹的抽象數(shù)據(jù)類型定義5.1 樹的邏輯結(jié)構(gòu)Parent 前置條件：樹已存在 輸入：結(jié)點(diǎn)x 功能：求結(jié)點(diǎn)x的雙親 輸出：結(jié)點(diǎn)x的雙親的信息 后置條件：樹保持不變 Depth 前置條件：樹已存在 輸入：無 功能：求樹的深度 輸出：樹的深度 后置條件：樹保持不變 樹的抽象數(shù)據(jù)類型定義5.1 樹的邏輯結(jié)構(gòu) PreOrder 前置條件：樹已存在 輸入：無 功能：前序遍歷樹 輸出：樹的前序遍歷序列 后置條件：樹保持不變 PostOrder 前置條件：樹已存在 輸入：無 功能：后序遍歷樹 輸出：樹的后

7、序遍歷序列 后置條件：樹保持不變endADT樹的抽象數(shù)據(jù)類型定義5.1 樹的邏輯結(jié)構(gòu)樹的遍歷操作 樹的遍歷：從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問樹中所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。 如何理解訪問?抽象操作，可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理，這里簡化為輸出結(jié)點(diǎn)的數(shù)據(jù)。如何理解次序?樹通常有前序（根）遍歷、后序（根）遍歷和層序（次）遍歷三種方式。5.1 樹的邏輯結(jié)構(gòu)樹結(jié)構(gòu)（非線性結(jié)構(gòu)）線性結(jié)構(gòu)。遍歷的實(shí)質(zhì)?前序遍歷 樹的前序遍歷操作定義為：若樹為空，則空操作返回；否則 訪問根結(jié)點(diǎn)； 按照從左到右的順序前序遍歷根結(jié)點(diǎn)的每一棵子樹。 5.1 樹的邏輯結(jié)構(gòu)前序遍歷序列：A B D E H I F C

8、 GACBGFEDHI后序遍歷 樹的后序遍歷操作定義為：若樹為空，則空操作返回；否則 按照從左到右的順序后序遍歷根結(jié)點(diǎn)的每一棵子樹； 訪問根結(jié)點(diǎn)。 5.1 樹的邏輯結(jié)構(gòu)后序遍歷序列：D H I E F B G C AACBGFEDHI層序遍歷 樹的層序遍歷操作定義為：從樹的第一層（即根結(jié)點(diǎn)）開始，自上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。 5.1 樹的邏輯結(jié)構(gòu)層序遍歷序列：A B C D E F G H IACBGFEDHI5.2 樹的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)樹的存儲(chǔ)結(jié)構(gòu)，關(guān)鍵是什么?什么是存儲(chǔ)結(jié)構(gòu)?樹中結(jié)點(diǎn)之間的邏輯關(guān)系是什么?思考問題的出發(fā)點(diǎn)：如何表示結(jié)點(diǎn)的雙親和孩子如何表示樹中結(jié)

9、點(diǎn)之間的邏輯關(guān)系。數(shù)據(jù)元素以及數(shù)據(jù)元素之間的邏輯關(guān)系在存儲(chǔ)器中的表示。雙親表示法基本思想：用一維數(shù)組來存儲(chǔ)樹的各個(gè)結(jié)點(diǎn)（一般按層序存儲(chǔ)），數(shù)組中的一個(gè)元素對(duì)應(yīng)樹中的一個(gè)結(jié)點(diǎn)，包括結(jié)點(diǎn)的數(shù)據(jù)信息以及該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)。 5.2 樹的存儲(chǔ)結(jié)構(gòu) data parentdata：存儲(chǔ)樹中結(jié)點(diǎn)的數(shù)據(jù)信息parent：存儲(chǔ)該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)template struct PNode T data; /數(shù)據(jù)域 int parent; /指針域，雙親在數(shù)組中的下標(biāo) ; data parent5.2 樹的存儲(chǔ)結(jié)構(gòu)樹的雙親表示法實(shí)質(zhì)上是一個(gè)靜態(tài)鏈表。雙親表示法下標(biāo) data parent01234

10、5678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 5.2 樹的存儲(chǔ)結(jié)構(gòu)如何查找雙親結(jié)點(diǎn)？時(shí)間性能？雙親表示法ACBHFEDGI5.2 樹的存儲(chǔ)結(jié)構(gòu)雙親表示法ACBHFEDGI如何查找孩子結(jié)點(diǎn)？時(shí)間性能？下標(biāo) data parentfirstchild 1 3 6 -1 8 -1-1-1-1012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 下標(biāo) data parent rightsib-1 2-1 4 5 -17-1-15.2 樹的存儲(chǔ)結(jié)構(gòu)雙親表示法012345678 A -1 B 0 C 0 D 1 E 1 F 1

11、G 2 H 2 I 4 ACBHFEDGI如何查找兄弟結(jié)點(diǎn)？時(shí)間性能？鏈表中的每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和多個(gè)指針域，每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn)。 如何確定鏈表中的結(jié)點(diǎn)結(jié)構(gòu)？5.2 樹的存儲(chǔ)結(jié)構(gòu)孩子鏈表表示法方案一：指針域的個(gè)數(shù)等于樹的度data child1 child2 childd其中：data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息； child1childd：指針域，指向該結(jié)點(diǎn)的孩子。 5.2 樹的存儲(chǔ)結(jié)構(gòu)缺點(diǎn)：浪費(fèi)空間ACBHFEDGIABCDEFGHI鏈表中的每個(gè)結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)域和多個(gè)指針域，每個(gè)指針域指向該結(jié)點(diǎn)的一個(gè)孩子結(jié)點(diǎn)。 如何確定鏈表中的結(jié)點(diǎn)結(jié)構(gòu)？5.2 樹的存儲(chǔ)結(jié)構(gòu)孩子鏈表

12、表示法方案二： 指針域的個(gè)數(shù)等于該結(jié)點(diǎn)的度 data degree child1 child2 childd其中：data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息； degree：度域，存放該結(jié)點(diǎn)的度； child1childd：指針域，指向該結(jié)點(diǎn)的孩子。 5.2 樹的存儲(chǔ)結(jié)構(gòu)缺點(diǎn)：結(jié)點(diǎn)結(jié)構(gòu)不一致ACBHFEDGIA 2B 3C 2E 1I 0G 0H 0F 0D 0孩子鏈表表示法基本思想：把每個(gè)結(jié)點(diǎn)的孩子排列起來，看成是一個(gè)線性表，且以單鏈表存儲(chǔ)，則n個(gè)結(jié)點(diǎn)共有 n 個(gè)孩子鏈表。這 n 個(gè)單鏈表共有 n 個(gè)頭指針，這 n 個(gè)頭指針又組成了一個(gè)線性表，為了便于進(jìn)行查找采用順序存儲(chǔ)。最后，將存放 n 個(gè)頭

13、指針的數(shù)組和存放n個(gè)結(jié)點(diǎn)的數(shù)組結(jié)合起來，構(gòu)成孩子鏈表的表頭數(shù)組。 5.2 樹的存儲(chǔ)結(jié)構(gòu)如何確定鏈表中的結(jié)點(diǎn)結(jié)構(gòu)？將結(jié)點(diǎn)的所有孩子放在一起，構(gòu)成線性表。child next孩子結(jié)點(diǎn)struct CTNode int child; CTNode *next;5.2 樹的存儲(chǔ)結(jié)構(gòu)template struct CBNode T data; CTNode *firstchild; ;孩子鏈表表示法data firstchild表頭結(jié)點(diǎn)ACBHFEDGI012345678下標(biāo) data firstchild A B C D E F G H I 5.2 樹的存儲(chǔ)結(jié)構(gòu)如何查找孩子結(jié)點(diǎn)？時(shí)間性能？12 345

14、 7 68 ACBHFEDGI012345678下標(biāo) data firstchild A B C D E F G H I 5.2 樹的存儲(chǔ)結(jié)構(gòu)12 345 7 68 如何查找雙親結(jié)點(diǎn)？時(shí)間性能？雙親孩子表示法5.2 樹的存儲(chǔ)結(jié)構(gòu)012345678 A -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 data parent firstchild12 345 7 68 ACBHFEDGI孩子兄弟表示法5.2 樹的存儲(chǔ)結(jié)構(gòu)ACBHFEDGI某結(jié)點(diǎn)的第一個(gè)孩子是惟一的某結(jié)點(diǎn)的右兄弟是惟一的設(shè)置兩個(gè)分別指向該結(jié)點(diǎn)的第一個(gè)孩子和右兄弟的指針 template struct TNode

15、 T data; TNode *firstchild, *rightsib;5.2 樹的存儲(chǔ)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)firstchild data rightsibdata：數(shù)據(jù)域，存儲(chǔ)該結(jié)點(diǎn)的數(shù)據(jù)信息；firstchild：指針域，指向該結(jié)點(diǎn)第一個(gè)孩子；rightsib：指針域，指向該結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)。 孩子兄弟表示法5.2 樹的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法ACBHFEDGI A B C D E F G H I如何查找兄弟結(jié)點(diǎn)？時(shí)間性能？5.2 樹的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法ACBHFEDGI A B C D E F G H I如何查找孩子結(jié)點(diǎn)？時(shí)間性能？二叉樹的定義 二叉樹是n（n0）個(gè)結(jié)點(diǎn)的有限集合，該集合或

16、者為空集（稱為空二叉樹），或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。5.3 二叉樹的邏輯結(jié)構(gòu)問題轉(zhuǎn)化：將樹轉(zhuǎn)換為二叉樹，從而利用二叉樹解決樹的有關(guān)問題。研究二叉樹的意義？二叉樹的特點(diǎn)： 每個(gè)結(jié)點(diǎn)最多有兩棵子樹； 二叉樹是有序的，其次序不能任意顛倒。 5.3 二叉樹的邏輯結(jié)構(gòu)注意：二叉樹和樹是兩種樹結(jié)構(gòu)。ABCDEFGABAB二叉樹的基本形態(tài)空二叉樹只有一個(gè)根結(jié)點(diǎn)左子樹根結(jié)點(diǎn)只有左子樹右子樹根結(jié)點(diǎn)只有右子樹左子樹右子樹根結(jié)點(diǎn)同時(shí)有左右子樹5.3 二叉樹的邏輯結(jié)構(gòu)5.3 二叉樹的邏輯結(jié)構(gòu)具有3個(gè)結(jié)點(diǎn)的樹和具有3個(gè)結(jié)點(diǎn)的二叉樹的形態(tài)二叉樹和樹是兩種樹結(jié)構(gòu)。特殊的二

17、叉樹斜樹1 .所有結(jié)點(diǎn)都只有左子樹的二叉樹稱為左斜樹；2 .所有結(jié)點(diǎn)都只有右子樹的二叉樹稱為右斜樹；3.左斜樹和右斜樹統(tǒng)稱為斜樹。1. 在斜樹中，每一層只有一個(gè)結(jié)點(diǎn)；2.斜樹的結(jié)點(diǎn)個(gè)數(shù)與其深度相同。 5.3 二叉樹的邏輯結(jié)構(gòu)斜樹的特點(diǎn)：ABCABC滿二叉樹在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上。滿二叉樹的特點(diǎn)：葉子只能出現(xiàn)在最下一層；只有度為0和度為2的結(jié)點(diǎn)。5.3 二叉樹的邏輯結(jié)構(gòu)特殊的二叉樹CDEFGHIJKLMNO1112131415滿二叉樹5.3 二叉樹的邏輯結(jié)構(gòu)不是滿二叉樹，雖然所有分支結(jié)點(diǎn)都有左右子樹，但葉子不在同一

18、層上。滿二叉樹在同樣深度的二叉樹中結(jié)點(diǎn)個(gè)數(shù)最多滿二叉樹在同樣深度的二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)最多A1523467BCDEFGLM89特殊的二叉樹完全二叉樹對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹按層序編號(hào)，如果編號(hào)為i（1in）的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為i的結(jié)點(diǎn)在二叉樹中的位置完全相同。5.3 二叉樹的邏輯結(jié)構(gòu)特殊的二叉樹CDEFGHIJKLMNO1112131415CDEFGHIJ在滿二叉樹中，從最后一個(gè)結(jié)點(diǎn)開始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹。5.3 二叉樹的邏輯結(jié)構(gòu)A1523467910BCDEFGHIJK11L12M13N14O158A1

19、5234678910BCDEFGHIJ不是完全二叉樹，結(jié)點(diǎn)10與滿二叉樹中的結(jié)點(diǎn)10不是同一個(gè)結(jié)點(diǎn)特殊的二叉樹1. 葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點(diǎn)都集中在二叉樹的左部；2. 完全二叉樹中如果有度為1的結(jié)點(diǎn)，只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子。 3. 深度為k的完全二叉樹在k-1層上一定是滿二叉樹。完全二叉樹的特點(diǎn)5.3 二叉樹的邏輯結(jié)構(gòu)特殊的二叉樹CDEFGHIJ二叉樹的基本性質(zhì) 性質(zhì)5-1 二叉樹的第i層上最多有2i-1個(gè)結(jié)點(diǎn)（i1）。 證明：當(dāng)i=1時(shí)，第1層只有一個(gè)根結(jié)點(diǎn)，而 2i-1=20 =1，結(jié)論顯然成立。假定i=k（1ki）時(shí)結(jié)論成立，即第

20、k層上至多有2k-1個(gè)結(jié)點(diǎn)， 則 i=k+1時(shí)，因?yàn)榈趉+1層上的結(jié)點(diǎn)是第k層上結(jié)點(diǎn)的孩子，而二叉樹中每個(gè)結(jié)點(diǎn)最多有2個(gè)孩子，故在第k+1層上最大結(jié)點(diǎn)個(gè)數(shù)為第k層上的最大結(jié)點(diǎn)個(gè)數(shù)的二倍，即22k-12k。結(jié)論成立。5.3 二叉樹的邏輯結(jié)構(gòu)性質(zhì)5-2 一棵深度為k的二叉樹中，最多有2k-1個(gè)結(jié)點(diǎn)，最少有k個(gè)結(jié)點(diǎn)。 證明：由性質(zhì)1可知，深度為k的二叉樹中結(jié)點(diǎn)個(gè)數(shù)最多= =2k-1；每一層至少要有一個(gè)結(jié)點(diǎn)，因此深度為k的二叉樹，至少有k個(gè)結(jié)點(diǎn)。5.3 二叉樹的邏輯結(jié)構(gòu)深度為k且具有2k-1個(gè)結(jié)點(diǎn)的二叉樹一定是滿二叉樹，深度為k且具有k個(gè)結(jié)點(diǎn)的二叉樹不一定是斜樹。！二叉樹的基本性質(zhì) 性質(zhì)5-3 在一棵

21、二叉樹中，如果葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有: n0n21。 證明: 設(shè)n為二叉樹的結(jié)點(diǎn)總數(shù)，n1為二叉樹中度為1的結(jié)點(diǎn)數(shù)，則有： nn0n1n2 在二叉樹中，除了根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有唯一的一個(gè)分枝進(jìn)入，由于這些分枝是由度為1和度為2的結(jié)點(diǎn)射出的，一個(gè)度為1的結(jié)點(diǎn)射出一個(gè)分枝，一個(gè)度為2的結(jié)點(diǎn)射出兩個(gè)分枝，所以有： nn12n21因此可以得到：n0n21 。5.3 二叉樹的邏輯結(jié)構(gòu)二叉樹的基本性質(zhì) 5.3 二叉樹的邏輯結(jié)構(gòu)在有n個(gè)結(jié)點(diǎn)的滿二叉樹中，有多少個(gè)葉子結(jié)點(diǎn)？因?yàn)樵跐M二叉樹中沒有度為1的結(jié)點(diǎn)，只有度為0的葉子結(jié)點(diǎn)和度為2的分支結(jié)點(diǎn)，所以，n n0 + n2n0n2 + 1

22、 即葉子結(jié)點(diǎn)n0（n + 1）/2 二叉樹的基本性質(zhì) 性質(zhì)5-3 在一棵二叉樹中，如果葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有: n0n21。 性質(zhì)5-4 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n +1。 5.3 二叉樹的邏輯結(jié)構(gòu)證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立 2k-1 n 2k 2k-1-12k-12k-1第k-1層第k層最少結(jié)點(diǎn)數(shù)最多結(jié)點(diǎn)數(shù)完全二叉樹的基本性質(zhì) 5.3 二叉樹的邏輯結(jié)構(gòu)log2n + 1log2nlog2nlog2n+1k所在區(qū)間證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質(zhì)2，有下式

23、成立 2k-1 n 2k完全二叉樹的基本性質(zhì) 性質(zhì)5-4 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n +1。 對(duì)不等式取對(duì)數(shù)，有： k-1log2nk即： log2nklog2n+1由于k是整數(shù)，故必有k log2n +1。 性質(zhì)5-5 對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中從1開始按層序編號(hào)，則對(duì)于任意的序號(hào)為i（1in）的結(jié)點(diǎn)（簡稱為結(jié)點(diǎn)i），有： （1）如果i1，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)的序號(hào)為 i/2；如果i1，則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。 (2)如果2in，則結(jié)點(diǎn)i的左孩子的序號(hào)為2i；如果2in，則結(jié)點(diǎn)i無左孩子。 (3)如果2i1n，則結(jié)點(diǎn)i的右孩子的序號(hào)為2i1；如果2i1n，則結(jié)點(diǎn)

24、i無右孩子。 5.3 二叉樹的邏輯結(jié)構(gòu)完全二叉樹的基本性質(zhì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中從1開始按層序編號(hào)，則 結(jié)點(diǎn)i的雙親結(jié)點(diǎn)為 i/2； 結(jié)點(diǎn)i的左孩子為2i； 結(jié)點(diǎn)i的右孩子為2i1。 5.3 二叉樹的邏輯結(jié)構(gòu)性質(zhì)5表明，在完全二叉樹中，結(jié)點(diǎn)的層序編號(hào)反映了結(jié)點(diǎn)之間的邏輯關(guān)系。完全二叉樹的基本性質(zhì) 二叉樹的抽象數(shù)據(jù)類型定義ADT BiTreeData 由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左右子樹構(gòu)成， 結(jié)點(diǎn)具有相同數(shù)據(jù)類型及層次關(guān)系Operation InitBiTree 前置條件：無 輸入：無 功能：初始化一棵二叉樹 輸出：無 后置條件：構(gòu)造一個(gè)空的二叉樹5.3 二叉

25、樹的邏輯結(jié)構(gòu) DestroyBiTree 前置條件：二叉樹已存在 輸入：無 功能：銷毀一棵二叉樹 輸出：無 后置條件：釋放二叉樹占用的存儲(chǔ)空間 InsertL 前置條件：二叉樹已存在 輸入：數(shù)據(jù)值x，指針parent 功能：將數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)插入到二叉樹中，作為結(jié)點(diǎn)parent的左孩子。如果結(jié)點(diǎn)parent原來有左孩子，則將結(jié)點(diǎn)parent原來的左孩子作為結(jié)點(diǎn)x的左孩子 輸出：無 后置條件：如果插入成功，得到一個(gè)新的二叉樹 二叉樹的抽象數(shù)據(jù)類型定義5.3 二叉樹的邏輯結(jié)構(gòu)DeleteL 前置條件：二叉樹已存在 輸入：指針parent 功能：在二叉樹中刪除結(jié)點(diǎn)parent的左子樹 輸出：無 后置

26、條件：如果刪除成功，得到一個(gè)新的二叉樹Search 前置條件：二叉樹已存在 輸入：數(shù)據(jù)值x 功能：在二叉樹中查找數(shù)據(jù)元素x 輸出：指向該元素結(jié)點(diǎn)的指針 后置條件：二叉樹不變 二叉樹的抽象數(shù)據(jù)類型定義5.3 二叉樹的邏輯結(jié)構(gòu) PreOrder 前置條件：二叉樹已存在 輸入：無 功能：前序遍歷二叉樹 輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性排列 后置條件：二叉樹不變 InOrder 前置條件：二叉樹已存在 輸入：無 功能：中序遍歷二叉樹 輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性排列 后置條件：二叉樹不變 二叉樹的抽象數(shù)據(jù)類型定義5.3 二叉樹的邏輯結(jié)構(gòu) PostOrder 前置條件：二叉樹已存在 輸入：無 功能：后序遍歷

27、二叉樹 輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性排列 后置條件：二叉樹不變 LeverOrder 前置條件：二叉樹已存在 輸入：無 功能：層序遍歷二叉樹 輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性排列 后置條件：二叉樹不變 endADT二叉樹的抽象數(shù)據(jù)類型定義5.3 二叉樹的邏輯結(jié)構(gòu)二叉樹的遍歷操作 二叉樹的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。二叉樹遍歷操作的結(jié)果？非線性結(jié)構(gòu)線性化5.3 二叉樹的邏輯結(jié)構(gòu)抽象操作，可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理，這里簡化為輸出結(jié)點(diǎn)的數(shù)據(jù)。前序遍歷中序遍歷后序遍歷層序遍歷 二叉樹的遍歷方式：DLR、LDR、LRD、DRL、RDL、R

28、LD 如果限定先左后右，則二叉樹遍歷方式有三種：前序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹的層序編號(hào)的次序訪問各結(jié)點(diǎn)。 5.3 二叉樹的邏輯結(jié)構(gòu)考慮二叉樹的組成：根結(jié)點(diǎn)D左子樹L右子樹R二叉樹前序（根）遍歷若二叉樹為空，則空操作返回；否則：訪問根結(jié)點(diǎn)；前序遍歷根結(jié)點(diǎn)的左子樹；前序遍歷根結(jié)點(diǎn)的右子樹。5.3 二叉樹的邏輯結(jié)構(gòu)前序遍歷序列：A B D G C E FABCDEFG二叉樹的遍歷操作 中序（根）遍歷若二叉樹為空，則空操作返回；否則：中序遍歷根結(jié)點(diǎn)的左子樹；訪問根結(jié)點(diǎn)；中序遍歷根結(jié)點(diǎn)的右子樹。 5.3 二叉樹的邏輯結(jié)構(gòu)中序遍歷序列：D G B A E C FABCDEFG二叉

29、樹的遍歷操作 后序（根）遍歷若二叉樹為空，則空操作返回；否則：后序遍歷根結(jié)點(diǎn)的左子樹；后序遍歷根結(jié)點(diǎn)的右子樹。訪問根結(jié)點(diǎn)；5.3 二叉樹的邏輯結(jié)構(gòu)后序遍歷序列：G D B E F C AABCDEFG二叉樹的遍歷操作 層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層（即根結(jié)點(diǎn)）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。 5.3 二叉樹的邏輯結(jié)構(gòu)層序遍歷序列：A B C D E F GABCDEFG二叉樹的遍歷操作 5.3 二叉樹的邏輯結(jié)構(gòu)-/+*abcdef二叉樹遍歷操作練習(xí)前序遍歷結(jié)果：- + a * b - c d / e f中序遍歷結(jié)果：a + b * c - d

30、 - e / f后序遍歷結(jié)果：a b c d - * + e f / -5.3 二叉樹的邏輯結(jié)構(gòu)若已知一棵二叉樹的前序（或中序，或后序，或?qū)有颍┬蛄?，能否唯一確定這棵二叉樹呢？ABC例：已知前序序列為ABC，則可能的二叉樹有5種。ABC二叉樹的遍歷操作 5.3 二叉樹的邏輯結(jié)構(gòu)例：已知前序遍歷序列為ABC，后序遍歷序列為CBA，則下列二叉樹都滿足條件。ABCABC若已知一棵二叉樹的前序序列和后序序列，能否唯一確定這棵二叉樹呢？二叉樹的遍歷操作 若已知一棵二叉樹的前序序列和中序序列，能否唯一確定這棵二叉樹呢？怎樣確定？ 例如：已知一棵二叉樹的前序遍歷序列和中序遍歷序列分別為ABCDEFGHI 和

31、BCAEDGHFI，如何構(gòu)造該二叉樹呢? 5.3 二叉樹的邏輯結(jié)構(gòu)二叉樹的遍歷操作 前序：A B C D E F G H I中序：B C A E D G H F I前序：B C中序：B C5.3 二叉樹的邏輯結(jié)構(gòu) B C D EF GH IA前序： D E F G H I中序： E D G H F IABCDEFGHI前序：F G H I中序：G H F I5.3 二叉樹的邏輯結(jié)構(gòu)前序： D E F G H I中序： E D G H F IABCDEFGHIABCDEFIGH1. 根據(jù)前序序列的第一個(gè)元素建立根結(jié)點(diǎn)；2. 在中序序列中找到該元素，確定根結(jié)點(diǎn)的左右子樹的中序序列；3. 在前序序列

32、中確定左右子樹的前序序列；4. 由左子樹的前序序列和中序序列建立左子樹；5. 由右子樹的前序序列和中序序列建立右子樹。 5.3 二叉樹的邏輯結(jié)構(gòu)已知一棵二叉樹的前序序列和中序序列，構(gòu)造該二叉樹的過程如下： 二叉樹的遍歷操作 順序存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)二叉樹中的結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）應(yīng)能體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系父子關(guān)系。 如何利用數(shù)組下標(biāo)來反映結(jié)點(diǎn)之間的邏輯關(guān)系?完全二叉樹和滿二叉樹中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系 。5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) A B C D E F G H I J數(shù)組下標(biāo) 1 2 3 4 5 6 7 8 9 10完全二叉樹的順

33、序存儲(chǔ)5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)CDEFGHIJ以編號(hào)為下標(biāo)二叉樹的順序存儲(chǔ)ABCDEFG數(shù)組下標(biāo) 1 2 3 4 5 6 7 8 9 10 11 12 135.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDFGE以編號(hào)為下標(biāo)ABCDFGE123561013按照完全二叉樹編號(hào)一棵斜樹的順序存儲(chǔ)會(huì)怎樣呢？深度為k的右斜樹，k個(gè)結(jié)點(diǎn)需分配2k1個(gè)存儲(chǔ)單元。 一棵二叉樹改造后成完全二叉樹形態(tài)，需增加很多空結(jié)點(diǎn)，造成存儲(chǔ)空間的浪費(fèi)。5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)二叉樹的順序存儲(chǔ)結(jié)構(gòu)一般僅存儲(chǔ)完全二叉樹ABC137D15二叉鏈表基本思想：令二叉樹的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，鏈表結(jié)點(diǎn)除了

34、存放與二叉樹結(jié)點(diǎn)有關(guān)的數(shù)據(jù)信息外，還要設(shè)置指示左右孩子的指針。 結(jié)點(diǎn)結(jié)構(gòu)： lchild data rchild其中，data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息； lchild：左指針域，存放指向左孩子的指針； rchild：右指針域，存放指向右孩子的指針。 5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)template struct BiNode T data; BiNode *lchild, *rchild;5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)lchild datarchild左孩子結(jié)點(diǎn)右孩子結(jié)點(diǎn)二叉鏈表GFEDBAABCDEFGC二叉鏈表5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，有多少個(gè)空指針？GF

35、EDBAABCDEFGC二叉鏈表5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針。二叉鏈表存儲(chǔ)結(jié)構(gòu)的類聲明template class BiTree public: BiTree( )root=NULL; BiTree(BiNode *root); BiTree( ); void PreOrder(BiNode *root); void InOrder(BiNode *root); void PostOrder(BiNode *root); void LeverOrder(BiNode *root); private: BiNode *root; void Creat(

36、BiNode *root); void Release(BiNode *root); ;5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)前序遍歷遞歸算法template void BiTree:PreOrder(BiNode *root) if (root =NULL) return; else coutdata; PreOrder(root-lchild); PreOrder(root-rchild); 5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)AGBCDFE5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)前序遍歷算法的執(zhí)行軌跡二叉樹前序遍歷的非遞歸算法的關(guān)鍵：在前序遍歷過某結(jié)點(diǎn)的整個(gè)左子樹后，如何找到該結(jié)點(diǎn)的右子樹的根指針。解決辦法：在

37、訪問完該結(jié)點(diǎn)后，將該結(jié)點(diǎn)的指針保存在棧中，以便以后能通過它找到該結(jié)點(diǎn)的右子樹。 在前序遍歷中，設(shè)要遍歷二叉樹的根指針為root，則有兩種可能： 若root!=NULL，則表明？如何處理？ 若root=NULL，則表明？如何處理？5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)前序遍歷非遞歸算法訪問結(jié)點(diǎn)序列:A棧S內(nèi)容:BD A B前序遍歷的非遞歸實(shí)現(xiàn) 5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ADBC訪問結(jié)點(diǎn)序列:A棧S內(nèi)容:BD A前序遍歷的非遞歸實(shí)現(xiàn) 5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ADBC D訪問結(jié)點(diǎn)序列:A棧S內(nèi)容:BD C前序遍歷的非遞歸實(shí)現(xiàn) 5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ADBCC1.棧s初始化；2.循環(huán)直到ro

38、ot為空且棧s為空 2.1 當(dāng)root不空時(shí)循環(huán)2.1.1 輸出root-data; 2.1.2 將指針root的值保存到棧中； 2.1.3 繼續(xù)遍歷root的左子樹2.2 如果棧s不空，則2.2.1 將棧頂元素彈出至root；2.2.2 準(zhǔn)備遍歷root的右子樹； 前序遍歷非遞歸算法（偽代碼）5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)前序遍歷非遞歸算法（偽代碼）5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)template void BiTree:PreOrder(BiNode *root) top= -1; /采用順序棧，并假定不會(huì)發(fā)生上溢 while (root!=NULL | | top!= -1) while

39、(root!= NULL) coutdata; s+top=root; root=root-lchild; if (top!= -1) root=stop-; root=root-rchild; 中序遍歷遞歸算法 template void BiTree:InOrder (BiNode *root) if (root=NULL) return; else InOrder(root-lchild); coutdata; InOrder(root-rchild); 5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)后序遍歷遞歸算法template void BiTree:PostOrder(BiNode *root)

40、 if (root=NULL) return; else PostOrder(root-lchild); PostOrder(root-rchild); coutdata; 5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)層序遍歷5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEFG遍歷序列：AABCBDCEFGDEFG層序遍歷隊(duì)列Q初始化；2. 如果二叉樹非空，將根指針入隊(duì)；3. 循環(huán)直到隊(duì)列Q為空 3.1 q=隊(duì)列Q的隊(duì)頭元素出隊(duì)； 3.2 訪問結(jié)點(diǎn)q的數(shù)據(jù)域； 3.3 若結(jié)點(diǎn)q存在左孩子，則將左孩子指針入隊(duì)； 3.4 若結(jié)點(diǎn)q存在右孩子，則將右孩子指針入隊(duì)；5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)二叉樹的建立為了建立一棵二叉

41、樹，將二叉樹中每個(gè)結(jié)點(diǎn)的空指針引出一個(gè)虛結(jié)點(diǎn)，其值為一特定值如“#”，以標(biāo)識(shí)其為空，把這樣處理后的二叉樹稱為原二叉樹的擴(kuò)展二叉樹。 為什么如此處理?5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何由一種遍歷序列生成該二叉樹？遍歷是二叉樹各種操作的基礎(chǔ)，可以在遍歷的過程中進(jìn)行各種操作，例如建立一棵二叉樹。擴(kuò)展二叉樹的前序遍歷序列:A B # D # # C # #5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)DBAC#DBAC#二叉樹的建立設(shè)二叉樹中的結(jié)點(diǎn)均為一個(gè)字符。假設(shè)擴(kuò)展二叉樹的前序遍歷序列由鍵盤輸入，root為指向根結(jié)點(diǎn)的指針，二叉鏈表的建立過程是：首先輸入根結(jié)點(diǎn)，若輸入的是一個(gè)“#”字符，則表明該二叉樹為空樹，即r

42、oot=NULL；否則輸入的字符應(yīng)該賦給root-data,，之后依次遞歸建立它的左子樹和右子樹 。5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)二叉樹的建立template BiTree :BiTree(BiNode *root) creat(root)；void BiTree :Creat(BiNode *root) cinch; if (ch=# ) root=NULL; else root=new BiNode; root-data=ch; creat(root-lchild); creat(root-rchild); 建立二叉遞歸算法5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)二叉樹算法設(shè)計(jì)練習(xí) 遍歷二叉樹是二叉

43、樹各種操作的基礎(chǔ)，遍歷算法中對(duì)每個(gè)結(jié)點(diǎn)的訪問操作可以是多種形式及多個(gè)操作，根據(jù)遍歷算法的框架，適當(dāng)修改訪問操作的內(nèi)容，可以派生出很多關(guān)于二叉樹的應(yīng)用算法。 void InOrder (BiNode *root) if (root=NULL) return; else InOrder(root-lchild); coutdata; InOrder(root-rchild); 二叉樹算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法求二叉樹的結(jié)點(diǎn)個(gè)數(shù)。 void Count(BiNode *root) /n為全局量并已初始化為0 if (root) Count(root-lchild); n+ +; Count(root-rc

44、hild); 二叉樹算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法按前序次序打印二叉樹中的葉子結(jié)點(diǎn)。 void PreOrder(BiNode *root) if (root) if (!root-lchild & !root-rchild) coutdata; PreOrder(root-lchild); PreOrder(root-rchild); 二叉樹算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法求二叉樹的深度。 int Depth(BiNode *root) if (root= =NULL) return 0; else hl= Depth(root-lchild); hr= Depth(root -rchild); return m

45、ax(hl, hr)+1; 二叉樹算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法求樹中結(jié)點(diǎn) x 的第 i 個(gè)孩子。 template TNode *Search(TNode *root, T x, int i) if (root-data= =x) j=1; p=root-firstchild; while (p!=NULL & jrightsib; if (p) return p; else return NULL; Search(root-firstchild, x, i); Search(root-rightsib, x, i);template struct TNode T data; TNode *first

46、child, *rightsib; 三叉鏈表5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)GFEDBAABCDEFGC在二叉鏈表中，如何求某結(jié)點(diǎn)的雙親？三叉鏈表 lchild dataparentrchild在二叉鏈表的基礎(chǔ)上增加了一個(gè)指向雙親的指針域。結(jié)點(diǎn)結(jié)構(gòu)其中：data、lchild和rchild三個(gè)域的含義同二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)；parent域?yàn)橹赶蛟摻Y(jié)點(diǎn)的雙親結(jié)點(diǎn)的指針。 5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEFGABDEFCG三叉鏈表5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEFG三叉鏈表的靜態(tài)鏈表形式5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)0123456data parent lchild rchildABC

47、DEFG-1 0 0 1 2 2 3 1 3 4-1-1-1-1 2-1 5 6-1-1-1線索鏈表5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：D G B A F C F如果二叉樹不改變，如何保存？順序存儲(chǔ)D G B A F C F線索鏈表5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：D G B A F C F如果二叉樹改變，如何保存？鏈接存儲(chǔ) D F 線索鏈表5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：D G B A F C F如何將二叉鏈表與中序鏈表結(jié)合？鏈接存

48、儲(chǔ) D F 線索鏈表線索：將二叉鏈表中的空指針域指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針被稱為線索；線索化：使二叉鏈表中結(jié)點(diǎn)的空鏈域存放其前驅(qū)或后繼信息的過程稱為線索化；線索二叉樹：加上線索的二叉樹稱為線索二叉樹。5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何保存二叉樹的某種遍歷序列？將二叉鏈表中的空指針域指向其前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn) ltag lchild data child rtag0: lchild指向該結(jié)點(diǎn)的左孩子1: lchild指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)0: rchild指向該結(jié)點(diǎn)的右孩子1: rchild指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)ltag=rtag=5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)結(jié)點(diǎn)結(jié)構(gòu)線索鏈表enum flag C

49、hild, Thread; template struct ThrNode T data; ThrNode *lchild, *rchild; flag ltag, rtag;5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線索鏈表 ltag lchild data child rtag結(jié)點(diǎn)結(jié)構(gòu)二叉樹的遍歷方式有4種，故有4種意義下的前驅(qū)和后繼，相應(yīng)的有4種線索二叉樹： 前序線索二叉樹 中序線索二叉樹 后序線索二叉樹 層序線索二叉樹5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線索二叉樹FABDCEG中序線索二叉樹5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線索二叉樹中序序列：D G B A E C Ftemplate class InTh

50、rBiTree public: InThrBiTree(ThrNode * root); InThrBiTree( ); ThrNode *Next(ThrNode *p); void InOrder(ThrNode *root); private: ThrNode *root; void Creat(ThrNode *root); void ThrBiTree(ThrNode *root);5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序線索鏈表類的聲明分析：建立線索鏈表，實(shí)質(zhì)上就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷該二叉樹時(shí)才能得到。5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)

51、建立二叉鏈表遍歷二叉樹，將空指針改為線索中序線索鏈表的建立構(gòu)造函數(shù)A頭指針BCDEFG00000000000000中序線索鏈表的建立過程5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)已經(jīng)建立起二叉鏈表A頭指針BCDEFG00000000000000中序線索鏈表的建立過程5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)p1A頭指針BCDEFG00000000000000中序線索鏈表的建立過程5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre1p1A頭指針BCDEFG00000000000000中序線索鏈表的建立過程5.4 二叉樹的存儲(chǔ)結(jié)

52、構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11p1A頭指針BCDEFG00000000000000中序線索鏈表的建立過程5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11p11A頭指針BCDEFG00000000000000中序線索鏈表的建立過程5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11p111A頭指針BCDEFG00000000000000中序線索鏈表的建立過程5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11p1111A頭指針

53、BCDEFG00000000000000中序線索鏈表的建立過程5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11p11111A頭指針BCDEFG00000000000000中序線索鏈表的建立過程5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11111111在遍歷過程中，訪問當(dāng)前結(jié)點(diǎn)root的操作為：如果root的左、右指針域?yàn)榭眨瑒t將相應(yīng)標(biāo)志置1；若root的左指針域?yàn)榭眨瑒t令其指向它的前驅(qū)，這需要設(shè)指針pre始終指向剛剛訪問過的結(jié)點(diǎn)，顯然pre的初值為NULL；若pre的右指針域?yàn)榭?，則令其指向它的后繼，

54、即當(dāng)前訪問的結(jié)點(diǎn)root; 令pre指向剛剛訪問過的結(jié)點(diǎn)root；5.4 二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序線索鏈表的建立1. 建立二叉鏈表，將每個(gè)結(jié)點(diǎn)的左右標(biāo)志置為0；2. 遍歷二叉鏈表，建立線索； 2.1 如果二叉鏈表root為空，則空操作返回； 2.2 對(duì)root的左子樹建立線索； 2.3 對(duì)根結(jié)點(diǎn)root建立線索； 2.3.1 若root沒有左孩子，則為root加上前驅(qū)線索; 2.3.2 若root沒有右孩子，則將root右標(biāo)志置為1； 2.3.3 若結(jié)點(diǎn)pre右標(biāo)志為1，則為pre加上后繼線索； 2.3.4 令pre指向剛剛訪問的結(jié)點(diǎn)root； 2.4 對(duì)root的右子樹建立線索。5.4 二

55、叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序線索鏈表的建立構(gòu)造函數(shù)5.5 樹、森林與二叉樹的轉(zhuǎn)換是哪些樹結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)?樹和二叉樹之間具有對(duì)應(yīng)關(guān)系A(chǔ)EBCFDGABCEDFGABCDEFG5.5 樹、森林與二叉樹的轉(zhuǎn)換樹和二叉樹之間的對(duì)應(yīng)關(guān)系 樹：兄弟關(guān)系二叉樹：雙親和右孩子 樹：雙親和長子二叉樹：雙親和左孩子AEBCFDGABCDEFG5.5 樹、森林與二叉樹的轉(zhuǎn)換 1.兄弟加線.樹和二叉樹之間的對(duì)應(yīng)關(guān)系A(chǔ)BCDEFG5.5 樹、森林與二叉樹的轉(zhuǎn)換2.保留雙親與第一孩子連線,刪去與其他孩子的連線.ABCDEFG樹和二叉樹之間的對(duì)應(yīng)關(guān)系 1.兄弟加線.3.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.5.5 樹、森林與二叉樹的轉(zhuǎn)換樹

56、和二叉樹之間的對(duì)應(yīng)關(guān)系2.保留雙親與第一孩子連線,刪去與其他孩子的連線. 1.兄弟加線.ABCDEFG3.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.5.5 樹、森林與二叉樹的轉(zhuǎn)換樹和二叉樹之間的對(duì)應(yīng)關(guān)系2.保留雙親與第一孩子連線,刪去與其他孩子的連線. 1.兄弟加線.GDABECF樹轉(zhuǎn)換為二叉樹 加線樹中所有相鄰兄弟之間加一條連線。 去線對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去它與其它孩子結(jié)點(diǎn)之間的連線。 層次調(diào)整以根結(jié)點(diǎn)為軸心，將樹順時(shí)針轉(zhuǎn)動(dòng)一定的角度，使之層次分明。 5.5 樹、森林與二叉樹的轉(zhuǎn)換CBEDFGAABEFCDG前序遍歷AEBCFDGABEFCDG前序遍歷樹的前序遍歷等價(jià)于二

57、叉樹的前序遍歷！5.5 樹、森林與二叉樹的轉(zhuǎn)換EFBCGDA后序遍歷EFBCGDA中序遍歷樹的后序遍歷等價(jià)于二叉樹的中序遍歷！5.5 樹、森林與二叉樹的轉(zhuǎn)換CBEDFGAAEBCFDG森林轉(zhuǎn)換為二叉樹 將森林中的每棵樹轉(zhuǎn)換成二叉樹； 從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連起來后，此時(shí)所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。5.5 樹、森林與二叉樹的轉(zhuǎn)換FEDCBAGHIJBAFEDCGHIKKIFEHABCGD5.5 樹、森林與二叉樹的轉(zhuǎn)換二叉樹轉(zhuǎn)換為樹或森林 加線若某結(jié)點(diǎn)x是其雙親y的左孩子，則把結(jié)點(diǎn)x的右孩子、右孩子的右孩子、，都與結(jié)

58、點(diǎn)y用線連起來； 去線刪去原二叉樹中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線； 層次調(diào)整整理由、兩步所得到的樹或森林，使之層次分明。 5.5 樹、森林與二叉樹的轉(zhuǎn)換FHGEAICDBFHGDCEBAIFEDCBAHGI加線去線層次調(diào)整IHGBCDAFE5.5 樹、森林與二叉樹的轉(zhuǎn)換森林的遍歷森林有兩種遍歷方法：前序（根）遍歷：前序遍歷森林即為前序遍歷森林中的每一棵樹。 后序（根）遍歷：后序遍歷森林即為后序遍歷森林中的每一棵樹。 5.5 樹、森林與二叉樹的轉(zhuǎn)換相關(guān)概念葉子結(jié)點(diǎn)的權(quán)值：對(duì)葉子結(jié)點(diǎn)賦予的一個(gè)有意義的數(shù)值量。 二叉樹的帶權(quán)路徑長度：設(shè)二叉樹具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑

59、長度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和。 記為：WPL=5.6 哈夫曼樹及哈夫曼編碼=nkkklw1第k個(gè)葉子的權(quán)值；從根結(jié)點(diǎn)到第k個(gè)葉子的路徑長度哈夫曼樹：給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，帶權(quán)路徑長度最小的二叉樹。例：給定4個(gè)葉子結(jié)點(diǎn)，其權(quán)值分別為2，3，4，7，可以構(gòu)造出形狀不同的多個(gè)二叉樹。 5.6 哈夫曼樹及哈夫曼編碼WPL=32 WPL=41 WPL=30234723477423哈夫曼樹的特點(diǎn)：1. 權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。 2. 只有度為0（葉子結(jié)點(diǎn)）和度為2（分支結(jié)點(diǎn)）的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn). 5.6 哈夫曼樹及哈夫曼編碼2347WPL=3

60、2 WPL=41 WPL=3023477423哈夫曼算法基本思想： 初始化：由給定的n個(gè)權(quán)值w1，w2，wn構(gòu)造n棵只有一個(gè)根結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹集合FT1，T2，Tn； 選取與合并：在F中選取根結(jié)點(diǎn)的權(quán)值最小的兩棵二叉樹分別作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和； 刪除與加入：在F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到F中； 重復(fù)、兩步，當(dāng)集合F中只剩下一棵二叉樹時(shí)，這棵二叉樹便是哈夫曼樹。 5.6 哈夫曼樹及哈夫曼編碼第1步：初始化W2，3，4，5 哈夫曼樹的構(gòu)造過程5.6 哈夫曼樹及哈夫曼編碼3524第2