數(shù)據(jù)結(jié)構(gòu)-第六章-樹與二叉樹課件

1、第六章 樹和二叉樹樹的概念和基本術(shù)語 二叉樹 二叉樹遍歷二叉樹的計數(shù) 樹與森林霍夫曼樹 第六章 樹和二叉樹樹的概念和基本術(shù)語 樹的概念和基本術(shù)語樹的定義 樹是由 n (n 0) 個結(jié)點的有限集合。如果 n = 0，稱為空樹；如果 n 0，則 有且僅有一個特定的稱之為根(Root)的結(jié)點，它只有直接后繼，但沒有直接前驅(qū)； 當n 1，除根以外的其它結(jié)點劃分為 m (m 0) 個互不相交的有限集 T1, T2 , Tm，其中每個集合本身又是一棵樹，并且稱為根的子樹(SubTree)。樹的概念和基本術(shù)語樹的定義 ACGBDEFKLHMIJ例如A只有根結(jié)點的樹有13個結(jié)點的樹其中：A是根；其余結(jié)點分成三

2、個互不相交的子集，T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M,T1,T2,T3都是根A的子樹，且本身也是一棵樹ACGBDEFKLHMIJ例如A只有根結(jié)點的樹有13個結(jié)點的樹的基本術(shù)語1層2層4層3層height= 4ACGBDEFKLHMIJ結(jié)點結(jié)點的度葉結(jié)點分支結(jié)點子女雙親兄弟祖先子孫結(jié)點層次樹的深度樹的度有序樹無序樹森林樹的基本術(shù)語1層2層4層3層heightACGBDEFKLH結(jié)點：一個數(shù)據(jù)元素及指向其子樹的分支。結(jié)點的度：結(jié)點擁有的子樹個數(shù)。葉結(jié)點：度為零的結(jié)點。子女：結(jié)點子樹的根。兄弟：同一結(jié)點子女。祖先：根到該結(jié)點路徑上的所有結(jié)點。子孫：某結(jié)點為根的子樹上

3、的任意結(jié)點。結(jié)點層次：從根開始，根為第一層，根的子女為第二層，以此類推。樹的深度（高度）：樹中結(jié)點的最大層次數(shù)。有序樹：樹中結(jié)點的子樹由左向右有序。森林：m(m 0)棵互不相交的樹。結(jié)點：一個數(shù)據(jù)元素及指向其子樹的分支。二叉樹 (Binary Tree)定義五種形態(tài)一棵二叉樹是結(jié)點的一個有限集合，該集合或者為空，或者是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。LLRR特點每個結(jié)點至多只有兩棵子樹（二叉樹中不存在度大于2的結(jié)點）二叉樹 (Binary Tree)定義五種形態(tài)一棵二叉樹是性質(zhì)1 在二叉樹的第 i 層上至多有 2i 1個結(jié)點。(i 1) 證明用歸納法證明：當

4、i=1時，只有根結(jié)點，2 i-1=2 0=1。假設(shè)對所有j，ij1，命題成立，即第j層上至多有2 j-1 個結(jié)點。由歸納假設(shè)第i-1 層上至多有 2i 2個結(jié)點。由于二叉樹的每個結(jié)點的度至多為2，故在第i層上的最大結(jié)點數(shù)為第i-1層上的最大結(jié)點數(shù)的2倍，即2* 2i 2= 2 i-1。性質(zhì)性質(zhì)1 在二叉樹的第 i 層上至多有 2i 1個結(jié)點。(性質(zhì)2 深度為 k 的二叉樹至多有 2k -1個結(jié)點(k 1)。證明：由性質(zhì)1可見，深度為k的二叉樹的最大結(jié)點數(shù)為 20 + 21 + + 2k-1 = 2k -1性質(zhì)2 深度為 k 的二叉樹至多有 2k -1個結(jié)點(k 性質(zhì)3 對任何一棵二叉樹T, 如

5、果其葉結(jié)點數(shù)為 n0, 度為2的結(jié)點數(shù)為 n2,則n0n21.證明：若度為1的結(jié)點有 n1 個，總結(jié)點個數(shù)為 n，總邊數(shù)為 e，則根據(jù)二叉樹的定義， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1 性質(zhì)3 對任何一棵二叉樹T, 如果其葉結(jié)點數(shù)為 n0, 定義1 滿二叉樹 (Full Binary Tree) 一棵深度為k且有2k -1個結(jié)點的二叉樹稱為滿二叉樹。兩種特殊形態(tài)的二叉樹621754389101113141512滿二叉樹定義1 滿二叉樹 (Ful

6、l Binary Tree) 兩2154367216543非完全二叉樹定義2 完全二叉樹 (Complete Binary Tree) 若設(shè)二叉樹的高度為h，則共有h層。除第 h 層外，其它各層 (0 h-1) 的結(jié)點數(shù)都達到最大個數(shù)，第 h 層從右向左連續(xù)缺若干結(jié)點，這就是完全二叉樹。621754389101112完全二叉樹2154367216543非完全二叉樹定義2 完全二叉樹 性質(zhì)4 具有 n 個結(jié)點的完全二叉樹的深度為log2(n) 1 證明：設(shè)完全二叉樹的深度為 h，則根據(jù)性質(zhì)2和完全二叉樹的定義有2h1 - 1 n 2h - 1或 2h1 n 2h取對數(shù) h1 log2n 0, 則

7、 i 的雙親為(i -1)/2 若2*i+1 n, 則 i 的左子女為 2*i+1，若2*i+2 leftChild ); Visit( T-data); InOrder ( T-rightChild ); 中序遍歷二叉樹的遞歸算法void InOrder ( BinTreeNode *T 前序遍歷二叉樹算法的定義：若二叉樹為空，則空操作；否則訪問根結(jié)點 (V)；前序遍歷左子樹 (L)；前序遍歷右子樹 (R)。遍歷結(jié)果 - + a * b - c d / e f前序遍歷 (Preorder Traversal)-/+*abcdef前序遍歷二叉樹算法的定義：前序遍歷 (Preorder Tr前序

8、遍歷二叉樹的遞歸算法void PreOrder ( BinTreeNode *T ) if ( T != NULL ) Visit( T-data); PreOrder ( T-leftChild ); PreOrder ( T-rightChild ); 前序遍歷二叉樹的遞歸算法后序遍歷二叉樹算法的定義：若二叉樹為空，則空操作；否則后序遍歷左子樹 (L)；后序遍歷右子樹 (R)；訪問根結(jié)點 (V)。遍歷結(jié)果 a b c d - * + e f / -后序遍歷 (Postorder Traversal)-/+*abcdef后序遍歷二叉樹算法的定義：后序遍歷 (Postorder T后序遍歷二叉

9、樹的遞歸算法：void PostOrder ( BinTreeNode * T ) if ( T != NULL ) PostOrder ( T-leftChild ); PostOrder ( T-rightChild ); Visit( T-data); 后序遍歷二叉樹的遞歸算法：二叉樹遍歷應用以遞歸方式建立二叉樹。輸入結(jié)點值的順序必須對應二叉樹結(jié)點前序遍歷的順序。并約定以輸入序列中不可能出現(xiàn)的值作為空結(jié)點的值以結(jié)束遞歸, 此值在RefValue中。例如用“”或用“-1”表示字符序列或正整數(shù)序列空結(jié)點。按前序建立二叉樹(遞歸算法)二叉樹遍歷應用以遞歸方式建立二叉樹。按前序建立二叉樹(遞歸算

10、如圖所示的二叉樹的前序遍歷順序為A B C D E G F ABCDEGF如圖所示的二叉樹的前序遍歷順序為ABCDEGF Status CreateBiTree ( BiTree& T ) scanf(&ch); /讀入根結(jié)點的值 if ( ch= ) T=NULL; else if ( !(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); /建立根結(jié)點 T-data = ch; CreateBiTree ( T-leftChild ); CreateBiTree ( T-rightChild ); return OK;/CreateBiT

11、ree Status CreateBiTree ( 2.計算二叉樹結(jié)點個數(shù)(遞歸算法)2.計算二叉樹結(jié)點個數(shù)(遞歸算法)int Count ( BinTreeNode *T ) if ( T = NULL ) return 0; else return 1 + Count ( T-leftChild ) + Count ( T-rightChild );2.計算二叉樹結(jié)點個數(shù)(遞歸算法)int Count ( BinTreeNode *T ) 3.求二叉樹中葉子結(jié)點的個數(shù)3.求二叉樹中葉子結(jié)點的個數(shù)int Leaf_Count(Bitree T) /求二叉樹中葉子結(jié)點的數(shù)目if(!T) ret

12、urn 0; /空樹沒有葉子 elseif(!T-lchild&!T-rchild) return 1; /葉子結(jié)點else return Leaf_Count(T-lchild)+Leaf_Count(T-rchild); /左子樹的葉子數(shù)加上右子樹的葉子數(shù)3.求二叉樹中葉子結(jié)點的個數(shù)int Leaf_Count(Bitree T)3.求二叉4.求二叉樹高度(遞歸算法)4.求二叉樹高度(遞歸算法)int Height ( BinTreeNode * T ) if ( T = NULL ) return 0; elseint m = Height ( T-leftChild );int n =

13、 Height ( T-rightChild ) ); return (m n) ? m+1 : n+1; 4.求二叉樹高度(遞歸算法)int Height ( BinTreeNode * T )5.復制二叉樹(遞歸算法)5.復制二叉樹(遞歸算法)5.復制二叉樹(遞歸算法)BiTNode* Copy( BinTreeNode * T ) if ( T = NULL ) return NULL;if(!(Temp=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); Temp-data=T-data;Temp- leftChild = Copy( T

14、-leftChild ); Temp- rightChild = Copy(T-rightChild ); return Temp;5.復制二叉樹(遞歸算法)BiTNode* Copy( B6.判斷二叉樹等價(遞歸算法)6.判斷二叉樹等價(遞歸算法)6.判斷二叉樹等價(遞歸算法)int Equal( BinTreeNode *a, BinTreeNode *b) if ( a = NULL & b = NULL ) return 1; if ( a != NULL & b != NULL & a-data=b-data & equal( a-leftChild, b-leftChild) &

15、equal( a-rightChild, b-rightChild) ) return 1; return 0;/如果a和b的子樹不等同，則函數(shù)返回06.判斷二叉樹等價(遞歸算法)int Equal( Bin中序遍歷二叉樹(非遞歸算法)用棧實現(xiàn)baabcdeadaaa b入棧b退棧訪問d入棧d退棧訪問e 退棧 訪問ecc?？?a退棧訪問c e 入棧c 退棧 訪問中序遍歷二叉樹(非遞歸算法)用棧實現(xiàn)babcdeadaa b void InOrder ( BinTree T ) stack S; InitStack( &S ); /遞歸工作棧 Push(S,T); /初始化 while ( !St

16、ackEmpty(S) while(GetTop(S,p)&p) Push(S, p-lchild);Pop(S,p);if ( !StackEmpty(S) ) /棧非空 Pop(S, p); /退棧 Visit(p-data); /訪問根 Push(S, p-rchild); /if /while return ok;abcde void InOrder ( BinTree 前序遍歷二叉樹(非遞歸算法)用棧實現(xiàn)acabcdedcc訪問a進棧c左進b訪問b進棧d左進空退棧d訪問d左進空退棧c訪問c左進e訪問e左進空退棧結(jié)束前序遍歷二叉樹(非遞歸算法)用棧實現(xiàn)acabcdedc訪問訪void

17、PreOrder( BinTree T ) stack S; InitStack(S); /遞歸工作棧 BinTreeNode * p = T; Push (S, NULL); while ( p != NULL ) Visit(p-data); if ( p-rightChild != NULL ) Push ( S, p-rightChild ); if ( p-leftChild != NULL ) p = p-leftChild;/進左子樹 else Pop( S, p ); abcdevoid PreOrder( BinTree T ) ab后序遍歷二叉樹(非遞歸算法)用棧實現(xiàn)后序遍

18、歷時使用的棧的結(jié)點定義typedef struct BinTreeNode *ptr; /結(jié)點指針 enum tag L, R ; /該結(jié)點退棧標記 StackNode; 根結(jié)點的 tag = L，表示從左子樹退出, 訪問右子樹。 tag = R, 表示從右子樹退出, 訪問根。ptr tagL,R 后序遍歷二叉樹(非遞歸算法)用棧實現(xiàn)后序遍歷時使用的棧的結(jié)點void PostOrder ( BinTree T ) stack S; InitStack(S); StackNode w; BinTreeNode * p = T; do while ( p != NULL ) /向左子樹走 w.pt

19、r = p; w.tag = L; Push (S, w); p = p-leftChild; int continue = 1; /繼續(xù)循環(huán)標記void PostOrder ( BinTree T ) while ( continue & !StackEmpty(S) ) Pop (S, w); p = w.ptr; switch ( w.tag ) /判斷棧頂tag標記 case L : w.tag = R; Push (S, w); continue = 0; p = p-rightChild; break; case R : Visit( p-data); while ( p != N

20、ULL | !StackEmpty(S) ); while ( continue & !StackE練習:交換二叉樹各結(jié)點的左、右子樹(遞歸算法)練習:交換二叉樹各結(jié)點的左、右子樹(遞歸算法) 練習:交換二叉樹各結(jié)點的左、右子樹(遞歸算法)void unknown ( BinTreeNode * T ) BinTreeNode *p = T, *temp; if ( p != NULL ) temp = p-leftChild; p-leftChild = p-rightChild; p-rightChild = temp; unknown ( p-leftChild ); unknown (

21、 p-rightChild ); 練習:交換二叉樹各結(jié)點的左、右子樹(遞歸算法)void void unknown ( BinTreeNode * T ) BinTreeNode *p = T, *temp; while ( p != NULL ) temp = p-leftChild; p-leftChild = p-rightChild; p-rightChild = temp; unknown ( p-leftChild ); p = p-rightChild; 不用棧消去遞歸算法中的第二個遞歸語句void unknown ( BinTreeNode * T 使用棧消去遞歸算法中的兩個遞

22、歸語句void unknown ( BinTreeNode * T ) BinTreeNode *p, *temp; stack S; InitEmpty (&S); if ( T != NULL ) push(&S, T); while ( ! StackEmpty(&S) ) Pop(&S, p); /棧中退出一個結(jié)點 temp = p-leftChild; /交換子女 p-leftChild = p-rightChild; p-rightChild = temp; 使用棧消去遞歸算法中的兩個遞歸語句void if ( p-rightChild != NULL ) push (&S, p-

23、rightChild ); if ( p-leftChild != NULL ) push (&S, p-leftChild ); if ( p-rightChild !=對二叉樹遍歷的過程實質(zhì)上是對一個非線性結(jié)構(gòu)進行線性化的操作.以二叉鏈表為存儲結(jié)構(gòu)時,結(jié)點的左右孩子可以直接找到,但不能直接找到結(jié)點的前驅(qū)和后繼,而結(jié)點的前驅(qū)和后繼只有在遍歷二叉樹的過程中才能得到.用二叉鏈表表示的二叉樹中,n個結(jié)點的二叉樹有n+1個空鏈域，可利用這些空鏈域存儲結(jié)點的前驅(qū)或后繼。線索二叉樹 (Threaded Binary Tree)對二叉樹遍歷的過程實質(zhì)上是對一個非線性結(jié)構(gòu)進行線性化的操作.LeftThrea

24、d=0, LeftChild為左子女指針LeftThread=1, LeftChild為前驅(qū)線索RightThread=0, RightChild為右子女指針RightThread=1, RightChild為后繼指針LeftChildRightChilddataLeftThreadRightThread結(jié)點結(jié)構(gòu)LeftThread=0, LeftChild為左子typedef enum Link,Thread PointerTag;/PointerTag為標志，Link=0代表指針，Thread=1代表線索typedef struct BiThrNodeTElemType data;stru

25、ct BiThrNode *lchild, *rchild;PointerTag LTag,RTag;BiThrNode, *BiThrTree;typedef enum Link,Thread Poi中序線索二叉樹BDAEC中序線索二叉樹BDAEC中序線索二叉樹后繼：結(jié)點標志為1時，其右指針為其后繼；結(jié)點標志為0時，其右子樹最左下結(jié)點為其后繼。前驅(qū)：結(jié)點標志為1時，其左指針為其前驅(qū)；結(jié)點標志為0時，其左子樹最右下結(jié)點為其前驅(qū)。abcde中序線索二叉樹abcde后序線索二叉樹后繼：(1)根的后繼為空。 (2)如果結(jié)點是雙親的右孩子或是左孩子但雙親沒有右子樹，則后繼是其雙親。 (3)如果結(jié)點是雙

26、親的左孩子且雙親有右子樹，則后繼是雙親右子樹上先遍歷到的結(jié)點?？傊?，如果二叉樹的應用主要是遍歷或查找結(jié)點的前驅(qū)和后繼則使用線索二叉樹更為合適。后序線索二叉樹Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(TElemType e)p=T-lchild;while(p!=T)while(p-LTag=Link)p=p-lchild;if(!Visit(p-data) return ERROR;while(p-RTag=Thread & p-rchild!=T)p=p-rchild; Visit(p-data);p=p-rchild;/

27、InOrderTraverse_ThrStatus InOrderTraverse_Thr(BiT數(shù)據(jù)結(jié)構(gòu)-第六章-樹與二叉樹課件void InThreading(BiThrTree p)if(p)InThreading(p-lchild);/左子樹線索化if(!p-lchild) p-LTag=Thread; p-lchild=pre;/建立前驅(qū)線索if(!pre-rchild) pre-RTag=Thread; pre-rchild=p;/建立后繼線索pre=p;/保持pre為下一結(jié)點的前驅(qū)InThreading(p-rchild); /右子樹線索化/InThreading通過中序遍歷建立

28、中序線索化二叉樹void InThreading(BiThrTree p)Status InOrderThreading(BiThrTree &Thrt, BiThrTree T)/中序遍歷并線索化二叉樹，Thrt為頭結(jié)點if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW); /建頭結(jié)點Thrt-LTag=Link;Thrt-RTag=Thread;Thrt-rchild=Thrt; /頭結(jié)點右指針回指if(!T)Thrt-lchild=Thrt; /如果二叉樹為空，則左指針也回指elseThrt-lchild=T; pre=

29、Thrt;/pre總是指向最后一個訪問過的結(jié)點，也就是其后要訪問結(jié)點的前驅(qū)InThreading(T);/線索化的主過程pre-rchild=Thrt; pre-RTag=Thread;Thrt-rchild=pre;/將最后一個結(jié)點線索化return OK;/InOrderThreadingStatus InOrderThreading(BiThrT樹的存儲結(jié)構(gòu)雙親表示：以一組連續(xù)空間存儲樹的結(jié)點，同時在結(jié)點中附設(shè)一個指針，存放雙親結(jié)點在鏈表中的位置。該方法利用每個結(jié)點只有一個雙親的特點，可以很方便求結(jié)點的雙親，但不方便求結(jié)點的孩子。樹與森林ABCDEFGdataparentA B C D

30、E F G-1 0 0 0 1 1 30 1 2 3 4 5 6樹的存儲結(jié)構(gòu)樹與森林ABCDEFGdataparentA 用雙親表示實現(xiàn)的樹定義#define MaxSize100 /最大結(jié)點個數(shù)typedef char TreeData; /結(jié)點數(shù)據(jù)typedef struct /樹結(jié)點定義 TreeData data; int parent; TreeNode;typedef TreeNode TreeMaxSize; /樹用雙親表示實現(xiàn)的樹定義#define MaxSize100ABCDEFG孩子表示法(多重鏈表 )第一種解決方案 等數(shù)量的鏈域 (d為樹的度) data child1ch

31、ild2child3childdABCDEFG 空鏈域n(d-1)+1個ABCDEFG孩子表示法(多重鏈表 )第一種解決方案 等第二種解決方案 孩子鏈表將每個結(jié)點的孩子鏈在該結(jié)點之后組成鏈表，再將所有頭結(jié)點組成一個線性表。typedef struct CTNode int child;struct CTNode *next;*ChildPtr;typedef structTElemType data;ChildPtr firstchild;CTBox;typedef structCTBox nodesMAX_TREE_SIZE;int n,r;/結(jié)點數(shù)和根的位置CTree;ABCDEFG0A1

32、B2C3D4E5F6G123 45 6 第二種解決方案 孩子鏈表將每個結(jié)點的孩子鏈在該結(jié)點之后組成鏈結(jié)點結(jié)構(gòu) datafirstChildnextSiblingABCDEFG空鏈域n+1個樹的左子女-右兄弟表示（二叉鏈表表示）BCDGFEA結(jié)點結(jié)構(gòu) datafirstChildnextSiblintypedef char TreeData;typedef struct node TreeData data; struct node *firstChild, *nextSibling; TreeNode;typedef TreeNode * Tree;用左子女-右兄弟表示實現(xiàn)的樹定義typede

33、f char TreeData;用左子女-右兄弟T1 T2 T3T1 T2 T3AFHBCDGIJEKAFBCDEGHIKJABCEDHIKJFG3 棵樹的森林各棵樹的二叉樹表示森林的二叉樹表示森林與二叉樹的轉(zhuǎn)換T1 T2 T3T1 樹的二叉樹表示:樹的遍歷深度優(yōu)先遍歷 先根次序遍歷 后根次序遍歷ABCDEFGABCEDGF樹的二叉樹表示:樹的遍歷深度優(yōu)先遍歷ABCDEFGABCED深度優(yōu)先遍歷當樹非空時 訪問根結(jié)點 依次先根遍歷根的各棵 子樹樹先根遍歷 ABEFCDG對應二叉樹前序遍歷 ABEFCDG樹的先根遍歷結(jié)果與其對應二叉樹 表示的前序遍歷結(jié)果相同樹的先根遍歷可以借助對應二叉樹的前序遍

34、歷算法實現(xiàn)ABCEDGF樹的先根次序遍歷ABCDEFG深度優(yōu)先遍歷當樹非空時ABCEDGF樹的先根次序遍歷ABCD樹的后根次序遍歷:當樹非空時依次后根遍歷根的各棵 子樹訪問根結(jié)點樹后根遍歷 EFBCGDA對應二叉樹中序遍歷 EFBCGDA樹的后根遍歷結(jié)果與其對應二叉樹 表示的中序遍歷結(jié)果相同樹的后根遍歷可以借助對應二叉樹的中序遍歷算法實現(xiàn)ABCEDGFABCDEFG樹的后根次序遍歷:當樹非空時ABCEDGFABCDEFG二叉樹的計數(shù) 由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。 例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 構(gòu)造二叉樹過程如下：HBDFEKCG

35、AEKCGABHDF二叉樹的計數(shù) 由二叉樹的前序序列和中序序列可唯一地確定KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKGKCGEKCGABHDFEKCGABHFDEABHFDEAB 如果前序序列固定不變，給出不同的中序序列，可得到不同的二叉樹。612345789612375849 固定前序排列,選擇所有可能的中序排列,可以構(gòu)造多少種不同的二叉樹？ 如果前序序列固定不變，給出不同的中序序列，可得到不同的 例如, 有 3 個數(shù)據(jù) 1, 2, 3 ，可得 5 種不同的二叉樹。它們的前序排列均為 123，中序序列可能是 321 ， 231， 213， 132，123.1231

36、23123123123 具有n個結(jié)點不同形態(tài)的樹的數(shù)目和具有n-1個結(jié)點互不相似的二叉樹的數(shù)目相同。 例如, 有 3 個數(shù)據(jù) 1, 2, 3 ，可 有0個, 1個, 2個, 3個結(jié)點的不同二叉樹如下b0 =1b1 =1b2 =2b3 =5 b4 =14 有0個, 1個, 2個, 3個結(jié)點的不同二叉樹如下b計算具有 n 個結(jié)點的不同二叉樹的棵數(shù)最終結(jié)果：bibn-i-11計算具有 n 個結(jié)點的不同二叉樹的棵數(shù)最終結(jié)果：bibn-i霍夫曼樹 (Huffman Tree)路徑長度 (Path Length) 兩個結(jié)點之間的路徑長度 PL 是連接兩結(jié)點的路徑上的分支數(shù)。 樹的外部路徑長度是各葉結(jié)點(外

37、結(jié)點)到根結(jié)點的路徑長度之和 EPL。 樹的內(nèi)部路徑長度是各非葉結(jié)點(內(nèi)結(jié)點)到根結(jié)點的路徑長度之和 IPL。 樹的路徑長度 PL = EPL + IPL霍夫曼樹 (Huffman Tree)路徑長度 (Path 123456782345678樹的外部路徑長度EPL = 3*1+2*3 = 9樹的外部路徑長度EPL = 1*1+2*1+3*1+4*1 = 101123456782345678樹的外部路徑長度樹的外部路徑長帶權(quán)路徑長度 (Weighted Path Length, WPL)二叉樹的帶權(quán) (外部) 路徑長度是樹的各葉結(jié)點所帶的權(quán)值 wi 與該結(jié)點到根的路徑長度 li 的乘積的和。帶

38、權(quán)路徑長度 (Weighted Path Length, WPL = 2*2+ WPL = 2*1+ WPL = 7*1+ 4*2+5*2+ 4*2+5*3+ 5*2+2*3+ 7*2 = 36 7*3 = 46 4*3 = 35 222444555777帶權(quán)(外部)路徑長度達到最小WPL = 2*2+ WPL = 2*1+ W數(shù)據(jù)結(jié)構(gòu)-第六章-樹與二叉樹課件霍夫曼樹帶權(quán)路徑長度達到最小的二叉樹即為霍夫曼樹。在霍夫曼樹中，權(quán)值大的結(jié)點離根最近。 (1) 由給定的 n 個權(quán)值 w0, w1, w2, , wn-1，構(gòu)造具有 n 棵擴充二叉樹的森林 F = T0, T1, T2, , Tn-1 ，

39、其中每棵擴充二叉樹 Ti 只有一 個帶權(quán)值 wi 的根結(jié)點, 其左、右子樹均為空。 霍夫曼算法霍夫曼樹帶權(quán)路徑長度達到最小的二叉樹即為霍夫曼樹。 ( (2) 重復以下步驟, 直到 F 中僅剩下一棵樹為止： 在 F 中選取兩棵根結(jié)點的權(quán)值最小的擴充二叉樹, 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。 在 F 中刪去這兩棵二叉樹。 把新的二叉樹加入 F。 (2) 重復以下步驟, 直到 F 中僅剩下一棵樹為止F : 7 5 2 4F : 7 5 6F : 7 11 7524初始合并2 475246F : 18 1175246合并5 65合并7 11

40、27461118舉例霍夫曼樹的構(gòu)造過程F : 7 5 2 4F : 7 55274Weight parent leftChild rightChild7 -1 -1 -15 -1 -1 -12 -1 -1 -14 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -10123456上例存儲結(jié)構(gòu)初 態(tài)5274Weight parent leftChil52746Weight parent leftChild rightChild 7 -1 -1 -1 5 -1 -1 -1 2 -1 -1 -1 4 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 -10123

41、456p1p24423i過 程52746Weight parent leftChi5274611Weight parent leftChild rightChild 7 -1 -1 -1 5 -1 -1 -1 2 4 -1 -1 4 4 -1 -1 6 -1 2 311 -1 -1 -1 -1 -1 -10123456p1p25514i5274611Weight parent leftC5274611Weight parent leftChild rightChild 7 -1 -1 -1 5 5 -1 -1 2 4 -1 -1 4 4 -1 -1 6 5 2 311 -1 1 418 -1

42、-1 -10123456p1p26605i18終 態(tài)5274611Weight parent leftCconst int n = 20;/葉結(jié)點數(shù)const int m = 2*n -1;/結(jié)點數(shù) typedef struct float weight; int parent, leftChild, rightChild; HTNode;typedef HTNode HuffmanTreem;霍夫曼樹的定義const int n = 20;/葉結(jié)點數(shù)霍夫曼樹的定建立霍夫曼樹的算法void CreateHuffmanTree ( HuffmanTree T, float fr ) for ( int i = 0; i n; i+ ) Ti.weight = fri; for ( i = 0; i m; i+ ) Ti.parent = -1; Ti.leftChild = -1; Ti.r