數(shù)據(jù)結(jié)構(gòu)：第六章 樹和二叉樹

1、1第6章 樹和二叉樹 6.1 樹的定義和基本術(shù)語 6.2 二叉樹 6.3 遍歷二叉樹和線索二叉樹 6.4 樹和森林 6.6 赫夫曼樹及其應(yīng)用本章要點深入掌握樹的相關(guān)概念、樹的表示和樹的性質(zhì)深入掌握二叉樹的相關(guān)概念、二叉樹的性質(zhì)和二叉樹的存儲結(jié)構(gòu)深入掌握二叉樹運算的實現(xiàn)過程掌握樹和森林的相互轉(zhuǎn)換過程深入掌握赫夫曼樹的構(gòu)造過程和赫夫曼編碼靈活應(yīng)用二叉樹的特點解決復雜的應(yīng)用問題難點：赫夫曼樹的構(gòu)造過程和赫夫曼編碼重點： 1、樹和二叉樹的相關(guān)概念、性質(zhì) 2、樹和二叉樹的存儲結(jié)構(gòu)及其基本運算的實現(xiàn) 3、赫夫曼樹的構(gòu)造過程和赫夫曼編碼本章要點：236.1 樹的定義和基本術(shù)語一. 樹的抽象數(shù)據(jù)類型定義二.

2、樹的基本術(shù)語46.1 樹的定義和基本術(shù)語一. 樹的抽象數(shù)據(jù)類型定義1. 樹的定義 樹是由n (n 0)個結(jié)點組成的有限集合。 如果n = 0，稱為空樹； 如果n 0，則: 有且只有一個特定的稱之為根(root)的結(jié)點，它只有后繼，但沒有前驅(qū)； 除根以外的其它結(jié)點劃分為m (m 0)個互不相交的有限集合T1, T2, , Tm，每個集合本身又是一棵樹，并且稱之為根的子樹(SubTree)。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個后繼。56.1 樹的定義和基本術(shù)語一. 樹的抽象數(shù)據(jù)類型定義2. 樹的表示方法 圖6.1 樹的示例 66.1 樹的定義和基本術(shù)語一. 樹的抽象數(shù)據(jù)類型定義

3、2. 樹的表示方法 (a)嵌套集合表示法 (b)廣義表表示法 (c)凹入表示法76.1 樹的定義和基本術(shù)語二. 樹的基本術(shù)語結(jié)點:結(jié)點的度:樹的度:葉子結(jié)點:分支結(jié)點:數(shù)據(jù)元素+若干指向子樹的分支結(jié)點擁有的分支個數(shù)樹中所有結(jié)點的度的最大值度為零的結(jié)點度大于零的結(jié)點DHIJM86.1 樹的定義和基本術(shù)語二. 樹的基本術(shù)語(從根到結(jié)點的)路徑：孩子結(jié)點、雙親結(jié)點、兄弟結(jié)點、堂兄弟祖先結(jié)點、子孫結(jié)點結(jié)點的層次: 由從根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成。假設(shè)根結(jié)點的層次為1,第l 層的結(jié)點的子樹根結(jié)點的層次為l+1ABCDEFGHIJMKL樹的深度：樹中葉子結(jié)點所在的最大層次96.1 樹的定義和基本術(shù)語二.

4、 樹的基本術(shù)語有序樹：是指樹中結(jié)點的各子樹從左至右是有次序的（不能互換），否則稱為無序樹。森林：是m（m0）棵互不相交的樹的集合。106.2 二叉樹二. 二叉樹的操作三. 二叉樹的性質(zhì)四. 二叉樹的存儲結(jié)構(gòu)一. 二叉樹的定義116.2 二叉樹一. 二叉樹的定義 一棵二叉樹是結(jié)點的一個有限集合，該集合（1）或者為空，（2）或者是由一個根結(jié)點組成（3）或者是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。126.2 二叉樹一. 二叉樹的定義ABCDEFGHK根結(jié)點左子樹右子樹特點：1）每個結(jié)點的度2；2）是有序樹6.2 二叉樹一. 二叉樹的定義圖6.3 二叉樹的五種不同形態(tài)13

5、6.2 二叉樹二. 二叉樹的操作14(1)InitBiTree(&T) (2)DestroyBiTree(&T)(3)CreateBiTree(&T，definition)(4)ClearBiTree(&T) (5)BiTreeEmpty(T)(6)BiTreeDepth(T) (7)Root(t) (8)Value(T,e) (9)Assign(T,&e,value)(10)Parent(T,e) (11)LeftChild(T,e) (12)RightChild(T,e) (13)InsertChild(T,p,LR,c) (14)DeleteChild(T,p,LR) (15)PreOr

6、derTraverse(T,Visit() (16)InOrderTraverse(T,Visit() (17)PostOrderTraverse(T,Visit()6.2 二叉樹三. 二叉樹的性質(zhì)15性質(zhì)1 若二叉樹的層次從1開始, 則在二叉樹的第 i 層最多有 2i-1個結(jié)點。(i 1) 證明用數(shù)學歸納法性質(zhì)2 深度為k的二叉樹最多有 2k-1個結(jié)點。(k 1) 證明用求等比級數(shù)前k項和的公式6.2 二叉樹三. 二叉樹的性質(zhì)16性質(zhì)3 對任何一棵二叉樹, 如果其葉結(jié)點個數(shù)為 n0, 度為2的非葉結(jié)點個數(shù)為 n2, 則有 n0n21證明： 若設(shè)度為1的結(jié)點有n1個，總結(jié)點個數(shù)為n，總邊數(shù)為e

7、，則根據(jù)二叉樹的定義， n = n0 + n1 + n2 e = 2n2 + n1 = n 1 因此，有 2n2 + n1 = n0 + n1 + n2 1 n2 = n0 - 1 n0 = n2 + 1 6.2 二叉樹三. 二叉樹的性質(zhì)17定義1 滿二叉樹(Full Binary Tree) 一棵深度為k且有2k -1個結(jié)點的二叉樹稱為滿二叉樹。如圖6.4（a）6.2 二叉樹三. 二叉樹的性質(zhì)18定義2 完全二叉樹(Complete Binary Tree) 深度為k，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。 如圖6.4

8、（b） 或者：若設(shè)二叉樹的深度為h，則共有h層。除第h層外，其它各層(0h-1)的結(jié)點數(shù)都達到最大個數(shù)，第h層從右向左連續(xù)缺若干結(jié)點。6.2 二叉樹三. 二叉樹的性質(zhì)19完全二叉樹的特點是：1）只允許最后一層有空缺結(jié)點且空缺在右邊，即葉子結(jié)點只能在層次最大的兩層上出現(xiàn)；2）對任一結(jié)點，如果其右子樹的深度為l，則其左子樹的深度必為l或l+1。 6.2 二叉樹三. 二叉樹的性質(zhì)20性質(zhì)4 具有n個結(jié)點的完全二叉樹的深度為 log2n +1證明：設(shè)完全二叉樹的深度為k，則有 2k-1 - 1 n 2k - 1 2k-1 n 2k 取對數(shù) k-1 log2n 1, 則 i 的雙親為i /2 若2*i

9、n, 則 i無左孩子；否則其左孩子結(jié)點為2i， 若2*i+1 n, 則 i無右孩子，否則其右孩子結(jié)點為2i+1，線性結(jié)構(gòu)樹形結(jié)構(gòu)第一個數(shù)據(jù)元素 (無前驅(qū)) 根結(jié)點 (無前驅(qū))最后一個數(shù)據(jù)元素 (無后繼)多個葉子結(jié)點 (無后繼) 其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼) 其它數(shù)據(jù)元素(一個前驅(qū)、多個后繼)雙親在同一層的結(jié)點ABCDEFGHIJKLM結(jié)點A的度：結(jié)點B的度：結(jié)點M的度：葉子：結(jié)點A的孩子：結(jié)點B的孩子：結(jié)點I的雙親：結(jié)點L的雙親：結(jié)點B，C，D為兄弟結(jié)點K，L為兄弟樹的度：結(jié)點A的層次：結(jié)點M的層次：樹的深度：結(jié)點F，G為堂兄弟結(jié)點A是結(jié)點F，G的祖先結(jié)點B的子孫：320B，C，D E，

10、F3K，L，F(xiàn)，G，M，I ，JD E14例E，K，L，F(xiàn)4思考：具有3個結(jié)點的二叉樹有多少種形態(tài)？例：112345678910121 i=6 其雙親為|i/2|= 3；其左孩子為2*i=12;i=1 是樹的根,無雙親;其左孩子為2*i=2,右孩子為2*i+1=3 .2*i=1812 2*i+1=1912 其無左、右孩子。2*i+1=1312 其無右孩子。i=9 其雙親為|i/2|= 4 ；6.2 二叉樹四、二叉樹的存儲結(jié)構(gòu)26順序存儲鏈式存儲6.2 二叉樹四、二叉樹的存儲結(jié)構(gòu)271. 順序存儲結(jié)構(gòu)（數(shù)組表示） 順序存儲二叉樹的具體方法是：在一棵具有n個結(jié)點的完全二叉樹中，從根結(jié)點開始編號為1

11、，自上到下，每層自左至右地給所有結(jié)點編號，這樣可以得到一個反映整個二叉樹結(jié)構(gòu)的線性序列；然后將完全二叉樹上編號為i的結(jié)點依次存儲在一維數(shù)組中下標為i-1的元素中。 6.2 二叉樹四、二叉樹的存儲結(jié)構(gòu)281. 順序存儲結(jié)構(gòu)（數(shù)組表示）#define MAX_TREE_SIZE 100typedef TElemType SqBiTreeMAX_TREE_SIZE;SqBiTree bt;二叉樹的順序存儲表示6.2 二叉樹四、二叉樹的存儲結(jié)構(gòu)291. 順序存儲結(jié)構(gòu)（數(shù)組表示）完全二叉樹的數(shù)組表示 一般二叉樹的數(shù)組表示6.2 二叉樹四、二叉樹的存儲結(jié)構(gòu)301. 順序存儲結(jié)構(gòu)（數(shù)組表示）由于一般二叉樹必

12、須仿照完全二叉樹那樣存儲，可能會浪費很多存儲空間，單支樹就是一個極端情況。一棵深度為k且只有k個結(jié)點的單支樹需要長度為2K-1的一維數(shù)組單支樹6.2 二叉樹四、二叉樹的存儲結(jié)構(gòu)312. 鏈式存儲結(jié)構(gòu) 鏈式存儲是使用鏈表來存儲二叉樹中的數(shù)據(jù)元素，鏈表中的一個結(jié)點相應(yīng)地存儲二叉樹中的一個結(jié)點。 常見的二叉樹的鏈式存儲結(jié)構(gòu)有兩種：二叉鏈表和三叉鏈表。6.2 二叉樹四、二叉樹的存儲結(jié)構(gòu)322. 鏈式存儲結(jié)構(gòu)二叉鏈表是指鏈表中的每個結(jié)點包含兩個指針域和一個數(shù)據(jù)域，分別用來存儲指向二叉樹中結(jié)點的左右孩子的指針及結(jié)點信息。三叉鏈表是指鏈表中的每個結(jié)點包含三個指針域和一個數(shù)據(jù)域，相比二叉鏈表多出的一個指針域則

13、用來指向該結(jié)點的雙親結(jié)點。6.2 二叉樹四、二叉樹的存儲結(jié)構(gòu)332. 鏈式存儲結(jié)構(gòu)6.2 二叉樹四、二叉樹的存儲結(jié)構(gòu)342.鏈式存儲結(jié)構(gòu)typedef struct BiTNodeTElemType data;Struct BiTNode *lchild,*rchild;BiTNode, *BiTree;二叉鏈表存儲表示6.2 二叉樹四、二叉樹的存儲結(jié)構(gòu)352. 鏈式存儲結(jié)構(gòu)圖6.8二叉樹鏈表表示的示例6.3 遍歷二叉樹和線索二叉樹36遍歷二叉樹線索二叉樹 “遍歷”是任何類型均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因為每個結(jié)點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，每個

14、結(jié)點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。 遍歷：順著某一條搜索路徑巡訪二叉樹中的結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。即找一個完整而有規(guī)律的走法，得到樹中所有結(jié)點的一個線性排列。 “訪問 ”的含義可以很廣， 如：輸出結(jié)點的信息等。6.3 遍歷二叉樹和線索二叉樹一、遍歷二叉樹6.3 遍歷二叉樹和線索二叉樹一、遍歷二叉樹38遍歷的結(jié)果：產(chǎn)生一個關(guān)于結(jié)點的線性序列。設(shè)訪問根結(jié)點記作 D，遍歷根的左子樹記作 L遍歷根的右子樹記作 R則可能的遍歷次序有：先序 DLR， 逆先序DRL中序 LDR， 逆中序RDL 后序 LRD， 逆后序RLD6.3 遍歷二叉樹和線索二叉樹一

15、、遍歷二叉樹39先序遍歷 (Preorder Traversal)先序遍歷二叉樹算法的框架是若二叉樹為空，則空操作；否則訪問根結(jié)點 (D)；先序遍歷左子樹 (L)；先序遍歷右子樹 (R)。ADBCD L RAD L R D L R BDCD L R先序遍歷序列：A B D C先序遍歷:6.3 遍歷二叉樹和線索二叉樹一、遍歷二叉樹41中序遍歷 (Inorder Traversal)中序遍歷二叉樹算法的框架是若二叉樹為空，則空操作；否則中序遍歷左子樹 (L)；訪問根結(jié)點 (D)；中序遍歷右子樹 (R)。ADBCL D RB L D RL D RADCL D R中序遍歷序列：B D A C中序遍歷:

16、6.3 遍歷二叉樹和線索二叉樹一、遍歷二叉樹43后序遍歷 (Postorder Traversal)后序遍歷二叉樹算法的框架是若二叉樹為空，則空操作；否則后序遍歷左子樹 (L)；后序遍歷右子樹 (R)；訪問根結(jié)點 (D)。ADBC L R DL R D L R DADCL R D后序遍歷序列： D B C A后序遍歷:BABCDEFGHK分 析：先序序列：中序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef4

17、7 由二叉樹的先序序列和中序序列可唯一地確定一棵二叉樹。例, 先序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 構(gòu)造二叉樹過程如下：6.3 遍歷二叉樹和線索二叉樹一、遍歷二叉樹48思考：已知二叉樹的先序序列和后序序列，問能否唯一確定這棵二叉樹？遍歷算法的遞歸描述void PreOrderTraverse (BiTree T, void ( *Visit)(TElemType e) / 先序遍歷二叉樹 if (T) Visit(T-data) ; / 訪問結(jié)點 PreOrder(T-lchild, Visit); / 遍歷左子樹 PreOrder(T-rchild, Visit)

18、;/ 遍歷右子樹 void pre(BiTree t) if (t!=NULL) printf (%dt,t-data); pre(t-lchild); pre(t-rchild); 主程序pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C遞歸算法的執(zhí)行過程T6.3 遍歷二

19、叉樹和線索二叉樹一、遍歷二叉樹51遍歷二叉樹的非遞歸算法中序遍歷在遍歷左子樹之前，先把根結(jié)點入棧，當左子樹遍歷結(jié)束后，從棧中彈出、訪問，再遍歷右子樹52中序遍歷的非遞歸算法Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType e) InitStack(S);/根指針進棧 Push(S, T); while (!StackEmpty(S) while (GetTop(S, p) & p) Push(S, p-lchild); /向左走到盡頭 Pop(S, p);/空指針退棧 if (!StackEmpty(S) /訪問結(jié)點，向右一步

20、 Pop(S, p); if (!Visit(p-data) return ERROR; Push(S, p-rchild); return OK;6.3 遍歷二叉樹和線索二叉樹6.3 遍歷二叉樹和線索二叉樹53先序建立二叉樹的遞歸算法（算法6.4）Status CreateBiTree(BiTree &T) char ch;scanf(%c,&ch); if (ch= ) T=NULL; else if (!(T=(BiTNode*)malloc(sizeof(BiTNode) exit(OVERFLOW); T-data = ch; CreateBiTree(T-lchild); Crea

21、teBiTree(T-rchild);return OK;6.3 遍歷二叉樹和線索二叉樹二、線索二叉樹（穿線樹、線索樹） (Threaded Binary Tree)54 1、問題的提出2、線索二叉樹定義3、在線索二叉樹上找前驅(qū)和后繼的規(guī)律4、如何建立中序線索二叉樹？5、線索二叉樹的遍歷算法二、 線索二叉樹55 如何找二叉樹上結(jié)點的前驅(qū)和后繼？遍歷二叉樹的結(jié)果是， 求得結(jié)點的一個線性序列。ABCDEFGHK例如:先序序列: A B C D E F G H K中序序列: B D C A H G K F E后序序列: D C B H K G F E A56 ADEBCFroot先序遍歷： A B

22、C D E F 利用二叉鏈表結(jié)點中的n+1個空鏈域： 如何在二叉樹上記錄結(jié)點的前驅(qū)和后繼信息？57 lchild data rchildltagrtagNULLABDCEF010000111111增加標志域如何區(qū)別是孩子指針還是前驅(qū)或后繼指針? 0link1thread6.3 遍歷二叉樹和線索二叉樹二、線索二叉樹（穿線樹、線索樹）58 1、問題的提出2、線索二叉樹定義3、在線索二叉樹上找前驅(qū)和后繼的規(guī)律4、如何建立中序線索二叉樹？5、線索二叉樹的遍歷算法6.3 遍歷二叉樹和線索二叉樹二、線索二叉樹（穿線樹、線索樹）59 線索：指向該線性序列中的“前驅(qū)”和“后繼” 的指針。線索鏈表：包含 “線索

23、” 的存儲結(jié)構(gòu)。 線索二叉樹：加上線索的二叉樹。lchild data rchildltagrtag6.3 遍歷二叉樹和線索二叉樹二、線索二叉樹（穿線樹、線索樹）60 線索二叉樹，即在一般二叉樹的基礎(chǔ)上，對每個結(jié)點進行考察。若其左子樹非空，則其左指針不變，仍指向左子樹；若其左子樹為空，則讓其左指針指向某種遍歷順序下該結(jié)點的前驅(qū)；若其右子樹非空，則其右指針不變，仍指向右子樹；若其右子樹為空，則讓其右指針指向某種遍歷順序下該結(jié)點的后繼。如果規(guī)定遍歷順序為前序，則稱為前序線索二叉樹；如果規(guī)定遍歷順序為中序，則稱為中序線索二叉樹；如果規(guī)定遍歷順序為后序，則稱為后序線索二叉樹。6.3 遍歷二叉樹和線索二

24、叉樹二、線索二叉樹（穿線樹、線索樹）61標志域：LTag = 0, lchild為左孩子指針LTag = 1, lchild為前驅(qū)線索RTag = 0, rchild為右孩子指針RTag = 1, rchild為后繼指針6.3 遍歷二叉樹和線索二叉樹二、線索二叉樹（穿線樹、線索樹）62線索二叉樹的類型描述typedef enum PointerTag Link,Thread;/Link=0：指針，指向孩子結(jié)點/Thread=1：線索，指向前驅(qū)或后繼結(jié)點typedef struct BiThrNode TElemType data;struct BiThrNode *lchild,*rchild

25、;PointerTag LTag,RTag; BiThrNode, *BiThrTree;BiThrTree T；6.3 遍歷二叉樹和線索二叉樹二、線索二叉樹（穿線樹、線索樹） (Threaded Binary Tree)63中序線索二叉樹中序遍歷： B C A D F EABDCEF010000111111NULLNULL646.3 遍歷二叉樹和線索二叉樹二、線索二叉樹（穿線樹、線索樹）65 1、問題的提出2、線索二叉樹定義3、在線索二叉樹上找前驅(qū)和后繼的規(guī)律4、如何建立中序線索二叉樹？5、線索二叉樹的遍歷算法1).在先序線索二叉樹找前驅(qū)和后繼2).在中序線索二叉樹找前驅(qū)和后繼3).在后序線

26、索二叉樹找前驅(qū)和后繼 4). 線索二叉樹上找前驅(qū)和后繼的規(guī)律如果是非葉子結(jié)點，則： 如果有左孩子，則左孩子是其后繼； 如果無左孩子，則右孩子是其后繼；如果是葉子結(jié)點，則右線索所指結(jié)點為后繼； 如果無左孩子，則左線索所指結(jié)點為前驅(qū)；否則需要遍歷；NULLABDCEF010000111111先序線索二叉樹A B C D E F找后繼：找前驅(qū)：1).在先序線索二叉樹找前驅(qū)和后繼 若無右孩子，則右線索所指結(jié)點為后繼； 否則，右孩子的“最左下”孩子為后繼；若無左孩子，則左線索所指結(jié)點為前驅(qū)；否則，左孩子的“最右下”孩子為前驅(qū)；找后繼：找前驅(qū)：NULLABDCEF000001101111NULL中序線索二

27、叉樹C H B A D F EH112).在中序線索二叉樹找前驅(qū)和后繼如果無右孩子，則右線索所指結(jié)點為后繼；否則需要遍歷；如果有右孩子，則右孩子是其前驅(qū)；如果無右孩子，但有左孩子，則左孩子為前驅(qū)；如果無左孩子，則左線索所指結(jié)點為前驅(qū)；后序線索二叉樹C B F E D A找后繼：找前驅(qū)：ABDCEF010000111111NULL3).在后序線索二叉樹找前驅(qū)和后繼 4). 線索二叉樹上找前驅(qū)和后繼的一般規(guī)律先序線索二叉樹找后繼方便， 找前驅(qū)可能需要遍歷。中序線索二叉樹找前驅(qū)和后繼都方便后序線索二叉樹找前驅(qū)方便， 找后繼可能需要遍歷。6.3 遍歷二叉樹和線索二叉樹二、線索二叉樹（穿線樹、線索樹）7

28、1 1、問題的提出2、線索二叉樹定義3、在線索二叉樹上找前驅(qū)和后繼的規(guī)律4、如何建立中序線索二叉樹？（自學）5、線索二叉樹的遍歷算法6.3 遍歷二叉樹和線索二叉樹二、線索二叉樹（穿線樹、線索樹）72 1、問題的提出2、線索二叉樹定義3、在線索二叉樹上找前驅(qū)和后繼的規(guī)律4、如何建立中序線索二叉樹？5、線索二叉樹的遍歷算法5、中序線索二叉樹的遍歷算法 如果已經(jīng)通過遍歷(前序，中序和后序) 得到線索二叉樹。 那么，對線索化的二叉樹進行遍歷就比對一般二叉樹進行遍歷更加有效和方便。帶頭結(jié)點的中序線索二叉樹ABDCEF010000111111根結(jié)點NULLNULL B C A D F E01頭結(jié)點T 中序

29、線索二叉樹的遍歷算法 中序遍歷的第一個結(jié)點 ？ 在中序線索二叉樹中結(jié)點的后繼 ？左子樹上處于“最左下”（沒有左子樹）的結(jié)點若無右子樹，則右線索所指結(jié)點為后繼否則，右子樹的“最左下”孩子為后繼； 結(jié)束的條件? 樹空或者指針指向頭結(jié)點Status InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; / T指向頭結(jié)點，p指向根結(jié)點 while (p != T) / 空樹或遍歷結(jié)束時，p=T while (p-LTag=Link) p = p-lchild; / 最左下結(jié)點 Visit(p-data) ；

30、/ 訪問最左下結(jié)點 while (p-RTag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data); / 訪問后繼結(jié)點 p = p-rchild; / p進至其右子樹根或頭結(jié)點 return OK； / InOrderTraverse_Thr6.4 樹和森林77 1、樹的三種存儲結(jié)構(gòu)2、森林與二叉樹的轉(zhuǎn)換3、樹和森林的遍歷（自學）樹的三種存儲結(jié)構(gòu)（1）雙親表示法（2）孩子鏈表表示法（3）孩子-兄弟表示法ABCDEFGr=0n=70 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5data parent（1）雙親表示法: 樹

31、結(jié)點 typedef struct PTNode TElemType data; int parent; / 雙親位置域 PTNode; data parent#define MAX_TREE_SIZE 100結(jié)點結(jié)構(gòu):C語言的類型描述:typedef struct PTNode nodes MAX_TREE_SIZE; int r, n； / 根結(jié)點的位置和結(jié)點個數(shù) PTree;樹結(jié)構(gòu):0 A1 B 2 C 3 D 4 E 5 F 6 G 0 1 2 3 4 5 6 r = 0 n = 7ABCDEFG64 5 1 2 3（2）孩子鏈表表示法:1。樹2。孩子鏈表的頭結(jié)點3。孩子鏈表結(jié)點 da

32、ta firstchildchild nextchildtypedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 結(jié)點數(shù)和根結(jié)點的位置 CTree;樹:typedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子鏈表結(jié)點: typedef struct TElemType data; ChildPtr firstchild; / 孩子鏈的頭指針 CTBox;孩子鏈表 頭結(jié)點:ABCDEFG二叉樹 AB C E D F G ABCEDFG樹二叉鏈表表示 firstchild d

33、ata nextsibling（3）樹的孩子-兄弟表示法C語言的類型描述:typedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;二叉結(jié)點: firstchild data nextsibling雙親表示法用結(jié)構(gòu)數(shù)組樹的順序存儲方式類型定義：找雙親方便，找孩子難孩子鏈表表示法順序和鏈式結(jié)合的表示方法找孩子方便，找雙親難孩子兄弟表示法找孩子容易，若增加parent域，則找雙親也較方便。森林與二叉樹的轉(zhuǎn)換（1） 樹轉(zhuǎn)換為二叉樹（2）二叉樹還原成樹（3） 森林轉(zhuǎn)換成二叉樹轉(zhuǎn)換對

34、應(yīng)的二叉樹樹ABCDE二叉鏈表存儲表示ABCEDABCEDABCEAABCED圖6.16舉例：ABECDFGHIABEDCIIFG（1） 樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹的步驟:加線：在兄弟結(jié)點之間加一連線；抹線：對任何結(jié)點，除了其最左的孩子 外，抹掉該結(jié)點原先與其孩子之 間的連線；旋轉(zhuǎn)：將水平的連線和原有的連線，以 樹根結(jié)點為軸心，按順時針方向 粗略地旋轉(zhuǎn)450。舉例：ABEDCI HFGABECDFGH I（2） 二叉樹還原成樹二叉樹還原成樹的步驟加線：如果p結(jié)點是雙親結(jié)點的左孩子; 則將p結(jié)點的右孩子,右孩子的右 孩子,沿著右分支搜索到的 所有右孩子都分別與p結(jié)點的雙 親用線連接起來;抹線：

35、抹掉原二叉樹中所有雙親結(jié)點與 右孩子的連線；調(diào)整： 將結(jié)點按層次排列,形成樹的結(jié)構(gòu).ABDCEFIHGJABCDHGIJEFABCDEFHGIJ舉例：（3） 森林轉(zhuǎn)換成二叉樹 森林轉(zhuǎn)換成二叉樹的步驟:轉(zhuǎn)換：將森林中的每一棵樹轉(zhuǎn)換成二 叉樹;連線：將各棵轉(zhuǎn)換后的二叉樹的根結(jié) 點相連；旋轉(zhuǎn)：將添加的水平線和原有的連線, 以第一棵樹的根結(jié)點為軸心,按 順時針方向旋轉(zhuǎn)450。森林轉(zhuǎn)化成二叉樹的規(guī)則 若森林F為空，即n = 0，則 對應(yīng)的二叉樹B為空二叉樹。 若F不空，則 對應(yīng)二叉樹B的根root (B)是F中第一棵樹T1的根root (T1)； 其左子樹為B (T11, T12, , T1m)，其中，

36、T11, T12, , T1m是root (T1)的子樹； 其右子樹為B (T2, T3, , Tn)，其中，T2, T3, , Tn是除T1外其它樹構(gòu)成的森林。6.6 赫夫曼樹及其應(yīng)用95 最優(yōu)樹的定義如何構(gòu)造最優(yōu)樹最優(yōu)樹的應(yīng)用1、最優(yōu)樹的定義樹的路徑長度： 樹的根到每個結(jié)點的路徑長度之和。 路徑長度： 路徑上分支的數(shù)目。 路徑： 從樹中一個結(jié)點到另一個結(jié)點之間的分支所構(gòu)成的通路 。 結(jié)點的帶權(quán)路徑長度： 從樹根到該結(jié)點之間的長度與結(jié)點權(quán)值的乘積 ( l * w ) 。 樹的帶權(quán)路徑長度： 樹中所有葉子結(jié)點的帶權(quán)路徑長度之和 WPL(T) = wk lk 27 9 75492WPL(T)=

37、72+52+23+43+92 =60WPL(T)= 74+94+53+42+21 =89 54 在所有含 n 個葉子結(jié)點、并帶相同權(quán)值的 m 叉樹中，必存在一棵其帶權(quán)路徑長度取最小值的樹，稱為“最優(yōu)樹”。最優(yōu)樹可能不止一個！具有不同帶權(quán)路徑長度的擴充二叉樹赫夫曼樹 帶權(quán)路徑長度達到最小的二叉樹即為赫夫曼樹（最優(yōu)二叉樹）。 在赫夫曼樹中，權(quán)值大的結(jié)點離根最近。6.6 赫夫曼樹及其應(yīng)用101 最優(yōu)樹的定義如何構(gòu)造最優(yōu)樹最優(yōu)樹的應(yīng)用赫夫曼算法 如何構(gòu)造一棵赫夫曼樹 (1) 由給定的n個權(quán)值w0, w1, w2, , wn-1，構(gòu)造具有n棵二叉樹的森林F = T0, T1, T2, , Tn-1，其中

38、每一棵二叉樹Ti只有一個帶有權(quán)值wi的根結(jié)點，其左、右子樹均為空。 (2) 重復以下步驟, 直到F中僅剩下一棵樹為止： 在F中選取兩棵根結(jié)點的權(quán)值最小的二叉樹, 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。 在F中刪去這兩棵二叉樹。 把新的二叉樹加入F。例如: 已知權(quán)值 W= 5, 6, 2, 9, 7 956275276976713952767139527952716671329哈夫曼樹 wpl6272532392 65可以證明哈夫曼樹是最優(yōu)樹例如: 已知權(quán)值 W= 5, 6, 2, 7, 7,7 75627WPL = 63+7472142

39、18710885276713342077147671334205277714WPL = 63+7373142 18710886.6 赫夫曼樹及其應(yīng)用106 最優(yōu)樹的定義如何構(gòu)造最優(yōu)樹最優(yōu)樹的應(yīng)用在解決某些判定問題時，利用赫夫曼樹可以得到最佳判定算法 用于通訊和數(shù)據(jù)傳送時的赫夫曼編碼3、最優(yōu)樹的應(yīng)用 假設(shè)電文由A,B,C,D四個字符組成.它們的編碼分別為00,01,10和11. 則電文ABACCDA 的編碼為00010010101100, 總長為14位. 為減少編碼長度,重新設(shè) A,B,C,D四個字符的編碼為0,00,1和01. 則電文編碼為000011010,總長為9位.3、最優(yōu)樹的應(yīng)用ABA

40、0000AAAABBBAA 前綴編碼指的是，任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。0 00 1 01 0 100 101 11 A B C D00 01 10 11 是前綴編碼不是前綴編碼是前綴編碼(2) 0 00 1 01 不是前綴編碼(3) 0 100 101 11 是前綴編碼A B C D(1) 00 01 10 11 是前綴編碼ABCD01110000011011(1)ABCD011011010010101(3)BCD010100011(2)AABCD01110000011011(1)ABCD011011010010101(3)那一種電報編碼的總長更短？1。假設(shè)概

41、率相同,且均為k wpl(1)=k*2*48k wpl(3)=k*1+k*3*2+k*29k2。概率不同,且A為0.5,B為0.1,C為0.1,D為0.3wpl(1)=0.5*2+0.1*2*2+0.3*22Wpl(3)=0.5*1+0.1*2*3+0.3*21.7 利用赫夫曼樹可以構(gòu)造一種不等長的二進制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，使所傳電文的總長度最短。舉例: 已知某系統(tǒng)在通訊聯(lián)絡(luò)中只可能 出現(xiàn)八種字符A,B,C,D,E,F,G,H, 其概率 分別為: 0.05, 0.29, 0.07, 0.08, 0.14, 0.23,0.03,0.11 試設(shè)計赫夫曼編碼.設(shè)權(quán) w

42、= 5, 29, 7, 8, 14, 23, 3, 11 A B C D E F G H設(shè)權(quán) w = 5, 29, 7, 8, 14, 23, 3, 11 29 5 7 8 3142311 5 38 8 71511191429234229581000000111100011100010011001111011011101111舉例: 已知某系統(tǒng)在通訊聯(lián)絡(luò)中只可能 出現(xiàn)八種字符A,B,C,D,E,F,G,H, 其概率 分別為: 0.05, 0.29, 0.07, 0.08, 0.14, 0.23,0.03,0.11 試設(shè)計赫夫曼編碼.赫夫曼編碼: 0110, 10, 1110, 1111, 11

43、0, 00, 0111, 010設(shè)權(quán) w = 5, 29, 7, 8, 14, 23, 3, 11 A B C D E F G H數(shù)據(jù)文件壓縮: 已知一個由A,B,C,D,E,F,G,H等八個字符組成的文件包含100個字符，如果對這八個字符都按等長編碼： 000,001,010,011,100,101,110，111 則文件包含的總位數(shù)為：1003300 位 現(xiàn)已知八個字符在文件中出現(xiàn)的個數(shù)分別為: 5,29,7,8,14,23,3,11 如果采用赫夫曼編碼: 0110,10,1110,1111,110,00,0111,010 則文件的總位數(shù)為： 542927484143232+34+113=271 位 壓縮率為10typedef struct unsigned int weight;unsigned int parent,lchild,rchild; HTNode, *HuffmanTree;typedef char *HuffmanCode;建立赫夫曼樹及求赫夫曼編碼的算法void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w, int n