第5章-樹和二叉樹課件

1、樹的邏輯結(jié)構(gòu)樹的存儲結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)及實現(xiàn)樹、森林與二叉樹的轉(zhuǎn)換哈夫曼樹第 5 章 樹和二叉樹本章的主要內(nèi)容是樹的定義樹：n（n0）個結(jié)點的有限集合。當(dāng)n0時，稱為空樹；任意一棵非空樹滿足以下條件： 有且僅有一個特定的稱為根的結(jié)點； 當(dāng)n1時，除根結(jié)點之外的其余結(jié)點被分成m（m0）個互不相交的有限集合T1,T2, ,Tm，其中每個集合又是一棵樹，并稱為這個根結(jié)點的子樹。5.1 樹的邏輯結(jié)構(gòu)樹的定義是采用遞歸方法(a) 一棵樹結(jié)構(gòu) (b)一個非樹結(jié)構(gòu) (c)一個非樹結(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é)點的度：結(jié)點所擁有的子樹的個數(shù)。樹的度：樹中各結(jié)點度的最大值。5.1 樹的邏輯結(jié)構(gòu)CGBDEFKLHMIJA5.1 樹的邏輯結(jié)構(gòu)葉子結(jié)點：度為0的結(jié)點，也稱為終端結(jié)點。分支結(jié)點：度不為0的結(jié)點，也稱為非終端結(jié)點。CGBDEFKLHMIJA樹的基本術(shù)語孩子、雙親：樹中某結(jié)點子樹的根結(jié)點稱為這個結(jié)點的孩子結(jié)點，這個結(jié)點稱為它孩子結(jié)點的雙親結(jié)點；兄弟：具有同一個雙親的孩子結(jié)點互稱為兄弟。 5.1 樹的邏輯結(jié)構(gòu)CGBDEFKLHMIJA樹的基本術(shù)語路徑：如果樹的結(jié)點序列n1, n

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

4、71234568910層序編號：將樹中結(jié)點按照從上層到下層、同層從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù)。5.1 樹的邏輯結(jié)構(gòu)樹的基本術(shù)語有序樹、無序樹：如果一棵樹中結(jié)點的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹 5.1 樹的邏輯結(jié)構(gòu)樹的基本術(shù)語ACBGFEDACBGFEDCBDEFKLHJ森林：m (m0)棵互不相交的樹的集合。 5.1 樹的邏輯結(jié)構(gòu)樹的基本術(shù)語A同構(gòu)：對兩棵樹，若通過對結(jié)點適當(dāng)?shù)刂孛?，就可以使這兩棵樹完全相等（結(jié)點對應(yīng)相等，結(jié)點對應(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)第一個數(shù)據(jù)元素根結(jié)點（只有一個）無前驅(qū)無雙親最后一個數(shù)據(jù)元素葉子結(jié)點(可以有多個)無后繼無孩子其它數(shù)據(jù)元素其它結(jié)點一個前驅(qū),一個后繼一個雙親,多個孩子一對一 一對多5.1 樹的邏輯結(jié)構(gòu)樹的抽象數(shù)據(jù)類型定義ADT TreeData 樹是由一個根結(jié)點和若干棵子樹構(gòu)成， 樹中結(jié)點具有相同數(shù)據(jù)類型及層次關(guān)系Operation InitTree 前置條件：樹不存在 輸入：無 功能：初始化一棵樹 輸出：無 后置條件：構(gòu)造一個空樹5.1 樹的邏輯結(jié)構(gòu) DestroyTree 前置條件：樹已存在 輸入：無 功能：銷毀一棵樹 輸出：無 后置條件：釋放該樹占用的存儲空

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

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

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

9、點之間的邏輯關(guān)系。數(shù)據(jù)元素以及數(shù)據(jù)元素之間的邏輯關(guān)系在存儲器中的表示。雙親表示法基本思想：用一維數(shù)組來存儲樹的各個結(jié)點（一般按層序存儲），數(shù)組中的一個元素對應(yīng)樹中的一個結(jié)點，包括結(jié)點的數(shù)據(jù)信息以及該結(jié)點的雙親在數(shù)組中的下標(biāo)。 5.2 樹的存儲結(jié)構(gòu) data parentdata：存儲樹中結(jié)點的數(shù)據(jù)信息parent：存儲該結(jié)點的雙親在數(shù)組中的下標(biāo)template struct PNode T data; /數(shù)據(jù)域 int parent; /指針域，雙親在數(shù)組中的下標(biāo) ; data parent5.2 樹的存儲結(jié)構(gòu)樹的雙親表示法實質(zhì)上是一個靜態(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 樹的存儲結(jié)構(gòu)如何查找雙親結(jié)點？時間性能？雙親表示法ACBHFEDGI5.2 樹的存儲結(jié)構(gòu)雙親表示法ACBHFEDGI如何查找孩子結(jié)點？時間性能？下標(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 樹的存儲結(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é)點？時間性能？鏈表中的每個結(jié)點包括一個數(shù)據(jù)域和多個指針域，每個指針域指向該結(jié)點的一個孩子結(jié)點。 如何確定鏈表中的結(jié)點結(jié)構(gòu)？5.2 樹的存儲結(jié)構(gòu)孩子鏈表表示法方案一：指針域的個數(shù)等于樹的度data child1 child2 childd其中：data：數(shù)據(jù)域，存放該結(jié)點的數(shù)據(jù)信息； child1childd：指針域，指向該結(jié)點的孩子。 5.2 樹的存儲結(jié)構(gòu)缺點：浪費空間ACBHFEDGIABCDEFGHI鏈表中的每個結(jié)點包括一個數(shù)據(jù)域和多個指針域，每個指針域指向該結(jié)點的一個孩子結(jié)點。 如何確定鏈表中的結(jié)點結(jié)構(gòu)？5.2 樹的存儲結(jié)構(gòu)孩子鏈表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、樹的遍歷操作 后序（根）遍歷若二叉樹為空，則空操作返回；否則：后序遍歷根結(jié)點的左子樹；后序遍歷根結(jié)點的右子樹。訪問根結(jié)點；5.3 二叉樹的邏輯結(jié)構(gòu)后序遍歷序列：G D B E F C AABCDEFG二叉樹的遍歷操作 層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層（即根結(jié)點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問。 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ù)前序序列的第一個元素建立根結(jié)點；2. 在中序序列中找到該元素，確定根結(jié)點的左右子樹的中序序列；3. 在前序序列

32、中確定左右子樹的前序序列；4. 由左子樹的前序序列和中序序列建立左子樹；5. 由右子樹的前序序列和中序序列建立右子樹。 5.3 二叉樹的邏輯結(jié)構(gòu)已知一棵二叉樹的前序序列和中序序列，構(gòu)造該二叉樹的過程如下： 二叉樹的遍歷操作 順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲二叉樹中的結(jié)點，并且結(jié)點的存儲位置（下標(biāo)）應(yīng)能體現(xiàn)結(jié)點之間的邏輯關(guān)系父子關(guān)系。 如何利用數(shù)組下標(biāo)來反映結(jié)點之間的邏輯關(guān)系?完全二叉樹和滿二叉樹中結(jié)點的序號可以唯一地反映出結(jié)點之間的邏輯關(guān)系 。5.4 二叉樹的存儲結(jié)構(gòu)及實現(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、序存儲5.4 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)CDEFGHIJ以編號為下標(biāo)二叉樹的順序存儲ABCDEFG數(shù)組下標(biāo) 1 2 3 4 5 6 7 8 9 10 11 12 135.4 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)ABCDFGE以編號為下標(biāo)ABCDFGE123561013按照完全二叉樹編號一棵斜樹的順序存儲會怎樣呢？深度為k的右斜樹，k個結(jié)點需分配2k1個存儲單元。 一棵二叉樹改造后成完全二叉樹形態(tài)，需增加很多空結(jié)點，造成存儲空間的浪費。5.4 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)二叉樹的順序存儲結(jié)構(gòu)一般僅存儲完全二叉樹ABC137D15二叉鏈表基本思想：令二叉樹的每個結(jié)點對應(yīng)一個鏈表結(jié)點，鏈表結(jié)點除了

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

35、EDBAABCDEFGC二叉鏈表5.4 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)具有n個結(jié)點的二叉鏈表中，有n+1個空指針。二叉鏈表存儲結(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 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)前序遍歷遞歸算法template void BiTree:PreOrder(BiNode *root) if (root =NULL) return; else coutdata; PreOrder(root-lchild); PreOrder(root-rchild); 5.4 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)AGBCDFE5.4 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)前序遍歷算法的執(zhí)行軌跡二叉樹前序遍歷的非遞歸算法的關(guān)鍵：在前序遍歷過某結(jié)點的整個左子樹后，如何找到該結(jié)點的右子樹的根指針。解決辦法：在

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

38、ot為空且棧s為空 2.1 當(dāng)root不空時循環(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 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)前序遍歷非遞歸算法（偽代碼）5.4 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)template void BiTree:PreOrder(BiNode *root) top= -1; /采用順序棧，并假定不會發(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 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)后序遍歷遞歸算法template void BiTree:PostOrder(BiNode *root)

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

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

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

43、樹各種操作的基礎(chǔ)，遍歷算法中對每個結(jié)點的訪問操作可以是多種形式及多個操作，根據(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è)計練習(xí)設(shè)計算法求二叉樹的結(jié)點個數(shù)。 void Count(BiNode *root) /n為全局量并已初始化為0 if (root) Count(root-lchild); n+ +; Count(root-rc

44、hild); 二叉樹算法設(shè)計練習(xí)設(shè)計算法按前序次序打印二叉樹中的葉子結(jié)點。 void PreOrder(BiNode *root) if (root) if (!root-lchild & !root-rchild) coutdata; PreOrder(root-lchild); PreOrder(root-rchild); 二叉樹算法設(shè)計練習(xí)設(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è)計練習(xí)設(shè)計算法求樹中結(jié)點 x 的第 i 個孩子。 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 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)GFEDBAABCDEFGC在二叉鏈表中，如何求某結(jié)點的雙親？三叉鏈表 lchild dataparentrchild在二叉鏈表的基礎(chǔ)上增加了一個指向雙親的指針域。結(jié)點結(jié)構(gòu)其中：data、lchild和rchild三個域的含義同二叉鏈表的結(jié)點結(jié)構(gòu)；parent域為指向該結(jié)點的雙親結(jié)點的指針。 5.4 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)ABCDEFGABDEFCG三叉鏈表5.4 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)ABCDEFG三叉鏈表的靜態(tài)鏈表形式5.4 二叉樹的存儲結(jié)構(gòu)及實現(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 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：D G B A F C F如果二叉樹不改變，如何保存？順序存儲D G B A F C F線索鏈表5.4 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：D G B A F C F如果二叉樹改變，如何保存？鏈接存儲 D F 線索鏈表5.4 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：D G B A F C F如何將二叉鏈表與中序鏈表結(jié)合？鏈接存

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

49、hild, Thread; template struct ThrNode T data; ThrNode *lchild, *rchild; flag ltag, rtag;5.4 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)線索鏈表 ltag lchild data child rtag結(jié)點結(jié)構(gòu)二叉樹的遍歷方式有4種，故有4種意義下的前驅(qū)和后繼，相應(yīng)的有4種線索二叉樹： 前序線索二叉樹 中序線索二叉樹 后序線索二叉樹 層序線索二叉樹5.4 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)線索二叉樹FABDCEG中序線索二叉樹5.4 二叉樹的存儲結(jié)構(gòu)及實現(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 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)中序線索鏈表類的聲明分析：建立線索鏈表，實質(zhì)上就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷該二叉樹時才能得到。5.4 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)

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

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

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

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

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

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

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

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

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

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