第5章-樹(shù)和二叉樹(shù)課件

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

2、輯結(jié)構(gòu)My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)。樹(shù)的度：樹(shù)中各結(jié)點(diǎn)度的最大值。5.1 樹(shù)的邏輯結(jié)構(gòu)CGBDEFKLHMIJA5.1 樹(shù)的邏輯結(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ù)的基本術(shù)語(yǔ)孩子、雙親：樹(shù)中某結(jié)點(diǎn)子樹(shù)的根結(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 樹(shù)的邏輯結(jié)構(gòu)CGBDEFKLHMIJA樹(shù)的基本術(shù)語(yǔ)路徑：如果樹(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)過(guò)的邊的個(gè)數(shù)稱為路徑長(zhǎng)度。 CGBDEFKLHMIJA5.1 樹(shù)的邏輯結(jié)構(gòu)樹(shù)的基本術(shù)語(yǔ)祖先、子孫：在樹(shù)中，如果有一條路徑從結(jié)點(diǎn)x到結(jié)點(diǎn)y，那么x就稱為y的祖先，而y稱為x的子孫。5.1 樹(shù)的邏輯結(jié)構(gòu)CGBDEFKLHMIJA樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)所在層數(shù)：根結(jié)點(diǎn)的層數(shù)為1；對(duì)其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第k層，則其孩子結(jié)點(diǎn)在第k+1層。樹(shù)的深度：樹(shù)中所有結(jié)點(diǎn)的最大層數(shù)，也稱高度。1層2層4層3層高度4CGBDEFKLHMIJC5.1 樹(shù)的邏輯結(jié)構(gòu)樹(shù)的基本術(shù)語(yǔ)CBDEFKLHJA

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

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

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

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

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

9、點(diǎn)之間的邏輯關(guān)系。數(shù)據(jù)元素以及數(shù)據(jù)元素之間的邏輯關(guān)系在存儲(chǔ)器中的表示。雙親表示法基本思想：用一維數(shù)組來(lái)存儲(chǔ)樹(shù)的各個(gè)結(jié)點(diǎn)（一般按層序存儲(chǔ)），數(shù)組中的一個(gè)元素對(duì)應(yīng)樹(shù)中的一個(gè)結(jié)點(diǎn)，包括結(jié)點(diǎn)的數(shù)據(jù)信息以及該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo)。 5.2 樹(shù)的存儲(chǔ)結(jié)構(gòu) data parentdata：存儲(chǔ)樹(shù)中結(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 樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的雙親表示法實(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 樹(shù)的存儲(chǔ)結(jié)構(gòu)如何查找雙親結(jié)點(diǎn)？時(shí)間性能？雙親表示法ACBHFEDGI5.2 樹(shù)的存儲(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 樹(shù)的存儲(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 樹(shù)的存儲(chǔ)結(jié)構(gòu)孩子鏈表表示法方案一：指針域的個(gè)數(shù)等于樹(shù)的度data child1 child2 childd其中：data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息； child1childd：指針域，指向該結(jié)點(diǎn)的孩子。 5.2 樹(shù)的存儲(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 樹(shù)的存儲(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 樹(shù)的存儲(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)的孩子排列起來(lái)，看成是一個(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é)合起來(lái)，構(gòu)成孩子鏈表的表頭數(shù)組。 5.2 樹(shù)的存儲(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 樹(shù)的存儲(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 樹(shù)的存儲(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 樹(shù)的存儲(chǔ)結(jié)構(gòu)12 345 7 68 如何查找雙親結(jié)點(diǎn)？時(shí)間性能？雙親孩子表示法5.2 樹(shù)的存儲(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 樹(shù)的存儲(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 樹(shù)的存儲(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 樹(shù)的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法ACBHFEDGI A B C D E F G H I如何查找兄弟結(jié)點(diǎn)？時(shí)間性能？5.2 樹(shù)的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法ACBHFEDGI A B C D E F G H I如何查找孩子結(jié)點(diǎn)？時(shí)間性能？二叉樹(shù)的定義 二叉樹(shù)是n（n0）個(gè)結(jié)點(diǎn)的有限集合，該集合或

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

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

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

19、5234678910BCDEFGHIJ不是完全二叉樹(shù)，結(jié)點(diǎn)10與滿二叉樹(shù)中的結(jié)點(diǎn)10不是同一個(gè)結(jié)點(diǎn)特殊的二叉樹(shù)1. 葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點(diǎn)都集中在二叉樹(shù)的左部；2. 完全二叉樹(shù)中如果有度為1的結(jié)點(diǎn)，只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子。 3. 深度為k的完全二叉樹(shù)在k-1層上一定是滿二叉樹(shù)。完全二叉樹(shù)的特點(diǎn)5.3 二叉樹(shù)的邏輯結(jié)構(gòu)特殊的二叉樹(shù)CDEFGHIJ二叉樹(shù)的基本性質(zhì) 性質(zhì)5-1 二叉樹(shù)的第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)的孩子，而二叉樹(shù)中每個(gè)結(jié)點(diǎn)最多有2個(gè)孩子，故在第k+1層上最大結(jié)點(diǎn)個(gè)數(shù)為第k層上的最大結(jié)點(diǎn)個(gè)數(shù)的二倍，即22k-12k。結(jié)論成立。5.3 二叉樹(shù)的邏輯結(jié)構(gòu)性質(zhì)5-2 一棵深度為k的二叉樹(shù)中，最多有2k-1個(gè)結(jié)點(diǎn)，最少有k個(gè)結(jié)點(diǎn)。 證明：由性質(zhì)1可知，深度為k的二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)最多= =2k-1；每一層至少要有一個(gè)結(jié)點(diǎn)，因此深度為k的二叉樹(shù)，至少有k個(gè)結(jié)點(diǎn)。5.3 二叉樹(shù)的邏輯結(jié)構(gòu)深度為k且具有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)一定是滿二叉樹(shù)，深度為k且具有k個(gè)結(jié)點(diǎn)的二叉樹(shù)不一定是斜樹(shù)。！二叉樹(shù)的基本性質(zhì) 性質(zhì)5-3 在一棵

21、二叉樹(shù)中，如果葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有: n0n21。 證明: 設(shè)n為二叉樹(shù)的結(jié)點(diǎn)總數(shù)，n1為二叉樹(shù)中度為1的結(jié)點(diǎn)數(shù)，則有： nn0n1n2 在二叉樹(shù)中，除了根結(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 二叉樹(shù)的邏輯結(jié)構(gòu)二叉樹(shù)的基本性質(zhì) 5.3 二叉樹(shù)的邏輯結(jié)構(gòu)在有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)中，有多少個(gè)葉子結(jié)點(diǎn)？因?yàn)樵跐M二叉樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，只有度為0的葉子結(jié)點(diǎn)和度為2的分支結(jié)點(diǎn)，所以，n n0 + n2n0n2 + 1

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

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

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

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

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

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

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

29、樹(shù)的遍歷操作 后序（根）遍歷若二叉樹(shù)為空，則空操作返回；否則：后序遍歷根結(jié)點(diǎn)的左子樹(shù)；后序遍歷根結(jié)點(diǎn)的右子樹(shù)。訪問(wèn)根結(jié)點(diǎn)；5.3 二叉樹(shù)的邏輯結(jié)構(gòu)后序遍歷序列：G D B E F C AABCDEFG二叉樹(shù)的遍歷操作 層序遍歷二叉樹(shù)的層次遍歷是指從二叉樹(shù)的第一層（即根結(jié)點(diǎn)）開(kāi)始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)。 5.3 二叉樹(shù)的邏輯結(jié)構(gòu)層序遍歷序列：A B C D E F GABCDEFG二叉樹(shù)的遍歷操作 5.3 二叉樹(shù)的邏輯結(jié)構(gòu)-/+*abcdef二叉樹(shù)遍歷操作練習(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 二叉樹(shù)的邏輯結(jié)構(gòu)若已知一棵二叉樹(shù)的前序（或中序，或后序，或?qū)有颍┬蛄?，能否唯一確定這棵二叉樹(shù)呢？ABC例：已知前序序列為ABC，則可能的二叉樹(shù)有5種。ABC二叉樹(shù)的遍歷操作 5.3 二叉樹(shù)的邏輯結(jié)構(gòu)例：已知前序遍歷序列為ABC，后序遍歷序列為CBA，則下列二叉樹(shù)都滿足條件。ABCABC若已知一棵二叉樹(shù)的前序序列和后序序列，能否唯一確定這棵二叉樹(shù)呢？二叉樹(shù)的遍歷操作 若已知一棵二叉樹(shù)的前序序列和中序序列，能否唯一確定這棵二叉樹(shù)呢？怎樣確定？ 例如：已知一棵二叉樹(shù)的前序遍歷序列和中序遍歷序列分別為ABCDEFGHI 和

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

32、中確定左右子樹(shù)的前序序列；4. 由左子樹(shù)的前序序列和中序序列建立左子樹(shù)；5. 由右子樹(shù)的前序序列和中序序列建立右子樹(shù)。 5.3 二叉樹(shù)的邏輯結(jié)構(gòu)已知一棵二叉樹(shù)的前序序列和中序序列，構(gòu)造該二叉樹(shù)的過(guò)程如下： 二叉樹(shù)的遍歷操作 順序存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)二叉樹(shù)中的結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）應(yīng)能體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系父子關(guān)系。 如何利用數(shù)組下標(biāo)來(lái)反映結(jié)點(diǎn)之間的邏輯關(guān)系?完全二叉樹(shù)和滿二叉樹(shù)中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系 。5.4 二叉樹(shù)的存儲(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完全二叉樹(shù)的順

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

34、存放與二叉樹(shù)結(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 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)template struct BiNode T data; BiNode *lchild, *rchild;5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)lchild datarchild左孩子結(jié)點(diǎn)右孩子結(jié)點(diǎn)二叉鏈表GFEDBAABCDEFGC二叉鏈表5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，有多少個(gè)空指針？GF

35、EDBAABCDEFGC二叉鏈表5.4 二叉樹(shù)的存儲(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 二叉樹(shù)的存儲(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 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)AGBCDFE5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)前序遍歷算法的執(zhí)行軌跡二叉樹(shù)前序遍歷的非遞歸算法的關(guān)鍵：在前序遍歷過(guò)某結(jié)點(diǎn)的整個(gè)左子樹(shù)后，如何找到該結(jié)點(diǎn)的右子樹(shù)的根指針。解決辦法：在

37、訪問(wèn)完該結(jié)點(diǎn)后，將該結(jié)點(diǎn)的指針保存在棧中，以便以后能通過(guò)它找到該結(jié)點(diǎn)的右子樹(shù)。 在前序遍歷中，設(shè)要遍歷二叉樹(shù)的根指針為root，則有兩種可能： 若root!=NULL，則表明？如何處理？ 若root=NULL，則表明？如何處理？5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)前序遍歷非遞歸算法訪問(wèn)結(jié)點(diǎn)序列:A棧S內(nèi)容:BD A B前序遍歷的非遞歸實(shí)現(xiàn) 5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ADBC訪問(wèn)結(jié)點(diǎn)序列:A棧S內(nèi)容:BD A前序遍歷的非遞歸實(shí)現(xiàn) 5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ADBC D訪問(wèn)結(jié)點(diǎn)序列:A棧S內(nèi)容:BD C前序遍歷的非遞歸實(shí)現(xiàn) 5.4 二叉樹(shù)的存儲(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的左子樹(shù)2.2 如果棧s不空，則2.2.1 將棧頂元素彈出至root；2.2.2 準(zhǔn)備遍歷root的右子樹(shù)； 前序遍歷非遞歸算法（偽代碼）5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)前序遍歷非遞歸算法（偽代碼）5.4 二叉樹(shù)的存儲(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 二叉樹(shù)的存儲(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 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)層序遍歷5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEFG遍歷序列：AABCBDCEFGDEFG層序遍歷隊(duì)列Q初始化；2. 如果二叉樹(shù)非空，將根指針入隊(duì)；3. 循環(huán)直到隊(duì)列Q為空 3.1 q=隊(duì)列Q的隊(duì)頭元素出隊(duì)； 3.2 訪問(wèn)結(jié)點(diǎn)q的數(shù)據(jù)域； 3.3 若結(jié)點(diǎn)q存在左孩子，則將左孩子指針入隊(duì)； 3.4 若結(jié)點(diǎn)q存在右孩子，則將右孩子指針入隊(duì)；5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)二叉樹(shù)的建立為了建立一棵二叉

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

42、oot=NULL；否則輸入的字符應(yīng)該賦給root-data,，之后依次遞歸建立它的左子樹(shù)和右子樹(shù) 。5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)二叉樹(shù)的建立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 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)二叉樹(shù)算法設(shè)計(jì)練習(xí) 遍歷二叉樹(shù)是二叉

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

44、hild); 二叉樹(shù)算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法按前序次序打印二叉樹(shù)中的葉子結(jié)點(diǎn)。 void PreOrder(BiNode *root) if (root) if (!root-lchild & !root-rchild) coutdata; PreOrder(root-lchild); PreOrder(root-rchild); 二叉樹(shù)算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法求二叉樹(shù)的深度。 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ù)算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法求樹(shù)中結(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 二叉樹(shù)的存儲(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 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEFGABDEFCG三叉鏈表5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEFG三叉鏈表的靜態(tài)鏈表形式5.4 二叉樹(shù)的存儲(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 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何保存二叉樹(shù)的某種遍歷序列？ABCDEFG中序遍歷序列：D G B A F C F如果二叉樹(shù)不改變，如何保存？順序存儲(chǔ)D G B A F C F線索鏈表5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何保存二叉樹(shù)的某種遍歷序列？ABCDEFG中序遍歷序列：D G B A F C F如果二叉樹(shù)改變，如何保存？鏈接存儲(chǔ) D F 線索鏈表5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何保存二叉樹(shù)的某種遍歷序列？ABCDEFG中序遍歷序列：D G B A F C F如何將二叉鏈表與中序鏈表結(jié)合？鏈接存

48、儲(chǔ) D F 線索鏈表線索：將二叉鏈表中的空指針域指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針被稱為線索；線索化：使二叉鏈表中結(jié)點(diǎn)的空鏈域存放其前驅(qū)或后繼信息的過(guò)程稱為線索化；線索二叉樹(shù)：加上線索的二叉樹(shù)稱為線索二叉樹(shù)。5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何保存二叉樹(shù)的某種遍歷序列？將二叉鏈表中的空指針域指向其前驅(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 二叉樹(shù)的存儲(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 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線索鏈表 ltag lchild data child rtag結(jié)點(diǎn)結(jié)構(gòu)二叉樹(shù)的遍歷方式有4種，故有4種意義下的前驅(qū)和后繼，相應(yīng)的有4種線索二叉樹(shù)： 前序線索二叉樹(shù) 中序線索二叉樹(shù) 后序線索二叉樹(shù) 層序線索二叉樹(shù)5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線索二叉樹(shù)FABDCEG中序線索二叉樹(shù)5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線索二叉樹(shù)中序序列：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 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序線索鏈表類的聲明分析：建立線索鏈表，實(shí)質(zhì)上就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷該二叉樹(shù)時(shí)才能得到。5.4 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)

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

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

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

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

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

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

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

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

59、長(zhǎng)度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和。 記為：WPL=5.6 哈夫曼樹(shù)及哈夫曼編碼=nkkklw1第k個(gè)葉子的權(quán)值；從根結(jié)點(diǎn)到第k個(gè)葉子的路徑長(zhǎng)度哈夫曼樹(shù)：給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)。例：給定4個(gè)葉子結(jié)點(diǎn)，其權(quán)值分別為2，3，4，7，可以構(gòu)造出形狀不同的多個(gè)二叉樹(shù)。 5.6 哈夫曼樹(shù)及哈夫曼編碼WPL=32 WPL=41 WPL=30234723477423哈夫曼樹(shù)的特點(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 哈夫曼樹(shù)及哈夫曼編碼2347WPL=3

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