樹的定義和基本術(shù)語課件

6.1樹的定義和基本術(shù)語6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.5Huffman樹及其應用第六章樹與二叉樹6.1樹的定義和基本術(shù)語第六章樹與二叉樹內(nèi)蒙古大學理工學院計算機學院生命科學學院外國語學院人文學院數(shù)學系物理系電子系計算機系計算中心網(wǎng)絡(luò)中心漢語系歷史系哲學系生物系環(huán)境系動物中心生物工程中心資源所英語系日語系行政機構(gòu)樹形結(jié)構(gòu)是一種非線性結(jié)構(gòu)，應用十分廣泛。如：行政機構(gòu)、家譜、磁盤目錄等內(nèi)蒙古大學理工學院計算機學院生命科學學院外國語學院人文學院數(shù)磁盤目錄磁盤目錄根Root分枝Branch葉Leaf根-----------------根結(jié)點分枝--------------分枝結(jié)點葉-----------------葉結(jié)點6.1樹（Tree）的定義和基本術(shù)語根Root分枝Branch葉Leaf根-----------樹的定義：樹是n（n>=0）結(jié)點的有限集，在任意非空樹中：(1)有且僅有一個特定的結(jié)點稱為根（Root）的結(jié)點.(2)當n>1時，其余的結(jié)點可分為m個互不相交的子集T1,T2,…,Tm,每個子集又都是樹，稱為根的子樹（Subtree）.6.1樹（Tree）的定義和基本術(shù)語樹的定義具有遞歸性樹的定義：樹是n（n>=0）結(jié)點的有限集，6.1樹（TreTree=<D,{R}>D={Book,C1,C2,C3,S1.1,S1.2,S2.1,S2.2,S2.3,S2.1.1,S2.1.2}R={<Book,C1>,<Book,C2>,<Book,C3>,<C1,S1.1>,<C1,S1.2>,<C2,S2.1>,<C2,S2.2>,<C2,S2.3>,<S2.1,S2.1.1>,<S2.1,S2.1.2>}BookC1C2C3S1.1S1.2S2.1S2.2S2.3S2.1.1S2.1.2ChapterSectionSection例6.16.1樹（Tree）的定義和基本術(shù)語Tree=<D,{R}>BookC1C2C3S1.術(shù)語主要來源于家譜和樹：雙親、父母（Parent）；子女、孩子（Child）：若〈a,b〉R，則稱a是b的雙親，b是a的子女(孩子).葉結(jié)點（Leaf）：度為0的結(jié)點；分枝結(jié)點（Branchnode）：度大于0的結(jié)點；結(jié)點度（Degree）：該結(jié)點所擁有的子女數(shù)；樹的度：樹內(nèi)各結(jié)點度的最大值；結(jié)點的層次（Level）：設(shè)根結(jié)點的層次為1，其它任一結(jié)點所在的層次是其雙親的層次加1；6.1樹（Tree）的定義和基本術(shù)語術(shù)語主要來源于家譜和樹：6.1樹（Tree）的定義和基本術(shù)樹是一種層次結(jié)構(gòu)（hiberarchy）123456.1樹（Tree）的定義和基本術(shù)語樹是一種層次結(jié)構(gòu)（hiberarchy）123456.1堂兄弟（Cousin）：雙親在同一層的結(jié)點之間互稱堂兄弟；路徑（Path）：如果有結(jié)點序列n1,n2,n3,…,nk，并且前1個結(jié)點是后1個結(jié)點的雙親；它的長度是k-1;祖先、后代（ancestor）:一個結(jié)點是它所有子樹中的結(jié)點的祖先，這些結(jié)點是它的后代(子孫);有序樹（Orderedtree）：每個結(jié)點的子女由左到右是有次序的稱有序樹；否則是無序樹；6.1樹（Tree）的定義和基本術(shù)語ABCACB無序有序深度（Depth）：樹中結(jié)點的最大層次；或稱為高；兄弟（Sibling)：具有同一雙親的結(jié)點互稱兄弟；堂兄弟（Cousin）：雙親在同一層的結(jié)點之間互稱堂兄弟；6ABCDEFGHIJKLM結(jié)點A的度：3結(jié)點B的度：2結(jié)點M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點A的孩子：B，C，D結(jié)點B的孩子：E，F(xiàn)結(jié)點I的雙親：D結(jié)點L的雙親：E結(jié)點B，C，D為兄弟結(jié)點K，L為兄弟樹的度：3結(jié)點A的層次：1結(jié)點M的層次：4樹的深度：4結(jié)點F，G為堂兄弟結(jié)點A是結(jié)點F，G的祖先ABCDEFGHIJKLM結(jié)點A的度：3葉子：K，L，F(xiàn)，GT1T2T3T4T5T66.1樹（Tree）的定義和基本術(shù)語森林（Forest）：是m(m0)棵互不相交的樹的集合(例如刪除樹根后的子樹構(gòu)成一個森林)ArootBCDEFGHIJMKLF任何一棵非空樹是一個二元組

Tree=（root，F(xiàn)）其中：root被稱為根結(jié)點，F(xiàn)被稱為子樹森林T1T2T3T4T5T66.1樹（Tree）的定義和基本術(shù)抽象數(shù)據(jù)類型樹的定義：6.1樹（Tree）的定義和基本術(shù)語ADTTree{數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹；若D僅含一個數(shù)據(jù)元素，則R為空集，否則R={H}，H是如下二元關(guān)系：(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；(2)若D-{root}≠，則存在D-{root}的一個劃分D1，D2，…，Dm，(m>0)，對任意j≠k(1≤j,k≤m)有Dj∩Dk=,

且對任意的i(1≤i≤m)，唯一存在數(shù)據(jù)元素xi∈Di，

有<root，xi>∈H；抽象數(shù)據(jù)類型樹的定義：6.1樹（Tree）的定義和基本術(shù)語(3)對應于D-{root}的劃分，H—{<root，x1>，…，<root，xm>}

有唯一的一個劃分H1,H2，…，Hm(m>0)，對任意j≠k(1≤j，k≤m)有Hj∩Hk=,且對任意i(1≤i≤m),Hi是Di上的二元關(guān)系,(Di,{Hi})是一棵符合本定義的樹,稱為根root的子樹.基本操作:InitTree(&T)

操作結(jié)果：構(gòu)造空樹T。DestroyTree(&T)

初始條件：樹T存在。操作結(jié)果，銷毀樹T。(3)對應于D-{root}的劃分，H—{<root，x1CreateTree(&T，definition)

初始條件：definition給出樹T的定義。操作結(jié)果：按definition構(gòu)造樹T。ClearTree(&T)

初始條件；樹T存在。操作結(jié)果：將樹T清為空樹。TreeEmpty(T)

初始條件：樹T存在。操作結(jié)果：若T為空樹，則返回TRUE，否則FALSE。TreeDepth(T)

初始條件：樹T存在。操作結(jié)果；返回T的深度?；静僮?CreateTree(&T，definition)基本操作:Root(T)

初始條件：樹T存在。操作結(jié)果：返回T的根。Value(T，cur_e)

初始條件：樹T存在，cur_e是T中某個結(jié)點。操作結(jié)果：返回cur_e的值。Assign(T，cur_e，value)

初始條件：樹T存在，cur_e是T中某個結(jié)點。操作結(jié)果：結(jié)點cur_e賦值為value。Parent(T，cur_e)；

初始條件：樹T存在，cur_e是T中某個結(jié)點。操作結(jié)果：若cur_e是T的非根結(jié)點，則返回它的雙親，否則返回“空”?；静僮?Root(T)基本操作:LeftChild(T，cur_e)；

初始條件：樹T存在，cur_e是T中某個結(jié)點。操作結(jié)果：若cur_e是T的非葉子結(jié)點，則返回它的最左孩子，否則返回“空”。RightSibling(T，cur_e)；

初始條件：樹T存在，cur_e是T中某個結(jié)點。

操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，否則返回“空”。

基本操作:LeftChild(T，cur_e)；基本操作:InsertChild(&T，&P，i，c)；

初始條件：樹T存在,p指向T中某個結(jié)點，i指結(jié)點的度,非空樹c與T不相交。操作結(jié)果：插入c為T中p所指結(jié)點的第i棵子樹。DeleteChild(&T，&p，i)；

初始條件：樹T存在，p指向T中某個結(jié)點，i指結(jié)點的度,操作結(jié)果：刪除T中p所指結(jié)點的第i棵子樹。TraverseTree(T)；

初始條件；樹T存在。操作結(jié)果：按某種次序?qū)的每個結(jié)點進行遍歷。}ADTTree基本操作:InsertChild(&T，&P，i，c)；基本操作:樹的表示方法：1.樹形表示：6.1樹（Tree）的定義和基本術(shù)語ABCDEFHIJG2.括號表示(廣義表表示)：(A(B(E))(C(F))(D(G(H)(I)(J))))

T1T3T2樹根樹的表示方法：6.1樹（Tree）的定義和基本術(shù)語ABCD3.凹入表表示(目錄表示法)：

ABCDEFHIJGABECFDGHIJ6.1樹（Tree）的定義和基本術(shù)語3.凹入表表示(目錄表示法)： ABCDEFHIJGAB4.文氏圖表示(集合表示):ABCDEFHIJGABECFDGHIJ6.1樹（Tree）的定義和基本術(shù)語4.文氏圖表示(集合表示):ABCDEFHIJGABECF二叉樹是另一種樹形結(jié)構(gòu)。6.2.1二叉樹的定義二叉樹：是n（n>=0）結(jié)點的有限集，在任意非空樹中：(1)有且僅有一個特定的稱為根（Root）的結(jié)點;(2)當n>1時，其余的結(jié)點最多分為2個互不相交的子集T1,T2,每個又都是二叉樹，分別稱為根的左子樹和右子樹.6.2二叉樹（BinaryTree）二叉樹是另一種樹形結(jié)構(gòu)。6.2二叉樹（BinaryTr例6.2.1二叉樹的定義ABCDEFGHK根結(jié)點左子樹右子樹二叉樹例6.2.1二叉樹的定義ABCDEFGHK根結(jié)點左子樹右子注意：二叉樹不是樹，它是另外單獨定義的一種樹形結(jié)構(gòu)，并非一般樹的特例。它的子樹有順序規(guī)定，分為左子樹和右子樹。不能隨意顛倒。注意：二叉樹不是樹，它是另外單獨定義的一種樹形結(jié)構(gòu)，并非一般二叉樹的5種基本形態(tài)：1空2只有根3右子樹空4左子樹空5左、右子樹非空具有3個結(jié)點的二叉樹可能有幾種不同形態(tài)？二叉樹的5種基本形態(tài)：1空2只有根3右子樹空4左子抽象數(shù)據(jù)類型二叉樹的定義：ADTBinaryTree{數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D=，則R=，稱Binary為空二叉樹；若D≠，則R={H}，H是如下二元關(guān)系：

(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；

(2)若D-{root}≠，則存在D-{root}的一個劃分{Dl，Dr}，且Dl∩Dr=；

(3)

若Dl≠,則Dl中存在唯一的元素x1,<root,x1>H,且存在Dl上的關(guān)系HlH,若Dr≠,則Dr中存在唯一的元素xr,<root,xr>H,且存在Dr上的關(guān)系HrH;H={<root,xl>,<root,xr>,Hl,Hr}

(4)(Dl,{Hl})是一顆符合本定義的二叉樹，稱為根的左子樹(Dr,{Hr})是一顆符合本定義的二叉樹，稱為根的右子樹6.2.1二叉樹的定義抽象數(shù)據(jù)類型二叉樹的定義：6.2.1二叉樹的定義基本操作:InitBiTree(&T);

操作結(jié)果：構(gòu)造空二叉樹T。DestroyBiTree(&T);

初始條件：二叉樹T存在。操作結(jié)果：銷毀二叉樹T。CreatBiTree(&T,definition);

初始條件：definition給出二叉樹T的定義。操作結(jié)果：按definition構(gòu)造二叉樹T。ClearBiTree(&T)；

初始條件：二叉樹T存在。操作結(jié)果：將二叉樹T清為空樹?；静僮?BiTreeEmpty(T)；

初始條件：二叉樹T存在。操作結(jié)果：若T為空二叉樹,則返回TRUE,否則FALSE.BiTreeDepth(T)；

初始條件：二叉樹T存在。操作結(jié)果：返回T的深度。Root(T)；

初始條件:二叉樹T存在。操作結(jié)果：返回T的根。Value(T，e)

初始條件：二叉樹T存在，e是T中某個結(jié)點。

操作結(jié)果；返回e的值。

基本操作:BiTreeEmpty(T)；基本操作:Assign(T，&e，value)；

初始條件；二叉樹T存在，e是T中某個結(jié)點。操作結(jié)果：結(jié)點e賦值為value。Parent(T，e)；

初始條件：二叉樹T存在，e是T中某個結(jié)點。操作結(jié)果：若e是T的非根結(jié)點，則返回它的雙親，否則返回“空”。LeftChild(T，e)；

初始條件：二叉樹T存在，e是T中某個結(jié)點。操作結(jié)果：返回e的左孩子，若e無左孩子，則返回“空”。RightChild(T，e)；

初始條件：二叉樹T存在，e是T中某個結(jié)點。操作結(jié)果：返回e的右孩子,若e無右孩子，則返回“空”?；静僮?Assign(T，&e，value)；基本操作:LeftSibling(T，e)；

初始條件：二叉樹T存在，e是T中某個結(jié)點。

操作結(jié)果：返回e的左兄弟。若e是T的左孩子或無左兄弟，則返回“空”。

Rightsibling(T，e)；

初始條件：二叉樹T存在，e是T中某個結(jié)點。操作結(jié)果：返回e的右兄弟。若e是T的右孩子或無右兄弟，則返回“空”?；静僮?LeftSibling(T，e)；Rightsibling(InsertChild(T，p，LR，c)；

初始條件：二叉樹T存在，p指向T中某個結(jié)點，LR為0或1，非空二叉樹c與T不相交且右子樹為空。操作結(jié)果：根據(jù)LR為0或1，插入c為T中p所指結(jié)點的左或右子樹。P所指結(jié)點的原有左或右子樹則成為c的右子樹?；静僮?DeleteChild(T，p，LR)；

初始條件：二叉樹T存在，p指向T中某個結(jié)點，LR為0或1。

操作結(jié)果：根據(jù)LR為0或1，刪除T中p所指結(jié)點的左或右子樹。InsertChild(T，p，LR，c)；操作結(jié)果：根據(jù)LPreOrderTraverse(T)；

初始條件：二叉樹T存在。操作結(jié)果：先序遍歷T中對每個結(jié)點一次且僅一次?；静僮?InOrderTraverse(T)；

初始條件：二叉樹T存在。操作結(jié)果：中序遍歷T中每個結(jié)點一次且僅一次。PreOrderTraverse(T)；基本操作:InOrdPostOrderTraverse(T)；

初始條件：二叉樹T存在。操作結(jié)果：后序遍歷T中每個結(jié)點一次且僅一次?；静僮?LevelOrderTraverse(T)；

初始條件：二叉樹T存在。操作結(jié)果：層序遍歷T中每個結(jié)點一次且僅一次.}ADTBinaryTreePostOrderTraverse(T)；基本操作:Leve性質(zhì)1:在二叉樹的第i層最多有2i-1

個結(jié)點(i>=1).用歸納法證明：

歸納基：

歸納假設(shè)：

歸納證明：i=1

層時，只有一個根結(jié)點，2i-1=20=1；i=k時命題成立;i=k+1時,二叉樹上每個結(jié)點至多有兩棵子樹，則第i層的結(jié)點數(shù)=2k-12=2(k+1)-1=2i-1

。6.2.2二叉樹的性質(zhì)性質(zhì)1:在二叉樹的第i層最多有2i-1個結(jié)點(i>=1)性質(zhì)2:深度為k的二叉樹最多有2k–1個結(jié)點（k>=1).證明：基于性質(zhì)1，深度為k的二叉樹上的結(jié)點數(shù)最多為

20+21+

+2k-1=2k-1

6.2.2二叉樹的性質(zhì)性質(zhì)2:深度為k的二叉樹最多有2k–1個結(jié)點（k>=1性質(zhì)3:任一二叉樹,若葉結(jié)點數(shù)是n0,度為2的結(jié)點數(shù)是n2,則n0=n2+1證明：設(shè)二叉樹上結(jié)點總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+16.2.2二叉樹的性質(zhì)性質(zhì)3:任一二叉樹,若葉結(jié)點數(shù)是n0,度為2的結(jié)滿二叉樹(FullBinaryTree):每一層的結(jié)點數(shù)都達到了最大的二叉樹.編號的滿二叉樹:從根開始,由上到下,從左到右地對每個結(jié)點進行編號.也就是說:根的編號是1,一個結(jié)點,若它是雙親的左子女,則它的編號是它的雙親編號的2倍;若它是雙親的右子女,則它的編號是雙親編號的2倍+1.6.2.2二叉樹的性質(zhì)ABCDEFH1234567編號的滿二叉樹滿二叉樹(FullBinaryTree):每一層的結(jié)點完全二叉樹(CompleteBinaryTree):深度為k的滿二叉樹,刪去第k層上最右邊的j(0j<2k-1)個結(jié)點,就得到一個深度為k的完全二叉樹.編號的完全二叉樹:與滿二叉樹編號相同6.2.2二叉樹的性質(zhì)1ABCE234ABCDE12345ABCEFH123456F7完全二叉樹(CompleteBinaryTree):深性質(zhì)4:具有n個結(jié)點的完全二叉樹,其深度為。證明：6.2.2二叉樹的性質(zhì)設(shè)完全二叉樹的深度為k則根據(jù)性質(zhì)2得2k-1-1<n≤2k-1

或者2k-1≤n<2k

即

k-1≤

log2n<

k

因為k只能是整數(shù)，因此，k=log2n

+1

或k=log2n+1性質(zhì)4:具有n個結(jié)點的完全二叉樹,其深度為性質(zhì)5：在編號的完全二叉樹中，對任一結(jié)點i（1≤i≤n）有：（1）若i=1,是根;若i>1，則它的雙親是（2）若2i≤n，則結(jié)點i的左子女是2i;否則無左子女；（3）若2i+1≤n，則結(jié)點i的右子女是2i;否則無右子女；123465ii+12i2i+16.2.2二叉樹的性質(zhì)2i+2性質(zhì)5：在編號的完全二叉樹中，對任一結(jié)點i（1≤i≤n）6.2.3二叉樹的存儲結(jié)構(gòu)一、二叉樹的順序存儲完全二叉樹的順序存儲：ABCEFH123456

ABCEHF0123456ST[]根據(jù)性質(zhì)5知：ST[i]的雙親是ST[],

左子女是ST[2*i]，右子女是ST[2*i+1]．6.2.3二叉樹的存儲結(jié)構(gòu)ABCEFH123456一、二叉樹的順序存儲

ABCEFH0123456789ST[]根據(jù)性質(zhì)5知：ST[i]的雙親是ST[],左子女是ST[2*i],右子女是ST[2*i+1].ABCEFH1234796.2.3二叉樹的存儲結(jié)構(gòu)這樣太浪費空間,適合完全二叉樹一、二叉樹的順序存儲ABCE二、二叉樹的鏈式存儲結(jié)構(gòu)(二叉鏈表)typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;ABCEFHG6.2.3二叉樹的存儲結(jié)構(gòu)ABCEHFG二叉鏈表BTlchilddatarchildLeftchildRightchildBiTNode:二、二叉樹的鏈式存儲結(jié)構(gòu)(二叉鏈表)typedefstr二、二叉樹的鏈式存儲結(jié)構(gòu)(三叉鏈表)lchilddatarchildparentLeftchildRightchildParenttypedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild,*parent;}BiTNode,*BiTree;6.2.3二叉樹的存儲結(jié)構(gòu)BiTNode:二、二叉樹的鏈式存儲結(jié)構(gòu)(三叉鏈表)lchildABCEFHG二、二叉樹的鏈式存儲結(jié)構(gòu)(三叉鏈表)6.2.3二叉樹的存儲結(jié)構(gòu)ABCEHFG三叉鏈表BTABCEFHG二、二叉樹的鏈式存儲結(jié)構(gòu)(三叉鏈表)6.2.6.3遍歷二叉樹和線索二叉樹按照某種搜索路徑訪問二叉樹中的所有結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次。一、遍歷“訪問”的含義特別很廣，如：輸出結(jié)點的信息等。因二叉樹是非線性結(jié)構(gòu)，每個結(jié)點可能有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。6.3遍歷二叉樹和線索二叉樹按照某種搜索前(先)序遍歷中序遍歷后序遍歷NLR123二、遍歷方法NLRLNRLRNNRLRNLRLN6.3遍歷二叉樹和線索二叉樹前(先)序遍歷中序遍歷后序遍歷NLR123二、遍歷方法NL算法思想6.1前序遍歷：若BT非空，則：1.訪問根結(jié)點；2.前序遍歷左子樹；3.前序遍歷右子樹;算法思想6.2中序遍歷：若BT非空，則：1.中序遍歷左子樹；2.訪問根結(jié)點；3.中序遍歷右子樹；算法思想6.3后序遍歷：若BT非空，則：1.后序遍歷左子樹；2.后序遍歷右子樹；3.訪問結(jié)點；6.3遍歷二叉樹和線索二叉樹算法思想6.1算法思想6.2算法思想6.36.3遍歷二叉ABCEFHG例6ABCEFHG前序遍歷(NLR)序列：ABEHGCF中序遍歷(LNR)序列：ABCEFHGEBGHAFC后序遍歷(LRN)序列：ABCEFHGEGHBFCA算法思想6.1前序遍歷：若BT非空，則：1.訪問根結(jié)點；2.前序遍歷左子樹；3.前序遍歷右子樹;6.3遍歷二叉樹和線索二叉樹ABCEFHG例6ABCEFHG前序遍歷(NLR)序列：AB前序遍歷二叉樹的遞歸算法算法6.1VoidPreOrderTraverse(BiTreeBT){ if(BT){ visit(BT); PreOrderTraverse(BT->lchild); PreOrderTraverse(BT->rchild); }//}//endofPreOrderTraverse請同學們自己寫出InOrderTraverse(BT)和PostOrderTraverse(BT)前序遍歷二叉樹的遞歸算法請同學們自己寫出建立二叉樹建立二叉樹的方法很多，我們給出以前序遍歷序列建立二叉樹的方法，但該序列是擴充二叉樹的前序遍歷序列。是擴充的葉結(jié)點，它代表空指針。DBFEAC該擴充二叉樹的前序遍歷序列是：ABD**EF***C**該算法是一遞歸算法，遞歸三要素：1.遞歸出口：當遇到*時，是空。2.建立根。3.建立左子樹和右子樹。建立二叉樹DBFEAC該擴充二叉樹的前序遍歷序列是：ABD*建立二叉樹的算法StatusCreateBiTree(BiTree&BT){//按先序次序輸入二叉樹中結(jié)點的值(一個字符)，空格字符表示空樹，構(gòu)造二叉鏈表表示的二叉樹T.

scanf(&ch)；if(ch==‘’)BT=NULL；else{if(!(BT=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW)；BT->data=ch;／／生成根結(jié)點CreateBiTree(BT->lchild);／／構(gòu)造左子樹CreateBiTree(BT->rchild);／／構(gòu)造右于樹}returnOK；}／／CreateBiTree建立二叉樹的算法ABCDABTBCD^^^^^ABCDABTBCD^^^^^遍歷二叉樹的非遞歸算法：我們先觀察一下三種遍歷行走的路線ABCEFHGDI*********前序遍歷NLR遍歷二叉樹的非遞歸算法：ABCEFHGDI*********#########ABCEFHGDI中序遍歷LNR#########ABCEFHGDI中序遍歷LNR&&&&&&&&&ABCEFHGDI后序遍歷LRN&&&&&&&&&ABCEFHGDI后序遍歷LRN&&&&&&&&&ABCEFHGDI*********#########三種遍歷的訪問位置對比：三種遍歷的路線完全一樣，只是訪問時間不同；前序：第一次經(jīng)過*時訪問中序：第二次經(jīng)過#時訪問后序：第三次經(jīng)過&時訪問&&&&&&&&&ABCEFHGDI*********###遍歷線路的核心規(guī)則是：先左后右；我們用一個棧stack記錄走過的位置，以便返回；

stack中數(shù)據(jù)元素的類型：*BiTNode(或BiTree)函數(shù)：BiTreeP;push(S,p);pop(S,p);

BooleanStackEmpty(S);下面給出基于邏輯結(jié)構(gòu)的算法描述非遞歸中序遍歷二叉樹的算法思想建立棧stack；P指向根；當p不空且stack不空時反復做： 若p不空,p入棧;p指向左子女； 否則：出棧頂元素到p中；訪問p；p指向右子女；4.結(jié)束如何進行前序遍歷？遍歷線路的核心規(guī)則是：先左后右；非遞歸中序遍歷二叉樹的算法思VoidlnorderTraverse(BiTreeBT){

／／采用二叉鏈表存儲結(jié)構(gòu)，中序遍歷二叉樹T的非遞歸算法.

InitStack(S)；p=BT；while(p||!StackEmpty(S)){if(p){push(S，p)；p=p->lchild；}//根指針進棧，遍歷左子樹

else{／／根指針退棧，訪問根結(jié)點，遍歷右子樹

pop(S，p)；visit(p));p=p->rchild；}//else}／／InOrderTraverse非遞歸中序遍歷BT的算法:VoidlnorderTraverse(BiTreeABCDEFGpi&A(1)例ABCDEFGpi&A(1)例ABCDEFGpi&A&B(2)例ABCDEFGpi&A&B(2)例ABCDEFGpi&A&B&C(3)例ABCDEFGpi&A&B&C(3)例p=NULLABCDEFGi&A&B訪問：C(4)例p=NULLABCDEFGi&A&B訪問：C(4)例pABCDEFGi&A訪問：CB(5)例pABCDEFGi&A訪問：CB(5)例ABCDEFGi&A&D訪問：CBp(6)例ABCDEFGi&A&D訪問：CBp(6)例ABCDEFGi&A&D&E訪問：CBp(7)例ABCDEFGi&A&D&E訪問：CBp(7)例ABCDEFGi&A&D訪問：CBEp(8)例ABCDEFGi&A&D訪問：CBEp(8)例ABCDEFGi&A&D&G訪問：CBEP=NULL(9)例ABCDEFGi&A&D&G訪問：CBEP=NULL(9ABCDEFGi&A&D訪問：CBEGp(10)例ABCDEFGi&A&D訪問：CBEGp(10)例ABCDEFGi&A訪問：CBEGDp(11)例ABCDEFGi&A訪問：CBEGDp(11)例ABCDEFGi&A&F訪問：CBEGDp(12)例ABCDEFGi&A&F訪問：CBEGDp(12)例ABCDEFGi&A訪問：CBEGDFp=NULL(13)例ABCDEFGi&A訪問：CBEGDFp=NULLABCDEFGi訪問：CBEGDFAp(14)例ABCDEFGi訪問：CBEGDFAp(14)例ABCDEFGi訪問：CBEGDFAp=NULL(15)例ABCDEFGi訪問：CBEGDFAp=NULL非遞歸后序遍歷二叉樹的算法思想建立棧stack；P指向根；當p不空且stack不空時反復做： 若p不空：(p,L)入棧;p指向左子女； 否則：出棧頂元到p和tag中；若tag==R,則訪問p；p置空；否則（p,R）入棧；并讓p指向右子女；4.結(jié)束后序遍歷時，訪問一個結(jié)點的時間是：第3次經(jīng)過時或第2次反回時或從右邊返回時；如何區(qū)分從左還是右返回的呢？P入棧時帶一標記:向左走時帶L向左走時帶R非遞歸后序遍歷BT的算法非遞歸后序遍歷二叉樹的算法思想后序遍歷時，訪問一個結(jié)點的時間非遞歸的后序遍歷BT算法:（基于二叉鏈表存儲結(jié)構(gòu)）voidPostOrderTraverse(BiTree

BT)

{

InitStack(S)；//建立棧

p=BT;//指向根

while(p||!StackEmpty(S)){

if(p){push((p,L))；

//p帶L入棧

p=p->lchild;}

//p指向左子女

else{ pop(p,e); //出棧頂元到e中

p=e.p;tag=e.tag; if(tag==‘R’){visite(p->data);p=NULL;}//訪問p

else{ push((p,R)); p=p->rchild;}//p指向右子女

}

//else

}

//endofwhile}

//endofpostOrderTraverse(bt)非遞歸的后序遍歷BT算法:（基于二叉鏈表存儲結(jié)構(gòu)）例BEACStart(A,L)入棧(A,L)(B,L)入棧(A,L)(B.L)(B.L)退棧，(A,L)(B,R)入棧(A,L)(B,R)(E,L)入棧(A,L)(B,R)(E,L)(E,L)退棧(A,L)(B,R)(E,R)入棧(A,L)(B,R)(E,P)(E,R)退棧(A,L)(B,R) 訪問E(B,R)退棧(A,L) 訪問B(A,L)退棧(A,R)入棧(A,R)(C,L)入棧(A,R)(C,L)(C,L)退棧(A,R)(C,R)入棧(A,R)(C,R)(C,R)退棧(A,R) 訪問C(A,R)退棧 訪問A1234567891011121314151612345678910111213141516例BEACStart(A,L)入棧(A,L課堂練習前序遍歷序列：EDACBGFE中序遍歷序列：ADCBEFHG試畫出滿足以上序列的二叉樹課堂練習中序遍歷序列：ADCBHFEG后序遍歷序列：ABCDEFGH試畫出滿足以上序列的二叉樹課堂練習課堂練習二、線索二叉樹(ThreadedBinaryTree)目的：利用二叉樹的空指針保存遍歷序列的前驅(qū)和后繼。n個結(jié)點的二叉樹,有2n個指針,只用了n-1個,有n+1個是空指。用空的左指針指向某一遍歷序列的前驅(qū).用空的右指針指向某一遍歷序列的后繼.這兩種指針稱為線索(Thread)。為了區(qū)分線索與真實指針，給結(jié)點增加兩個域Ltag和Rtag二、線索二叉樹(ThreadedBinaryTree)lchild

LtagdataRtagrchildLtag=0:lchild指向結(jié)點的左子女；Ltag=1:lchild指向某一遍歷序列前驅(qū)；Rtag=0:rchild指向結(jié)點的右子女；Rtag=1:rchild指向某一遍歷序列后繼；二、線索二叉樹(ThreadedBinaryTree)lchildLtagdataTypedefenum{Link,Thread}PointerTag;TypedefstructBiThrNode{ ElemTypedata; structBiThrNode*lchild,*rchild;PointerTagLtag,Rtag;}BiThrNode,*BiThrTree;lchildLtagdataRtagrchild二、線索二叉樹(ThreadedBinaryTree)Typedefenum{Link,Thread}Po加了線索的二叉樹是線索二叉樹；給二叉樹加線索的過程是線索化（穿線）；按前序遍歷序列穿線的二叉樹是前序線索二叉樹；按中序遍歷序列穿線的二叉樹是中序線索二叉樹；按后序遍歷序列穿線的二叉樹是后序線索二叉樹；中序線索二叉樹簡稱線索二叉樹；二、線索二叉樹(ThreadedBinaryTree)加了線索的二叉樹是線索二叉樹；二、線索二叉樹(ThreadeABCDE

A

B

D

C

ET先序序列：ABCDE先序線索二叉樹00001111^11二、線索二叉樹(ThreadedBinaryTree)ABCDEABABCDE

A

B

D

C

ET中序序列：BCAED中序線索二叉樹00001111^11^二、線索二叉樹(ThreadedBinaryTree)ABCDEABABCDE

A

B

D

C

ET后序序列：CBEDA后序線索二叉樹0000111111^二、線索二叉樹(ThreadedBinaryTree)ABCDEABDBFEACNULLNULL中序線索二叉樹二、線索二叉樹(ThreadedBinaryTree)DBFEACNULLNULL中序線索二叉樹二、線索二叉樹(TVoidlnorderTraverse(BiTreeBT){

／／采用二叉鏈表存儲結(jié)構(gòu)，中序遍歷二叉樹T的非遞歸算法.

InitStack(S)；p=BT；while(p||!StackEmpty(S)){if(p){push(S，p)；p=p->lchild；}//根指針進棧，遍歷左子樹

else{／／根指針退棧，訪問根結(jié)點，遍歷右子樹

pop(S，p)；visit(p);p=p->rchild；}//else}／／InOrderTraverse非遞歸中序遍歷二叉樹的算法(回憶)VoidlnorderTraverse(BiTree對以二叉鏈表存儲的二叉樹進行中序線索化(非遞歸的)voidInOrderThreading(BiThrTreeBT)

{

InitStack(S);//建立棧

p=BT;pre=NULL;

//p指向根,pre是p的前驅(qū)結(jié)點

while(p||!StackEmpty(S)){

if(p){ push(S,p); //p入棧

p=p->lchild;} //p指向左子女

else{ pop(S,p); //出棧頂元到p中

if(!p->lchild){p->lchild=pre;p.ltag=true;}

if(pre&&!pre->rchild){pre->rchild=p;pre.rtag=true;} pre=p;

p=p->rchild;} //p指向右子女 }//endofwhile}//endofInOrderThreading(BT)visit(p)對以二叉鏈表存儲的二叉樹進行中序線索化(非遞歸的)visi(中序)線索二叉樹的線索給我們提供了足夠的信息,對其進行遍歷時，既不需要遞歸(使用了系統(tǒng)棧),也不需要棧.對(中序)線索二叉樹進行非遞歸遍歷且不需要設(shè)棧時需要主要解決的兩個問題:找到某一次序下的第一個結(jié)點p;2)找出給定結(jié)點p在某一次序中的后繼結(jié)點;(中序)線索二叉樹的線索給我們提供了足夠的信息,對(中序)線關(guān)鍵問題1沿著根的左鏈走,直到無左子女的結(jié)點p，即中序序列中的第一個結(jié)點;p=BT;while(!p.ltag)p=p->lchild;關(guān)鍵問題2，有如下兩種情況：P無右子女：則p->rchild是p的后繼；P有右子女：則p的右子樹中最左的結(jié)點就是p的后繼，方法同關(guān)鍵問題1。if(p.rtag)p=p->rchild;//P無右子女else{p=p->rchild;//P有右子女while(!p.ltag)p=p->lchild;}中序遍歷(中序)線索二叉樹時如何解決這兩個問題:關(guān)鍵問題1關(guān)鍵問題2，有如下兩種情況：中序遍歷(中序)線索二voidInOrderTraverse(BiThrTree

BT){

p=BT;while(!p){

while(!p->ltag)p=p->lchild;

//沿左鏈走直到無左子女的結(jié)點

visit(p);

while(p->rtag&&p){p=p->rchild;visit(p);}

p=p->rchild;

}

}//

inOrderTraverse中序遍歷線索二叉樹的算法voidInOrderTraverse(BiThrTre同理，我們可以前序非遞歸遍歷中序線索二叉樹，同樣不需要遞歸（使用了系統(tǒng)棧）也不需要棧.關(guān)鍵問題1根就是第一個結(jié)點.關(guān)鍵問題2，有如下3種情況：P有左子女：則p左子女是p的后繼；否則P有右子女：則p的右子女是p的后繼;否則P是葉：沿著p的線索走，直到空或一個有右子女的結(jié)點r為止，若空，則p無后繼，否則r的右子女是p的后繼。同理，我們可以前序非遞歸遍歷中序線索二叉樹，關(guān)鍵問題1關(guān)鍵問前序遍歷線索二叉樹的算法voidPreOrderTraverse(BiThrTreeBT){p=BT;while(p){visit(p);if(!p->ltag)p=p->lchild;//P有左子女

elseif(!p->rtag)p=p->rchild;//P有右子女

else{r=p->rchild;

//p是葉

while(r&&r.rtag)r=r->rchild;if(r)p=r->rchild;elsep=r;

}}}

//PreOrderTraverse前序遍歷線索二叉樹的算法1、雙親表示法是一種順序存儲方法，即用數(shù)組存儲。每個結(jié)點有兩個域:data是結(jié)點的數(shù)據(jù)元素；parent是指出該結(jié)點的雙親結(jié)點在數(shù)組中的下標；dataparent一、樹的存儲結(jié)構(gòu)6.4樹的存儲結(jié)構(gòu)PTNode:1、雙親表示法dataparent一、樹的存儲結(jié)構(gòu)6.4樹的雙親表示法說明：#defineMAX-TREE-SIZE100typedefstructPTNode{ ElementTypedata; intparent;//該結(jié)點的雙親的下標}PTNode;typedefstruct{ PTNodenodes[MAX-TREE-SIZE]; intn;//樹的結(jié)點數(shù)}PTree;一、樹的存儲結(jié)構(gòu)樹的雙親表示法說明：一、樹的存儲結(jié)構(gòu)例用雙親法存儲樹A-1B0C0D0E1F2G3H6I6J601234567891011ABCDEFGHIJ0123456789ABCDEFHIJG一、樹的存儲結(jié)構(gòu)例用雙親法存儲樹A-10ABCDEFGHIJ同樣的道理可以存儲森林例用雙親法存儲森林ACDFHIJG023BE145678A-1B-1C0D-1E1F2G3H6I6J6012345678910119一、樹的存儲結(jié)構(gòu)同樣的道理可以存儲森林例用雙親法存儲森林ACDFHIJ2、孩子（子女）表示法

Datachild1child2child3child4……….…childk結(jié)點結(jié)構(gòu)對不同的結(jié)點,k(度)是不同的,因此應取最大數(shù),即樹的度;這種方法不可取;所以最自然的方法是為每個結(jié)點建立一個單鏈表，該單鏈表存儲它的所有孩子，所有結(jié)點組成一個數(shù)組，稱表頭數(shù)組。表頭數(shù)組中每一項稱孩子鏈表頭指針CTBox:(頭結(jié)點)單鏈表中每一項稱孩子結(jié)點(也稱表結(jié)點)：CTNode:一、樹的存儲結(jié)構(gòu)datafirstchildchildnext2、孩子（子女）表示法Datachild1typedefstructCTNode{//孩子結(jié)點（表結(jié)點）

intchild；structCTNode*next；}*ChildPtr；tyPedefstruct{//頭結(jié)點TElemTypedata；ChildPtrfirstchild;}CTBox；typedefstruct{//孩子鏈表頭指針CTBoxnodes[MAX_TREE_SIZE]；intn，r；//結(jié)點數(shù)和根的位置；}CTree；樹的孩子鏈表存儲表示說明：typedefstructCTNode{//孩abcdefhgiacdefghib6012345789datafirstchild12^34^^867^5^^^^如何找雙親結(jié)點2、孩子表示法(子女表示法)

^abcdefhgiacdefghib6012345789da帶雙親的孩子鏈表存儲表示:typedefstructCTNode{//孩子結(jié)點（表結(jié)點）

intchild；structCTNode*next；}*ChildPtr；typedefstruct{//頭結(jié)點TElemTypedata；intparent;ChildPtrfirstchild;}CTBox；typedefstruct{//孩子鏈表頭指針CTBoxnodes[MAX_TREE_SIZE]；intn，r；//結(jié)點數(shù)和根的位置；}CTree；帶雙親的孩子鏈表存儲表示:typedefstructCT帶雙親的孩子鏈表12^^^867^345^^^^^501234678acdefghibdatafirstchild-101124440parentabcdefhgi2、孩子表示法(子女表示法)

帶雙親的孩子鏈表12^^^867^345^^3、孩子兄弟表示法(也稱二叉樹表示法或二叉鏈表表示法)結(jié)點結(jié)構(gòu)（CSNode）:datafirstchildnextsibling一、樹的存儲結(jié)構(gòu)指向該結(jié)點的下一個兄弟指向該結(jié)點的第一個孩子3、孩子兄弟表示法(也稱二叉樹表示法結(jié)點結(jié)構(gòu)（CSNo

typedefstructCSNode{TElemTypedata；structCSNode*firstchild，*nextsihling；}CSNode，*CSTree；樹的孩子鏈表存儲表示typedefstructCSNode{樹的孩子鏈表例用孩子兄弟法存儲樹ABCDEFHIJG0123456789IΛAΛBCDΛEΛΛFΛΛGΛHΛJΛΛ一、樹的存儲結(jié)構(gòu)例用孩子兄弟法存儲樹ABCDEFHIJG01234567樹的遍歷:按根的次序區(qū)分有兩種遍歷次序

(1)先根遍歷:若樹非空，則訪問根結(jié)點;從左到右先根遍歷根的每棵子樹;二、樹與森林的遍歷樹的遍歷:按根的次序區(qū)分有兩種遍歷次序二、樹與森林的遍歷例先根遍歷樹ABCDEFHIJG先根遍歷序列:ABECFDGHIJ二、樹與森林的遍歷例先根遍歷樹ABCDEFHIJG先根遍歷序列:ABE（2）后根遍歷:若樹非空，則從左到右后根次序遍歷根的每棵子樹;訪問根結(jié)點;二、樹與森林的遍歷（2）后根遍歷:二、樹與森林的遍歷例后根遍歷樹后根遍歷序列:EBFCHIJGDAABCDEFHIJG二、樹與森林的遍歷例后根遍歷樹后根遍歷序列:ABCDEFHIJG二、森林的遍歷:森林的遍歷是基于樹的遍歷完成的,對應有兩種遍歷次序:(1)先序遍歷:訪問第一棵樹的根;先序遍歷第一棵樹中的根結(jié)點的子樹森林；先序遍歷其余的樹所構(gòu)成的森林；(2)中序遍歷:中序遍歷第一棵樹的子樹；訪問第一棵樹的根;中序遍歷其余的樹所構(gòu)成的森林；二、樹與森林的遍歷森林的遍歷:二、樹與森林的遍歷先序遍歷森林DHIJGACFBEDHIJGBEACFDGHIJ先序遍歷序列：二、樹與森林的遍歷先序遍歷:訪問第一棵樹的根;先序遍歷第一棵樹中的根結(jié)點的子樹森林；先序遍歷其余的樹所構(gòu)成的森林；先序遍歷森林DHIJGACFBEDHIJGBEACFDGHIABCDEFGHIJ中序遍歷序列：BCDAFEHJIG中序遍歷森林二、樹與森林的遍歷中序遍歷:中序遍歷第一棵樹的子樹；訪問第一棵樹的根;中序遍歷其余的樹所構(gòu)成的森林；ABCDEFGHIJ中序遍歷序列：BCDAFEHJIG中序遍三、森林與二叉樹的轉(zhuǎn)換在森林與二叉樹之間存在一一對應的關(guān)系。1).森林=>二叉樹的轉(zhuǎn)換自然轉(zhuǎn)換法：

凡是兄弟用線連起來，然后去掉雙親到子女的連線，但保留雙親到其第一子女的連線，最后轉(zhuǎn)45°。三、森林與二叉樹的轉(zhuǎn)換在森林與二叉樹之間存在一一對應的例：森林到二叉樹的轉(zhuǎn)換ABCDEFGHIJABCDEFGHIJ前序序列：ABCDEFGHIJ前序序列：ABCDEFGHIJ=三、森林與二叉樹的轉(zhuǎn)換中序序列：BCDAFEHJIG中序序列：BCDAFEHJIG=例：森林到二叉樹的轉(zhuǎn)換ABCDEFGHIJABCDEFGHI2)二叉樹=>森林的轉(zhuǎn)換自然轉(zhuǎn)換法：若某結(jié)點是其雙親的左孩子，則該結(jié)點的右孩子、右孩子的右孩子…,都與該結(jié)點的雙親連接起來,最后去掉所有雙親到右孩子的連線.三、森林與二叉樹的轉(zhuǎn)換2)二叉樹=>森林的轉(zhuǎn)換自然轉(zhuǎn)換法：三、森林與二叉ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ問題提出:在數(shù)據(jù)通信中，用二進制給每個字符編碼,如何使電文總長最短且不產(chǎn)生二義性?根據(jù)字符出現(xiàn)頻率，利用Huffman樹可以構(gòu)造一種不等長的二進制編碼，并且構(gòu)造所得的Huffman編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。6.6Huffman樹及其應用問題提出:在數(shù)據(jù)通信中，用二進制給每個字根據(jù)字符出現(xiàn)頻6.6Huffman樹及其應用最優(yōu)二叉樹（Huffman）如何構(gòu)造最優(yōu)二叉樹如何求哈夫曼編碼6.6Huffman樹及其應用最優(yōu)二叉樹（Huffman）一、哈夫曼樹(最優(yōu)樹)的定義結(jié)點的路徑長度：從根結(jié)點到該結(jié)點的路徑上分支的數(shù)目。樹的路徑長度：樹中每個結(jié)點的路徑長度之和。(結(jié)點)帶權(quán)路徑長度:結(jié)點的路徑長度*結(jié)點的權(quán)=li*wi樹的帶權(quán)路徑長度：樹中所有葉結(jié)點的帶權(quán)路徑長度之和WPL(T)=一、哈夫曼樹(最優(yōu)樹)的定義結(jié)點的路徑長度：從根結(jié)點到該結(jié)設(shè)K={k1,k2,…kn},它們的權(quán)W={w1,w2,…,wn},構(gòu)造以k1,k2,…kn為葉結(jié)點的二叉樹，使得WPL=為最小,則稱之為“最優(yōu)二叉樹”。

一、哈夫曼樹(最優(yōu)樹)的定義設(shè)K={k1,k2,…kn},它們的權(quán)W={w1,w2,…,例W={1,2,4,6},可構(gòu)造出如下的二叉樹：124612466412WPL=(1+2+4+6)*2=26WPL=1+2*2+(4+6)*3=35WPL=6+4*2+(1+2)*3=23(1)(2)(3)根據(jù)定義求Huffman樹的方法是：對給定的n個葉子結(jié)點（外部結(jié)點），構(gòu)造出全部二叉樹并求出其WPL，然后找出WPL最小的樹。當n較大時，顯然這種方法是不可取的。例W={1,2,4,6},可構(gòu)造出如下的二叉樹：1二、構(gòu)造huffman樹算法思想：1.根據(jù)權(quán)值{w1,w2,…,wn}構(gòu)造n個二叉樹F={T1,T2,…,Tn}，其中Ti中是只含權(quán)值為wi

的結(jié)點。2.從F中選兩個權(quán)值最小的二叉樹Ti和Tj，構(gòu)造一個根結(jié)點R,R的權(quán)wR為wi+wj。3.從F中刪除Ti和Tj，加入新的樹R到F中。4.重復2，3直到F中只有一棵樹(或執(zhí)行n-1次)為止。問題:如何證明所構(gòu)造的二叉樹是最優(yōu)樹?二、構(gòu)造huffman樹問題:如何證明所構(gòu)造的二叉樹是最例:已知權(quán)值W={5,6,3,9,7}56379673859例:已知權(quán)值W={5,6,3,9,7}5例:已知權(quán)值W={5,6,3,9,7}5637938576139例:已知權(quán)值W={5,6,3,9,7}5例:已知權(quán)值W={5,6,3,9,7}563797613385917例:已知權(quán)值W={5,6,3,9,7}5例:已知權(quán)值W={5,6,3,9,7}56379385917761330例:已知權(quán)值W={5,6,3,9,7}5用n個葉結(jié)點構(gòu)造出的最優(yōu)二叉樹共有幾個結(jié)點？構(gòu)造最優(yōu)樹時共執(zhí)行n-1次循環(huán)，每次增加一個新結(jié)點，共增加了n-1個結(jié)點，所以結(jié)點總數(shù)一定是n+n-1=2n-1因為n0=n2+1,所以n2=n0-1,又由于在最優(yōu)二叉樹中沒有度為1的結(jié)點,所以在最優(yōu)二叉樹中總的結(jié)點數(shù)為

n+n-1=2n-1Huffman算法的實現(xiàn)：用n個葉結(jié)點構(gòu)造出的最優(yōu)二叉樹共有幾個結(jié)點？構(gòu)造最優(yōu)樹時Huffman編碼：設(shè)字符集為{c1,c2,…,cn},看作葉結(jié)點出現(xiàn)概率為{w1,w2,…,wn},葉結(jié)點的權(quán)（1）構(gòu)造Huffman樹（2）左分支標0，右分支標1（3）根到葉結(jié)點ci的路徑上的二進制編碼就是ci的編碼編碼長度為{l1,l2,…,ln}是葉結(jié)點的路徑長度,則樹的帶權(quán)路徑長度WPL是：Huffman編碼：

根到任何ci的路徑都不會經(jīng)過任何其它ck,因此Huffman編碼是無前綴編碼，即任何一個編碼都不會是另一個編碼的前綴。例：字符集{a,b,c,d,e,f,g,h}出現(xiàn)概率分別是{0.14,0.08,0.11,0.23,0.29,0.05,0.03,0.07}Huffman編碼：根到任何ci的路徑都不會經(jīng)過任何其它ck,因此構(gòu)造Huffman樹：

abchdefg1004258192915823351129147801111111000000(2)編碼：a:110b:1111c:011d:00e:10f:0101g:0100h:1110(3)編碼長度：

WPL=2*0.23+4*0.03+4*0.05+3*0.11+2*0.29+3*0.14+4*0.08+4*0.07=2.710000001111111構(gòu)造Huffman樹：Huffman算法的實現(xiàn)：用數(shù)組存儲Huffman樹，每個數(shù)組元素HTNode包括4個域:123nn+12n-1權(quán)w雙親parent左子女lchild右子女rchild葉子結(jié)點(外部結(jié)點)

內(nèi)部結(jié)點

Huffman算法的實現(xiàn)：123//——哈夫曼樹和哈夫曼編碼的存儲表示——typedefstruct{unsignedintweight；unsignedintparent，lchild，rchild；}HTNode，*HuffmanTree；//動態(tài)分配數(shù)組存儲哈夫曼樹typedefchar**HuffmanCod