數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第三版）（微課版）第5章 樹(shù)和二叉樹(shù)

第5章樹(shù)教學(xué)要求相關(guān)知識(shí)點(diǎn)常用術(shù)語(yǔ)：樹(shù)、二叉樹(shù)、完全二叉樹(shù)、滿(mǎn)二叉樹(shù)、節(jié)點(diǎn)、節(jié)點(diǎn)的度、樹(shù)的高度、有序樹(shù)、無(wú)序樹(shù)、Huffman樹(shù)樹(shù)及二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷樹(shù)和二叉樹(shù)之間的轉(zhuǎn)換Huffman樹(shù)學(xué)習(xí)重點(diǎn)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷Huffman樹(shù)目錄二叉樹(shù)樹(shù)和森林哈夫曼樹(shù)5樹(shù)的概念126本章小結(jié)7二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷345.1樹(shù)的概念5.1樹(shù)的概念樹(shù)的定義1.樹(shù)的定義樹(shù)（Tree）是n（n≥0）個(gè)有限數(shù)據(jù)元素的集合。當(dāng)n＝0時(shí)，稱(chēng)這棵樹(shù)為空樹(shù)。在一棵非空樹(shù)T中：有一個(gè)特殊的數(shù)據(jù)元素稱(chēng)為樹(shù)的根節(jié)點(diǎn)，根節(jié)點(diǎn)沒(méi)有前驅(qū)。若n>1，除根節(jié)點(diǎn)之外的其余數(shù)據(jù)元素被分成m（m>0）個(gè)互不相交的集合T1，T2，…，Tm，其中每一個(gè)集合Ti（1≤i≤m）又是一棵樹(shù)，稱(chēng)為根節(jié)點(diǎn)的子樹(shù)。2.樹(shù)的特點(diǎn)樹(shù)的根節(jié)點(diǎn)沒(méi)有前驅(qū)節(jié)點(diǎn)，除根節(jié)點(diǎn)之外的所有節(jié)點(diǎn)有且只有一個(gè)前驅(qū)節(jié)點(diǎn)。樹(shù)中所有節(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼節(jié)點(diǎn)。5.1樹(shù)的概念樹(shù)的基本術(shù)語(yǔ)（1）節(jié)點(diǎn)表示樹(shù)中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的分支。如圖5.1中的A~M均為節(jié)點(diǎn)。5.1樹(shù)的概念（2）節(jié)點(diǎn)的寬度節(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)稱(chēng)為該節(jié)點(diǎn)的寬度（簡(jiǎn)稱(chēng)為度）。如圖5.1中A的度為3，B的度為2，C的度為1，D的度為3，E的度為0。5.1樹(shù)的概念（3）葉節(jié)點(diǎn)或終端節(jié)點(diǎn)度為0的節(jié)點(diǎn)稱(chēng)為葉節(jié)點(diǎn)，或者稱(chēng)為終端節(jié)點(diǎn)。如圖5.1中的E、K、L、G、H、M、J為葉節(jié)點(diǎn)。5.1樹(shù)的概念（4）分枝節(jié)點(diǎn)或非終端節(jié)點(diǎn)度不為0的節(jié)點(diǎn)稱(chēng)為分支節(jié)點(diǎn)，或者稱(chēng)為非終端節(jié)點(diǎn)。一棵樹(shù)的節(jié)點(diǎn)除葉節(jié)點(diǎn)外，其余的都是分支節(jié)點(diǎn)。如圖5.1中的A、B、C、D、F、I為分支節(jié)點(diǎn)。5.1樹(shù)的概念（5）樹(shù)的寬度樹(shù)的度是指樹(shù)中各節(jié)點(diǎn)度的最大值。如圖5.1中的樹(shù)的寬度為3。5.1樹(shù)的概念（6）孩子節(jié)點(diǎn)或子節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)含有的子樹(shù)的根節(jié)點(diǎn)稱(chēng)為該節(jié)點(diǎn)的孩子節(jié)點(diǎn)或子節(jié)點(diǎn)。圖5.1中的A節(jié)點(diǎn)含有的子樹(shù)T1的根節(jié)點(diǎn)B就為A節(jié)點(diǎn)的一個(gè)孩子節(jié)點(diǎn)。5.1樹(shù)的概念（7）雙親節(jié)點(diǎn)或父節(jié)點(diǎn)若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱(chēng)為其子節(jié)點(diǎn)的雙親節(jié)點(diǎn)或父節(jié)點(diǎn)。圖5.1中的A節(jié)點(diǎn)含有子節(jié)點(diǎn)B，則A節(jié)點(diǎn)稱(chēng)為B節(jié)點(diǎn)的父節(jié)點(diǎn)。5.1樹(shù)的概念（8）兄弟節(jié)點(diǎn)有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱(chēng)為兄弟節(jié)點(diǎn)。如圖5.1中的B、C、D為兄弟節(jié)點(diǎn)，有相同的父節(jié)點(diǎn)A。5.1樹(shù)的概念（9）節(jié)點(diǎn)的祖先指從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)。如圖5.1中K節(jié)點(diǎn)的祖先為A、B、F。5.1樹(shù)的概念（10）子孫以某節(jié)點(diǎn)為根的子樹(shù)中的任一節(jié)點(diǎn)都稱(chēng)為該節(jié)點(diǎn)的子孫。如圖5.1中B節(jié)點(diǎn)的子孫為E、F、K、L。5.1樹(shù)的概念（11）節(jié)點(diǎn)的層數(shù)規(guī)定樹(shù)的根節(jié)點(diǎn)的層數(shù)為1，其余節(jié)點(diǎn)的層數(shù)等于它的雙親節(jié)點(diǎn)的層數(shù)加1。如圖5.1中A節(jié)點(diǎn)的層次為1，B、C、D節(jié)點(diǎn)的層次為2，以此類(lèi)推。5.1樹(shù)的概念（12）堂兄弟節(jié)點(diǎn)雙親節(jié)點(diǎn)在同一層且雙親節(jié)點(diǎn)不相同的節(jié)點(diǎn)互為堂兄弟。如圖5.1中的E與G為堂兄弟，其雙親節(jié)點(diǎn)B與C在同一層但不相同。5.1樹(shù)的概念（13）樹(shù)的度(高度或深度)樹(shù)中所有節(jié)點(diǎn)的最大層數(shù)稱(chēng)為樹(shù)的度，如圖5.1中樹(shù)的度為4。5.1樹(shù)的概念（14）路徑、路徑長(zhǎng)度如果一棵樹(shù)的一串節(jié)點(diǎn)n0，n1，…，nk-1有如下關(guān)系：節(jié)點(diǎn)ni是ni+1的父節(jié)點(diǎn)(0≤i<k-1)，就把n0，n1，…，nk-1稱(chēng)為一條由n0至nk-1的路徑。這條路徑的長(zhǎng)度是k-1。（15）有序樹(shù)和無(wú)序樹(shù)如果一棵樹(shù)中節(jié)點(diǎn)的各子樹(shù)叢左到右是有次序的，即若交換了某節(jié)點(diǎn)各子樹(shù)的相對(duì)位置，則構(gòu)成不同的樹(shù)，稱(chēng)這棵樹(shù)為有序樹(shù)；反之，則稱(chēng)為無(wú)序樹(shù)。5.1樹(shù)的概念（16）森林零棵或有限棵不相交的樹(shù)的集合稱(chēng)為森林。自然界中樹(shù)和森林是不同的概念，但在數(shù)據(jù)結(jié)構(gòu)中，樹(shù)和森林只有很小的差別。任何一棵樹(shù)，刪去根節(jié)點(diǎn)就變成了森林。5.2二叉樹(shù)5.2二叉樹(shù)二叉樹(shù)的定義1.二叉樹(shù)的遞歸形式定義二叉樹(shù)（BinaryTree）是個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱(chēng)為根(root)的元素及兩個(gè)不相交的、被分別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。當(dāng)集合為空時(shí)，稱(chēng)該二叉樹(shù)為空二叉樹(shù)。5.2二叉樹(shù)2.二叉樹(shù)具有五種基本形態(tài)5.2二叉樹(shù)3.兩類(lèi)特殊的二叉樹(shù)（1）滿(mǎn)二叉樹(shù)在一棵二叉樹(shù)中，如果所有分支節(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子節(jié)點(diǎn)都在同一層上。5.2二叉樹(shù)（2）完全二叉樹(shù)一棵深度為k的有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，對(duì)樹(shù)中的節(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為i(0≤i≤n-1)的節(jié)點(diǎn)與滿(mǎn)二叉樹(shù)中編號(hào)為i的節(jié)點(diǎn)在二叉樹(shù)中的位置相同，則這棵二叉樹(shù)稱(chēng)為完全二叉樹(shù)。特點(diǎn)：葉子節(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下層的葉子節(jié)點(diǎn)集中在樹(shù)的左部。5.2二叉樹(shù)二叉樹(shù)的性質(zhì)性質(zhì)1

一棵非空二叉樹(shù)的第i層上最多有2i-1個(gè)節(jié)點(diǎn)（i≥1）。性質(zhì)2

一棵深度為k的二叉樹(shù)中，最多具有2k-1個(gè)節(jié)點(diǎn)。

性質(zhì)3

對(duì)于一棵非空的二叉樹(shù)，如果葉子節(jié)點(diǎn)數(shù)為n0，度數(shù)為2的節(jié)點(diǎn)數(shù)為n2，則有:n0＝n2＋1。

性質(zhì)4

具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)的深度k為。

5.2二叉樹(shù)二叉樹(shù)的性質(zhì)性質(zhì)5

對(duì)于具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，如果按照從上至下和從左到右的順序?qū)Χ鏄?shù)中的所有節(jié)點(diǎn)從1對(duì)n順序編號(hào)，則對(duì)于任意的序號(hào)為i的節(jié)點(diǎn)，有：（1）若i=1，則該節(jié)點(diǎn)是二叉樹(shù)的根節(jié)點(diǎn)，無(wú)雙親節(jié)點(diǎn)，否則，編號(hào)為

i/2

的節(jié)點(diǎn)為其雙親節(jié)點(diǎn)。（2）如果2i≤n，則序號(hào)為i的節(jié)點(diǎn)的左孩子節(jié)點(diǎn)的序號(hào)為2i；如果2i>n，則序號(hào)為i的節(jié)點(diǎn)無(wú)左孩子。（3）如果2i＋1≤n，則序號(hào)為i的節(jié)點(diǎn)的右孩子節(jié)點(diǎn)的序號(hào)為2i＋1；如果2i＋1>n，則序號(hào)為i的節(jié)點(diǎn)無(wú)右孩子。5.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)5.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)用一組連續(xù)的存儲(chǔ)單元存放二叉樹(shù)中的節(jié)點(diǎn)。一般是按照二叉樹(shù)節(jié)點(diǎn)從上至下、從左到右的順序存儲(chǔ)。增添一些并不存在的空節(jié)點(diǎn)，使之成為一棵完全二叉樹(shù)的形式，然后再用一維數(shù)組順序存儲(chǔ)。5.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)表示可描述為：#defineMaxNode10/*二叉樹(shù)的最大節(jié)點(diǎn)數(shù)*/typedefelemtypeSqBiTree[MaxNode]/*0號(hào)單元存放根節(jié)點(diǎn)*/SqBiTreebt;5.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)與操作1.二叉鏈表存儲(chǔ)每個(gè)節(jié)點(diǎn)由三個(gè)域組成，除了數(shù)據(jù)域外，還有兩個(gè)指針域，給出該節(jié)點(diǎn)左孩子和右孩子所在的節(jié)點(diǎn)的存儲(chǔ)地址。5.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)與操作1.二叉鏈表存儲(chǔ)用C語(yǔ)言的類(lèi)型描述二叉鏈表結(jié)構(gòu)如下:typedefstructBiTNode/*節(jié)點(diǎn)結(jié)構(gòu)*/{TElemTypedata;structBiTNode*lchild,*rchild; /*左右孩子節(jié)點(diǎn)指針*/}BiTNode,*BiTree;

5.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)2.三叉鏈表存儲(chǔ)每個(gè)節(jié)點(diǎn)由四個(gè)域組成，除了data、lchild以及rchild三個(gè)域外，增加parent域指向該節(jié)點(diǎn)雙親節(jié)點(diǎn)的指針。lchilddatarchildparent5.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)3.二叉樹(shù)的基本操作(1)Initiate(bt)建立一棵空二叉樹(shù)。intInitiate(BiTreebt)/*建立二叉樹(shù)，0表示建立失敗，1表示成功*/{if((*bt=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)return0;

*bt->lchild=NULL;

*bt->rchild=NULL;return1;}5.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)(2)Create(x)生成以x為根節(jié)點(diǎn)數(shù)據(jù)域的二叉樹(shù)。算法5.2生成一棵二叉樹(shù)BiTreeCreate(elemtypex){BiTreep;if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)returnNULL;p->data=x;p->lchild=NULL;p->rchild=NULL;returnp;}5.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)(3)InsertL(bt，x，parent)將數(shù)據(jù)域?yàn)閤的節(jié)點(diǎn)插入到二叉樹(shù)bt中作為節(jié)點(diǎn)parent的左孩子節(jié)點(diǎn)。如果節(jié)點(diǎn)parent原來(lái)有左孩子節(jié)點(diǎn)，則將節(jié)點(diǎn)parent原來(lái)左孩子節(jié)點(diǎn)作為節(jié)點(diǎn)x左孩子節(jié)點(diǎn)。

BiTreeInsertL(BiTreebt,elemtypex,BiTreeparent)/*在bt的節(jié)點(diǎn)parent的左子樹(shù)中插入節(jié)點(diǎn)數(shù)據(jù)元素x*/{BiTreep;if(parent==NULL){printf(“\n插入出錯(cuò)”);returnNULL;}5.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)returnNULL;p->data=x;p->lchild=NULL;p->rchild=NULL;if(parent->lchild==NULL)parent->lchild=p;else{p->lchild=parent->lchild;parent->lchild=p;}returnbt;}5.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)(4)InsertR(bt，x，parent)將數(shù)據(jù)域?yàn)閤的節(jié)點(diǎn)插入到二叉樹(shù)bt中作為節(jié)點(diǎn)parent的右孩子節(jié)點(diǎn)。如果節(jié)點(diǎn)parent原來(lái)有右孩子節(jié)點(diǎn)，則將節(jié)點(diǎn)parent原來(lái)的右孩子節(jié)點(diǎn)作為節(jié)點(diǎn)x的右孩子節(jié)點(diǎn)。5.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)(5)DeleteL(bt，parent)在二叉樹(shù)bt中刪除節(jié)點(diǎn)parent的左子樹(shù)。算法5.4在二叉樹(shù)中刪除節(jié)點(diǎn)BiTreeDeleteL(BiTreebt，BiTreeparent){BiTreep;if(parent==NULL||parent->lchild==NULL){printf("\n刪除出錯(cuò)")；returnNULL;}p=parent->lchild;parent->lchild=NULL;free(p);returnbr;}5.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)(6)DeleteR(bt，parent)在二叉樹(shù)bt中刪除節(jié)點(diǎn)parent的右子樹(shù)。(7)Search(bt，x)在二叉樹(shù)bt中查找數(shù)據(jù)元素x。(8)Traverse(bt)按某種方式遍歷二叉樹(shù)bt的全部節(jié)點(diǎn)。5.4二叉樹(shù)的遍歷5.4二叉樹(shù)遍歷遍歷算法二叉樹(shù)的遍歷是指按照某種順序訪(fǎng)問(wèn)二叉樹(shù)中的每個(gè)節(jié)點(diǎn)，使每個(gè)節(jié)點(diǎn)被訪(fǎng)問(wèn)一次且僅被訪(fǎng)問(wèn)一次。1.深度優(yōu)先遍歷深度優(yōu)先遍歷是指從根節(jié)點(diǎn)開(kāi)始，以遞歸的形式一棵子樹(shù)一棵子樹(shù)的遍歷。一棵樹(shù)由根節(jié)點(diǎn)、根節(jié)點(diǎn)的左子樹(shù)和根節(jié)點(diǎn)的右子樹(shù)三部分組成。若以D、L、R分別表示訪(fǎng)問(wèn)根節(jié)點(diǎn)、遍歷根節(jié)點(diǎn)的左子樹(shù)、遍歷根節(jié)點(diǎn)的右子樹(shù)，并規(guī)定先左后右，則二叉樹(shù)的遍歷方式有三種方式，即DLR(稱(chēng)為先序遍歷)、LDR(稱(chēng)為中序遍歷)和LRD(稱(chēng)為后序遍歷)。5.4二叉樹(shù)遍歷（1）先序（根）遍歷（DLR）先序遍歷的遞歸過(guò)程為：若二叉樹(shù)為空，遍歷結(jié)束。否則，訪(fǎng)問(wèn)根節(jié)點(diǎn)；先序遍歷根節(jié)點(diǎn)的左子樹(shù)；先序遍歷根節(jié)點(diǎn)的右子樹(shù)。5.4二叉樹(shù)遍歷算法5.5DLR先序(根)遍歷voidPreOrder(BiTreebt)/*先序遍歷二叉樹(shù)bt*/{if(bt==NULL)return;//遞歸調(diào)用結(jié)束條件Visit(bt->data); /*訪(fǎng)問(wèn)節(jié)點(diǎn)的數(shù)據(jù)域*/PreOrder(bt->lchild);//先序遞歸遍歷bt左子樹(shù)PreOrder(bt->rchild);//先序遞歸遍歷bt右子樹(shù)}5.4二叉樹(shù)遍歷【例5.1】對(duì)如圖5.11所示的二叉樹(shù)進(jìn)行先序遍歷。解答：第一步：先訪(fǎng)問(wèn)根節(jié)點(diǎn)A。第二步：發(fā)現(xiàn)A節(jié)點(diǎn)有左右子樹(shù)，遵循先左后右的原則進(jìn)入A的左子樹(shù)，訪(fǎng)問(wèn)左子樹(shù)的根B。以B為根的子樹(shù)只有右子樹(shù)D，所以訪(fǎng)問(wèn)D。第三步：至此，A的左子樹(shù)已經(jīng)訪(fǎng)問(wèn)完了，接著進(jìn)入A的右子樹(shù)，訪(fǎng)問(wèn)C。所以，先序遍歷上述二叉樹(shù)的順序?yàn)锳BDC。5.4二叉樹(shù)遍歷（2）中序遍歷（LDR）中序遍歷的遞歸過(guò)程為：若二叉樹(shù)為空，遍歷結(jié)束。否則，（1）中序遍歷根節(jié)點(diǎn)的左子樹(shù)；（2）訪(fǎng)問(wèn)根節(jié)點(diǎn)；（3）中序遍歷根節(jié)點(diǎn)的右子樹(shù)。5.4二叉樹(shù)遍歷算法5.6LDR中序(根)遍歷voidMidOrder(BiTreebt)/*中序遍歷二叉樹(shù)bt*/{if(bt==NULL)return;//遞歸調(diào)用結(jié)束條件MidOrder(bt->lchild);//中序遞歸遍歷bt左子樹(shù)Visit(bt->data);/*訪(fǎng)問(wèn)節(jié)點(diǎn)的數(shù)據(jù)域*/MidOrder(bt->rchild);//中序遞歸遍歷bt右子樹(shù)}5.4二叉樹(shù)遍歷【例5.2】對(duì)圖5.11所示的二叉樹(shù)

進(jìn)行中序遍歷。解答：第一步：發(fā)現(xiàn)A節(jié)點(diǎn)有左右子樹(shù)，進(jìn)入A的左子樹(shù)，由于A(yíng)的左子樹(shù)無(wú)左子樹(shù)，所以訪(fǎng)問(wèn)左子樹(shù)的根B。再訪(fǎng)問(wèn)以B為根的子樹(shù)的右子樹(shù)，所以訪(fǎng)問(wèn)D。第二步：再訪(fǎng)問(wèn)根節(jié)點(diǎn)A。第三步：接著進(jìn)入A的右子樹(shù)，訪(fǎng)問(wèn)C。所以，中序遍歷圖5.11所示的二叉樹(shù)的順序?yàn)锽DAC。5.4二叉樹(shù)遍歷（3）后序遍歷（LRD）后序遍歷的遞歸過(guò)程為：若二叉樹(shù)為空，遍歷結(jié)束。否則，（1）后序遍歷根節(jié)點(diǎn)的左子樹(shù)；（2）后序遍歷根節(jié)點(diǎn)的右子樹(shù)；（3）訪(fǎng)問(wèn)根節(jié)點(diǎn)。5.4二叉樹(shù)遍歷算法5.7LRD后(根)序遍歷voidPostOrder(BiTreebt){if(bt==NULL)return;//遞歸調(diào)用的結(jié)束條件PostOrder(bt->lchild);//后序遞歸遍歷bt左子樹(shù)PostOrder(bt->rchild);//后序遞歸遍歷bt右子樹(shù)

Visit(bt->data);/*訪(fǎng)問(wèn)節(jié)點(diǎn)的數(shù)據(jù)域*/}5.4二叉樹(shù)遍歷【例5.3】對(duì)如圖5.11所示的

二叉樹(shù)進(jìn)行后序遍歷。解答：第一步：發(fā)現(xiàn)A節(jié)點(diǎn)有左右子樹(shù)，進(jìn)入A的左子樹(shù)，由于A(yíng)的左子樹(shù)無(wú)左子樹(shù)，所以遍歷A的左子樹(shù)的右子樹(shù)，即訪(fǎng)問(wèn)D，再訪(fǎng)問(wèn)A的左子樹(shù)的根B。第二步：接著進(jìn)入A的右子樹(shù)，訪(fǎng)問(wèn)C。第三步：最后訪(fǎng)問(wèn)根節(jié)點(diǎn)A。所以，后序遍歷圖5.11所示的二叉樹(shù)的順序?yàn)镈BCA。5.4二叉樹(shù)遍歷【例5.4】對(duì)如圖5.12所示的二叉樹(shù)進(jìn)行先序遍歷、中序遍歷、后序遍歷。ABEFGHICD解答：先序遍歷結(jié)果：中序遍歷結(jié)果：后序遍歷結(jié)果：BDCAEHGIFDCBHIGFEA5.4二叉樹(shù)遍歷2.廣度優(yōu)先的層次遍歷所謂二叉樹(shù)的層次遍歷，是指從二叉樹(shù)的第一層（根節(jié)點(diǎn)）開(kāi)始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)?jié)點(diǎn)逐個(gè)訪(fǎng)問(wèn)。遍歷算法如下：(1)將根節(jié)點(diǎn)入隊(duì)；(2)若隊(duì)列為空，則結(jié)束；(3)否則隊(duì)首節(jié)點(diǎn)出隊(duì)并訪(fǎng)問(wèn)，再將其左右孩子節(jié)點(diǎn)按照先左后右的順序分別入隊(duì)，繼續(xù)執(zhí)行(2)。5.4二叉樹(shù)遍歷算法5.8層次遍歷二叉樹(shù)voidLevelOrder(BiTreebt){BiTreeQueue[MaxNode];

intfront,rear;

if(bt==NULL)exit(0);

front=-1;/*front為隊(duì)頭元素的前一個(gè)位置*/

rear=-1;/*rear為隊(duì)尾當(dāng)前位置*/

Queue[++rear]=bt;/*樹(shù)根入隊(duì)(先修改rear再入隊(duì))*/5.4二叉樹(shù)遍歷

while(front!=rear)

{

/*訪(fǎng)問(wèn)隊(duì)首節(jié)點(diǎn)的數(shù)據(jù)域，隊(duì)頭出隊(duì)(先修改front再訪(fǎng)問(wèn))*/

Visit(Queue[++front]->data);

/*將隊(duì)首節(jié)點(diǎn)的左孩子節(jié)點(diǎn)入隊(duì)*/

if(Queue[front]->lchild!=NULL)

{Queue[++rear]=Queue[front]->lchild;}

/*將隊(duì)首節(jié)點(diǎn)的右孩子節(jié)點(diǎn)入隊(duì)*/

if(Queue[front]->rchild!=NULL)

{Queue[++rear]=Queue[front]->rchild;}

}}5.4二叉樹(shù)遍歷【例5.5】對(duì)圖5.12所示的二叉樹(shù)進(jìn)行層次遍歷。rearAfront-15.4二叉樹(shù)遍歷【例5.5】對(duì)圖5.12所示的二叉樹(shù)進(jìn)行層次遍歷。

解答：層次遍歷結(jié)果：ArearEBfront-15.4二叉樹(shù)遍歷【例5.5】對(duì)圖5.12所示的二叉樹(shù)進(jìn)行層次遍歷。

解答：層次遍歷結(jié)果：ABrearCEfront-15.4二叉樹(shù)遍歷【例5.5】對(duì)圖5.12所示的二叉樹(shù)進(jìn)行層次遍歷。

解答：層次遍歷結(jié)果：ABErearFCfront-15.4二叉樹(shù)遍歷【例5.5】對(duì)圖5.12所示的二叉樹(shù)進(jìn)行層次遍歷。

解答：層次遍歷結(jié)果：ABECrearDFfront-15.4二叉樹(shù)遍歷【例5.5】對(duì)圖5.12所示的二叉樹(shù)進(jìn)行層次遍歷。

解答：層次遍歷結(jié)果：ABECFrearGDfront-15.4二叉樹(shù)遍歷【例5.5】對(duì)圖5.12所示的二叉樹(shù)進(jìn)行層次遍歷。

解答：層次遍歷結(jié)果：ABECFDrearGfront-15.4二叉樹(shù)遍歷【例5.5】對(duì)圖5.12所示的二叉樹(shù)進(jìn)行層次遍歷。

解答：層次遍歷結(jié)果：ABECFDGrearIHfront-15.4二叉樹(shù)遍歷【例5.5】對(duì)圖5.12所示的二叉樹(shù)進(jìn)行層次遍歷。

解答：層次遍歷結(jié)果：ABECFDGHrearIfront-15.4二叉樹(shù)遍歷【例5.5】對(duì)圖5.12所示的二叉樹(shù)進(jìn)行層次遍歷。

解答：層次遍歷結(jié)果：ABECFDGHIrearfront-15.4二叉樹(shù)遍歷線(xiàn)索二叉樹(shù)1.線(xiàn)索二叉樹(shù)節(jié)點(diǎn)結(jié)構(gòu)線(xiàn)索二叉樹(shù)是給二叉鏈表的左右孩子鏈表域賦予新的含義并增加兩個(gè)標(biāo)志域使得結(jié)構(gòu)如圖5.13所示。lchildltagdatartagrchild當(dāng)節(jié)點(diǎn)有左子樹(shù)，即lchild域不為空時(shí)，ltag為0。當(dāng)節(jié)點(diǎn)沒(méi)有左子樹(shù)，即lchild為空時(shí)，令lchild域指向該節(jié)點(diǎn)的前驅(qū)，ltag為1。當(dāng)節(jié)點(diǎn)有右子樹(shù)，即rchild域不為空時(shí)，rlag為0。當(dāng)節(jié)點(diǎn)沒(méi)有右子樹(shù)，即rchild為空時(shí)，令rchild域指向該節(jié)點(diǎn)的后繼，rtag為1。5.4二叉樹(shù)遍歷2.線(xiàn)索二叉樹(shù)結(jié)構(gòu)體描述typedefstructBiThrNode{ElemTypedata;

BiThrNode*lchild,*rchild;

intltag,rtag;}BiThrNode,*BiThrTree以此節(jié)點(diǎn)構(gòu)成的二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，叫作線(xiàn)索鏈表，其中指向節(jié)點(diǎn)前驅(qū)和后繼的指針?lè)Q作線(xiàn)索。加上線(xiàn)索的二叉樹(shù)叫線(xiàn)索二叉樹(shù)。對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€(xiàn)索二叉樹(shù)的過(guò)程稱(chēng)作線(xiàn)索化。5.4二叉樹(shù)遍歷3.線(xiàn)索二叉樹(shù)的實(shí)現(xiàn)線(xiàn)索二叉樹(shù)的表示方法：當(dāng)節(jié)點(diǎn)有左右子樹(shù)時(shí)，用實(shí)線(xiàn)箭頭指向其左右孩子節(jié)點(diǎn)；當(dāng)節(jié)點(diǎn)沒(méi)有左右子樹(shù)時(shí)，用虛線(xiàn)箭頭指向該節(jié)點(diǎn)的前驅(qū)或后繼。序列中最后一個(gè)節(jié)點(diǎn)的右指針可以為空。【例5.6】畫(huà)出如圖5.14所示的二叉樹(shù)的先序、中序、后序線(xiàn)索化后的線(xiàn)索二叉樹(shù)。5.4二叉樹(shù)遍歷(1)該二叉樹(shù)的先序遍歷的結(jié)果是abdce先序線(xiàn)索二叉樹(shù)如圖5.15所示。5.4二叉樹(shù)遍歷(2)該二叉樹(shù)中序遍歷的結(jié)果是bdaec中序線(xiàn)索二叉樹(shù)如圖5.16所示。5.4二叉樹(shù)遍歷(3)該二叉樹(shù)后序遍歷的結(jié)果是dbeca后序線(xiàn)索二叉樹(shù)如圖5.17所示。5.4二叉樹(shù)遍歷(1)中序線(xiàn)索二叉樹(shù)的建立算法5.9中序線(xiàn)索二叉樹(shù)的建立BiThrTreeInOrderThr(BiThrTreeT)/*中序遍歷二叉樹(shù)T，中序線(xiàn)索化，*head指向頭節(jié)點(diǎn)*/{BiThrTreehead;

if(!(head=(BiThrNodeType*)malloc(sizeof(BiThrNodeType))))returnNULL;

head->ltag=0;

head->rtag=1; /*建立頭節(jié)點(diǎn)*/head->rchild=head; /*右指針回指*/5.4二叉樹(shù)遍歷

if(!T)head->lchild=head;/*若二叉樹(shù)為空，則左指針回指*/

else

{head->lchild=T;pre=head;

InThreading(T);//中序遍歷進(jìn)行中序線(xiàn)索化

pre->rchild=head;

pre->rtag=1;/*最后一個(gè)節(jié)點(diǎn)線(xiàn)索化*/

head->rchild=pre;

}

returnhead;}5.4二叉樹(shù)遍歷(2)中序線(xiàn)索二叉樹(shù)的遍歷算法5.10中序線(xiàn)索二叉樹(shù)的遍歷voidInThreading(BiThrTreep)/*中序遍歷進(jìn)行中序線(xiàn)索化*/{if(p)

{InThreading(p->lchild);//左子樹(shù)線(xiàn)索化if(!p->lchild)/*對(duì)無(wú)左孩子的節(jié)點(diǎn)p進(jìn)行前驅(qū)線(xiàn)索化到節(jié)點(diǎn)pre*/{p->ltag=1;p->lchild=pre;}5.4二叉樹(shù)遍歷if(!pre->rchild)/*對(duì)無(wú)右孩子的節(jié)點(diǎn)pre進(jìn)行后繼線(xiàn)索化到節(jié)點(diǎn)p*/{pre->rtag=1;pre->rchild=p;}pre=p;//pre保存剛訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)，p為下一個(gè)要訪(fǎng)問(wèn)的節(jié)點(diǎn)InThreading(p->rchild);/*右子樹(shù)線(xiàn)索化*/}}5.4二叉樹(shù)遍歷(3)在中序線(xiàn)索二叉樹(shù)上查找中序前驅(qū)節(jié)點(diǎn)算法5.11在中序線(xiàn)索二叉樹(shù)上查找中序前驅(qū)節(jié)點(diǎn)BiThrTreeInPreNode(BiThrTreep)/*在中序線(xiàn)索二叉樹(shù)上查找節(jié)點(diǎn)p的中序前驅(qū)節(jié)點(diǎn)*/{BiThrTreepre;pre=p->lchild;//中序線(xiàn)索p節(jié)點(diǎn)若有左孩子，則其前驅(qū)一定是其左孩子的最深層的右孩子節(jié)點(diǎn)if(p->ltag!=1) while(pre->rtag==0)pre=pre->rchild;

return(pre);}5.4二叉樹(shù)遍歷(4)在中序線(xiàn)索二叉樹(shù)上查找中序后繼節(jié)點(diǎn)算法5.12中序線(xiàn)索二叉樹(shù)上查找中序后繼節(jié)點(diǎn)BiThrTreeInPostNode(BiThrTreep)/*在中序線(xiàn)索二叉樹(shù)上查找節(jié)點(diǎn)p的中序后繼節(jié)點(diǎn)*/{BiThrTreepost;post=p->rchild;//中序線(xiàn)索p節(jié)點(diǎn)若有右孩子，則其后繼一定是其右孩子的最深層的左孩子節(jié)點(diǎn)if(p->rtag!=1) while(post->ltag==0)post=post->lchild;

return(post);}5.5樹(shù)和森林5.5樹(shù)和森林樹(shù)和森林的存儲(chǔ)1.雙親存儲(chǔ)法雙親存儲(chǔ)法：用一組連續(xù)的存儲(chǔ)空間(一維數(shù)組)存儲(chǔ)樹(shù)中的各個(gè)節(jié)點(diǎn)，數(shù)組中的一個(gè)元素表示樹(shù)中的一個(gè)節(jié)點(diǎn)，數(shù)組元素為結(jié)構(gòu)體類(lèi)型，其中包括節(jié)點(diǎn)本身的信息以及節(jié)點(diǎn)的雙親節(jié)點(diǎn)在數(shù)組中的序號(hào)。雙親存儲(chǔ)法的實(shí)現(xiàn)：定義數(shù)組結(jié)構(gòu)存放樹(shù)的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)含有兩個(gè)域，分別為數(shù)據(jù)域和雙親域。數(shù)據(jù)域存放節(jié)點(diǎn)本身的信息，雙親域存放該節(jié)點(diǎn)的父節(jié)點(diǎn)的位置。

5.5樹(shù)和森林typedefstructnode{ElemTypedata;

intparent;}TreeNode;TreeNodetree[M];5.5樹(shù)和森林圖5.18所示的樹(shù)對(duì)應(yīng)的雙親存儲(chǔ)法的存儲(chǔ)結(jié)構(gòu)如圖5.19所示。

dataparent01a2b

3c4d5e6f7g8

h011225555.5樹(shù)和森林2.孩子鏈表存儲(chǔ)法孩子鏈表存儲(chǔ)法：使用一個(gè)與節(jié)點(diǎn)個(gè)數(shù)相同大小的一維數(shù)組，數(shù)組的每一個(gè)元素由兩個(gè)域組成，一個(gè)域用來(lái)存放節(jié)點(diǎn)信息，另一個(gè)用來(lái)存放指針，該指針指向由該節(jié)點(diǎn)的孩子節(jié)點(diǎn)組成的單鏈表的首位置。單鏈表結(jié)構(gòu)由兩個(gè)域組成，一個(gè)存放孩子節(jié)點(diǎn)在一維數(shù)組中的序號(hào)，另一個(gè)是指針域，指向下一個(gè)孩子節(jié)點(diǎn)。用一組連續(xù)的空間存儲(chǔ)樹(shù)的所有節(jié)點(diǎn)，然后給每個(gè)節(jié)點(diǎn)加上一個(gè)單鏈表，單鏈表是由其孩子節(jié)點(diǎn)組成的。每個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)用單鏈表存儲(chǔ)，再用含M個(gè)元素的結(jié)構(gòu)數(shù)組指向每個(gè)孩子鏈表。5.5樹(shù)和森林2.孩子鏈表存儲(chǔ)法(1)孩子節(jié)點(diǎn)typedefstructChildNode{intChild;/*節(jié)點(diǎn)在表頭數(shù)組中的下標(biāo)*/

structChildNode*next;/*指向下一個(gè)孩子節(jié)點(diǎn)在表頭數(shù)組中的下標(biāo)位置*/};5.5樹(shù)和森林2.孩子鏈表存儲(chǔ)法(2)表頭節(jié)點(diǎn)typedefstructHeadNode{ElemTypedata;/*數(shù)據(jù)域*/

structChildNode*firstchild;/*指向第一個(gè)孩子節(jié)點(diǎn)*/};HeadNodet[M];5.5樹(shù)和森林圖5.18所示的樹(shù)對(duì)應(yīng)的孩子鏈表存儲(chǔ)法的存儲(chǔ)結(jié)構(gòu)如圖5.20所示。5.5樹(shù)和森林3.雙親孩子存儲(chǔ)法雙親孩子存儲(chǔ)法：將雙親存儲(chǔ)法和孩子鏈表存儲(chǔ)法相結(jié)合的結(jié)果。其仍將各節(jié)點(diǎn)的孩子節(jié)點(diǎn)分別組成單鏈表，同時(shí)用一維數(shù)組順序存儲(chǔ)樹(shù)中的各節(jié)點(diǎn)，數(shù)組元素除了包括節(jié)點(diǎn)本身的信息和該節(jié)點(diǎn)的孩子節(jié)點(diǎn)鏈表的頭指針之外，還增設(shè)了一個(gè)域，用來(lái)存儲(chǔ)該節(jié)點(diǎn)雙親節(jié)點(diǎn)在數(shù)組中的序號(hào)。每個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)用單鏈表存儲(chǔ)，再用含M個(gè)元素的結(jié)構(gòu)數(shù)組指向每個(gè)孩子鏈表。結(jié)構(gòu)數(shù)組存放樹(shù)的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)含有三個(gè)域，分別為數(shù)據(jù)域、雙親域和第一個(gè)孩子節(jié)點(diǎn)的地址。5.5樹(shù)和森林3.雙親孩子存儲(chǔ)法(1)孩子節(jié)點(diǎn)typedefstructChildNode{intChild;/*節(jié)點(diǎn)在表頭數(shù)組中的下標(biāo)*/

structChildNode*next;/*指向下一個(gè)孩子節(jié)點(diǎn)在表頭數(shù)組中的下標(biāo)位置*/};5.5樹(shù)和森林3.雙親孩子存儲(chǔ)法(2)表頭節(jié)點(diǎn)typedefstructHeadNode{ElemTypedata;/*數(shù)據(jù)域*/

intparent;/*雙親域*/

structChildNode*firstchild;/*指向第一個(gè)孩子節(jié)點(diǎn)*/};HeadNodet[M];5.5樹(shù)和森林圖5.18所示的樹(shù)對(duì)應(yīng)的雙親孩子存儲(chǔ)法的存儲(chǔ)結(jié)構(gòu)如圖5.21所示。5.5樹(shù)和森林4.孩子兄弟存儲(chǔ)法孩子兄弟存儲(chǔ)法:用二叉鏈表存儲(chǔ)樹(shù)和森林，在樹(shù)中，每個(gè)節(jié)點(diǎn)除其信息域外，再增加了兩個(gè)指針，分別指向該節(jié)點(diǎn)的第一個(gè)孩子節(jié)點(diǎn)和下一個(gè)兄弟節(jié)點(diǎn)的指針。樹(shù)中節(jié)點(diǎn)的存儲(chǔ)表示可描述為：typedefstructTreeNode{ElemTypedata;

structNode*firstchild;structNode*nextsibling;}TreeNode;5.5樹(shù)和森林圖5.18所示的樹(shù)對(duì)應(yīng)的孩子兄弟存儲(chǔ)法的存儲(chǔ)結(jié)構(gòu)如圖5.22所示。5.5樹(shù)和森林二叉樹(shù)、樹(shù)和森林的轉(zhuǎn)換1.樹(shù)轉(zhuǎn)換為二叉樹(shù)在樹(shù)中所有相鄰兄弟之間加一條連線(xiàn)。對(duì)樹(shù)中的每個(gè)節(jié)點(diǎn)，只保留它與第一個(gè)孩子節(jié)點(diǎn)之間的連線(xiàn)，刪去它與其他孩子節(jié)點(diǎn)之間的連線(xiàn)。以樹(shù)的根節(jié)點(diǎn)為軸心，將整棵樹(shù)順時(shí)針轉(zhuǎn)動(dòng)一定的角度，使之結(jié)構(gòu)層次分明。5.5樹(shù)和森林2.森林轉(zhuǎn)換為二叉樹(shù)

將森林中的每棵樹(shù)轉(zhuǎn)換成相應(yīng)的二叉樹(shù)；將森林中第一棵二叉樹(shù)不動(dòng)，第一棵樹(shù)的根節(jié)點(diǎn)作為二叉樹(shù)的根節(jié)點(diǎn)；將森林中第一棵樹(shù)的子孫節(jié)點(diǎn)作為二叉樹(shù)的左子樹(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ù)和森林【例5.7】將如圖5.23所示的森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹(shù)轉(zhuǎn)換的二叉樹(shù)如右圖所示5.5樹(shù)和森林3.二叉樹(shù)轉(zhuǎn)換為樹(shù)和森林由二叉樹(shù)的根節(jié)點(diǎn)作為森林中第一棵樹(shù)的根節(jié)點(diǎn)；二叉樹(shù)的左子樹(shù)作為森林中第一棵樹(shù)的子孫；二叉樹(shù)的右子樹(shù)作為森林中第一棵樹(shù)的兄弟?？梢砸罁?jù)二叉樹(shù)的根節(jié)點(diǎn)有無(wú)右分支，將一棵二叉樹(shù)還原為樹(shù)或森林，具體方法如下：(1)若某節(jié)點(diǎn)是其雙親的左孩子，則把該節(jié)點(diǎn)的右孩子、右孩子的右孩子都與該節(jié)點(diǎn)的雙親節(jié)點(diǎn)用線(xiàn)連起來(lái)；(2)刪去原二叉樹(shù)中所有雙親節(jié)點(diǎn)與右孩子節(jié)點(diǎn)的連線(xiàn)；(3)整理由(1)、(2)兩步所得到的樹(shù)或森林，使之結(jié)構(gòu)層次分明。5.5樹(shù)和森林樹(shù)和森林的遍歷1.樹(shù)的遍歷(1)先根遍歷訪(fǎng)問(wèn)根節(jié)點(diǎn)；按照從左到右的順序先根遍歷根節(jié)點(diǎn)的每一棵子樹(shù)。樹(shù)的先根遍歷與其轉(zhuǎn)換的相應(yīng)二叉樹(shù)的先序遍歷的結(jié)果序列相同。5.5樹(shù)和森林1.樹(shù)的遍歷(2)后根遍歷按照從左到右的順序后根遍歷根節(jié)點(diǎn)的每一棵子樹(shù)；訪(fǎng)問(wèn)根節(jié)點(diǎn)。樹(shù)的后根遍歷與其轉(zhuǎn)換的相應(yīng)二叉樹(shù)的中序遍歷的結(jié)果序列相同。5.5樹(shù)和森林2.森林的遍歷(1)先序遍歷訪(fǎng)問(wèn)森林中第一棵樹(shù)的根節(jié)點(diǎn)；先序遍歷第一棵樹(shù)的根節(jié)點(diǎn)的子樹(shù)；先序遍歷去掉第一棵樹(shù)后的子森林。森林的先序遍歷與所轉(zhuǎn)換的二叉樹(shù)的先序遍歷的結(jié)果序列相同。5.5樹(shù)和森林2.森林的遍歷(2)中序遍歷中序遍歷第一棵樹(shù)的根節(jié)點(diǎn)的子樹(shù)；訪(fǎng)問(wèn)森林中第一棵樹(shù)的根節(jié)點(diǎn)；中序遍歷去掉第一棵樹(shù)后的子森林。森林的中序遍歷與所轉(zhuǎn)換的二叉樹(shù)的中序遍歷的結(jié)果序列相同。5.6哈夫曼樹(shù)5.6哈夫曼樹(shù)哈夫曼樹(shù)的定義哈夫曼（Haffman）樹(shù)也稱(chēng)最優(yōu)二叉樹(shù)，是指對(duì)一組帶權(quán)的葉節(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長(zhǎng)度的二叉樹(shù)。節(jié)點(diǎn)的路徑長(zhǎng)度：從根節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑上分支數(shù)。

節(jié)點(diǎn)權(quán)值：附加在節(jié)點(diǎn)上的信息。

節(jié)點(diǎn)帶權(quán)路徑：節(jié)點(diǎn)上權(quán)值與該節(jié)點(diǎn)到根之間的路徑長(zhǎng)度的乘積。

二叉樹(shù)的路徑長(zhǎng)度：由根節(jié)點(diǎn)到所有葉節(jié)點(diǎn)的路徑長(zhǎng)度之和。

5.6哈夫曼樹(shù)二叉樹(shù)的帶權(quán)路徑長(zhǎng)度：設(shè)二叉樹(shù)具有n個(gè)帶權(quán)的葉節(jié)點(diǎn)，那么從根節(jié)點(diǎn)到各個(gè)葉節(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)節(jié)點(diǎn)權(quán)值的乘積之和稱(chēng)作二叉樹(shù)的帶權(quán)路徑長(zhǎng)度，記為：WPL(T)=

wklk(權(quán)重為wk，路徑為lk)哈夫曼(Huffman)樹(shù)：使WPL取最小值的二叉樹(shù)，又稱(chēng)最優(yōu)二叉樹(shù)。5.6哈夫曼樹(shù)【例5.10】計(jì)算如圖5.25所示二叉樹(shù)的WPL。解答：WPL(T)=1×2+8×2+5×3+7×4+2×2=655.6哈夫曼樹(shù)哈夫曼樹(shù)的存儲(chǔ)定義哈夫曼樹(shù)的存儲(chǔ)定義如下：typedefstruct{intweight;intparent;intlchild;intrchild;}HNodeType;5.6哈夫曼樹(shù)哈夫曼樹(shù)的構(gòu)造算法哈夫曼提出哈夫曼樹(shù)的構(gòu)造算法，也叫哈夫曼算法。(1)由給定的n個(gè)權(quán)值{w1，w2，…，wn}構(gòu)成n棵只有一個(gè)節(jié)點(diǎn)的二叉樹(shù)的集合F={T1，T2，…，Tn}，即每棵二叉樹(shù)Ti只有一個(gè)權(quán)值為Wi的根節(jié)點(diǎn)，其左右子樹(shù)均空；(2)在F中選兩棵根節(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹(shù)作為左右子樹(shù)構(gòu)成一棵新的二叉樹(shù)，且根節(jié)點(diǎn)的權(quán)值為其左右子樹(shù)根節(jié)點(diǎn)的權(quán)值之和；(3)在集合F中刪除作為左、右子樹(shù)的兩棵二叉樹(shù)，并將新建立的二叉樹(shù)加入到集合F中；(4)重復(fù)步驟(2)和(3)，直到F只含一棵二叉樹(shù)，這棵二叉樹(shù)便是所要構(gòu)造的哈夫曼樹(shù)。5.6哈夫曼樹(shù)【例5.9】已知權(quán)值W={5，6，3，10，7}，請(qǐng)構(gòu)造一棵哈夫曼樹(shù)。解答：第1步：根據(jù)給定的5個(gè)權(quán)值構(gòu)成5棵只有一個(gè)節(jié)點(diǎn)的二叉樹(shù)，如圖5.26(a)所示；第2步：選擇權(quán)值為3、5的節(jié)點(diǎn)構(gòu)成一棵新的二叉樹(shù)，如圖5.26(b)所示；5.6哈夫曼樹(shù)第3步：在F中刪除權(quán)值分別為3、5兩個(gè)二叉樹(shù)，并將新二叉樹(shù)權(quán)8加入到F中，得F={7、6、10、8}；第4步：在F={7、6、10、8}中選擇6、7的節(jié)點(diǎn)樹(shù)作為左右子樹(shù)構(gòu)成一棵新的二叉樹(shù)，如圖5.26(c)所示；5.6哈夫曼樹(shù)第5步：在F中刪除權(quán)值分別為6、7兩個(gè)二叉樹(shù)，并將新二叉樹(shù)權(quán)13加入到F中，得F={13、10、8}；第6步：在F={13、10、8}中選擇8、10的節(jié)點(diǎn)作為左右子樹(shù)構(gòu)成一棵新的二叉樹(shù)，如圖5.27(a)所示；5.6哈夫曼樹(shù)第7步：在F中刪除權(quán)值分別為8、10兩個(gè)二叉樹(shù)，并將新二叉樹(shù)權(quán)183加入到F中，得F={13、18}；第8步：在F={13、18}中只能選擇13、18的節(jié)點(diǎn)作為左右子樹(shù)構(gòu)成一棵新的二叉樹(shù)，如圖5.27(b)所示；5.6哈夫曼樹(shù)第9步：在F中刪除權(quán)值分別為13、18兩個(gè)二叉樹(shù)，并將新二叉樹(shù)權(quán)31加入到F中，得F={31}；第10步：至此，F(xiàn)={31}僅含有一棵樹(shù)，所以該樹(shù)即為哈夫曼樹(shù)。由上述構(gòu)造算法可知，哈夫曼樹(shù)的形式不唯一。5.6哈夫曼樹(shù)哈夫曼樹(shù)的建立過(guò)程5.6哈夫曼樹(shù)哈夫曼樹(shù)的構(gòu)造算法已知n個(gè)字符的權(quán)值，生成一棵哈夫曼樹(shù)。算法5.13哈夫曼樹(shù)的構(gòu)造voidHaffmanTree(HNodeTypeHuffNode[MAXLEAF]){inti,j,m1,m2,x1,x2;