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

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

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

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

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

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

初始條件：樹T存在。操作結(jié)果，銷毀樹T。(3)對(duì)應(yīng)于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中某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回cur_e的值。Assign(T，cur_e，value)

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

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

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

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

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

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

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

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

初始條件；樹T存在。操作結(jié)果：按某種次序?qū)的每個(gè)結(jié)點(diǎn)進(jìn)行遍歷。}ADTTree基本操作:InsertChild(&T，&P，i，c)；基本操作:樹的表示方法：1.樹形表示：6.1樹（Tree）的定義和基本術(shù)語ABCDEFHIJG2.括號(hào)表示(廣義表表示)：(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é)點(diǎn)的有限集，在任意非空樹中：(1)有且僅有一個(gè)特定的稱為根（Root）的結(jié)點(diǎn);(2)當(dāng)n>1時(shí)，其余的結(jié)點(diǎn)最多分為2個(gè)互不相交的子集T1,T2,每個(gè)又都是二叉樹，分別稱為根的左子樹和右子樹.6.2二叉樹（BinaryTree）二叉樹是另一種樹形結(jié)構(gòu)。6.2二叉樹（BinaryTr例6.2.1二叉樹的定義ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹二叉樹例6.2.1二叉樹的定義ABCDEFGHK根結(jié)點(diǎn)左子樹右子注意：二叉樹不是樹，它是另外單獨(dú)定義的一種樹形結(jié)構(gòu)，并非一般樹的特例。它的子樹有順序規(guī)定，分為左子樹和右子樹。不能隨意顛倒。注意：二叉樹不是樹，它是另外單獨(dú)定義的一種樹形結(jié)構(gòu)，并非一般二叉樹的5種基本形態(tài)：1空2只有根3右子樹空4左子樹空5左、右子樹非空具有3個(gè)結(jié)點(diǎn)的二叉樹可能有幾種不同形態(tài)？二叉樹的5種基本形態(tài)：1空2只有根3右子樹空4左子抽象數(shù)據(jù)類型二叉樹的定義：ADTBinaryTree{數(shù)據(jù)對(duì)象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}的一個(gè)劃分{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中某個(gè)結(jié)點(diǎn)。

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

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

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

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

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

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

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

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

Rightsibling(T，e)；

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

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

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

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

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

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

初始條件：二叉樹T存在。操作結(jié)果：后序遍歷T中每個(gè)結(jié)點(diǎn)一次且僅一次。基本操作:LevelOrderTraverse(T)；

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

個(gè)結(jié)點(diǎn)(i>=1).用歸納法證明：

歸納基：

歸納假設(shè)：

歸納證明：i=1

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

2=2(k+1)-1=2i-1

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

20+21+

+2k-1=2k-1

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

或者2k-1≤n<2k

即

k-1≤

log2n<

k

因?yàn)閗只能是整數(shù)，因此，k=log2n

+1

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

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

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

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

scanf(&ch)；if(ch==‘’)BT=NULL；else{if(!(BT=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW)；BT->data=ch;／／生成根結(jié)點(diǎn)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*********#########三種遍歷的訪問位置對(duì)比：三種遍歷的路線完全一樣，只是訪問時(shí)間不同；前序：第一次經(jīng)過*時(shí)訪問中序：第二次經(jīng)過#時(shí)訪問后序：第三次經(jīng)過&時(shí)訪問&&&&&&&&&ABCEFHGDI*********###遍歷線路的核心規(guī)則是：先左后右；我們用一個(gè)棧stack記錄走過的位置，以便返回；

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

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

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

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

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

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指向根；當(dāng)p不空且stack不空時(shí)反復(fù)做： 若p不空：(p,L)入棧;p指向左子女； 否則：出棧頂元到p和tag中；若tag==R,則訪問p；p置空；否則（p,R）入棧；并讓p指向右子女；4.結(jié)束后序遍歷時(shí)，訪問一個(gè)結(jié)點(diǎn)的時(shí)間是：第3次經(jīng)過時(shí)或第2次反回時(shí)或從右邊返回時(shí)；如何區(qū)分從左還是右返回的呢？P入棧時(shí)帶一標(biāo)記:向左走時(shí)帶L向左走時(shí)帶R非遞歸后序遍歷BT的算法非遞歸后序遍歷二叉樹的算法思想后序遍歷時(shí)，訪問一個(gè)結(jié)點(diǎn)的時(shí)間非遞歸的后序遍歷BT算法:（基于二叉鏈表存儲(chǔ)結(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算法:（基于二叉鏈表存儲(chǔ)結(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課堂練習(xí)前序遍歷序列：EDACBGFE中序遍歷序列：ADCBEFHG試畫出滿足以上序列的二叉樹課堂練習(xí)中序遍歷序列：ADCBHFEG后序遍歷序列：ABCDEFGH試畫出滿足以上序列的二叉樹課堂練習(xí)課堂練習(xí)二、線索二叉樹(ThreadedBinaryTree)目的：利用二叉樹的空指針保存遍歷序列的前驅(qū)和后繼。n個(gè)結(jié)點(diǎn)的二叉樹,有2n個(gè)指針,只用了n-1個(gè),有n+1個(gè)是空指。用空的左指針指向某一遍歷序列的前驅(qū).用空的右指針指向某一遍歷序列的后繼.這兩種指針稱為線索(Thread)。為了區(qū)分線索與真實(shí)指針，給結(jié)點(diǎn)增加兩個(gè)域Ltag和Rtag二、線索二叉樹(ThreadedBinaryTree)lchild

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

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

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

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

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

{

InitStack(S);//建立棧

p=BT;pre=NULL;

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

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

BT){

p=BT;while(!p){

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

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

visit(p);

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

p=p->rchild;

}

}//

inOrderTraverse中序遍歷線索二叉樹的算法voidInOrderTraverse(BiThrTre同理，我們可以前序非遞歸遍歷中序線索二叉樹，同樣不需要遞歸（使用了系統(tǒng)棧）也不需要棧.關(guān)鍵問題1根就是第一個(gè)結(jié)點(diǎn).關(guān)鍵問題2，有如下3種情況：P有左子女：則p左子女是p的后繼；否則P有右子女：則p的右子女是p的后繼;否則P是葉：沿著p的線索走，直到空或一個(gè)有右子女的結(jié)點(diǎn)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、雙親表示法是一種順序存儲(chǔ)方法，即用數(shù)組存儲(chǔ)。每個(gè)結(jié)點(diǎn)有兩個(gè)域:data是結(jié)點(diǎn)的數(shù)據(jù)元素；parent是指出該結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中的下標(biāo)；dataparent一、樹的存儲(chǔ)結(jié)構(gòu)6.4樹的存儲(chǔ)結(jié)構(gòu)PTNode:1、雙親表示法dataparent一、樹的存儲(chǔ)結(jié)構(gòu)6.4樹的雙親表示法說明：#defineMAX-TREE-SIZE100typedefstructPTNode{ ElementTypedata; intparent;//該結(jié)點(diǎn)的雙親的下標(biāo)}PTNode;typedefstruct{ PTNodenodes[MAX-TREE-SIZE]; intn;//樹的結(jié)點(diǎn)數(shù)}PTree;一、樹的存儲(chǔ)結(jié)構(gòu)樹的雙親表示法說明：一、樹的存儲(chǔ)結(jié)構(gòu)例用雙親法存儲(chǔ)樹A-1B0C0D0E1F2G3H6I6J601234567891011ABCDEFGHIJ0123456789ABCDEFHIJG一、樹的存儲(chǔ)結(jié)構(gòu)例用雙親法存儲(chǔ)樹A-10ABCDEFGHIJ同樣的道理可以存儲(chǔ)森林例用雙親法存儲(chǔ)森林ACDFHIJG023BE145678A-1B-1C0D-1E1F2G3H6I6J6012345678910119一、樹的存儲(chǔ)結(jié)構(gòu)同樣的道理可以存儲(chǔ)森林例用雙親法存儲(chǔ)森林ACDFHIJ2、孩子（子女）表示法

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

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

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

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

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

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

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

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

的結(jié)點(diǎn)。2.從F中選兩個(gè)權(quán)值最小的二叉樹Ti和Tj，構(gòu)造一個(gè)根結(jié)點(diǎn)R,R的權(quán)wR為wi+wj。3.從F中刪除Ti和Tj，加入新的樹R到F中。4.重復(fù)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個(gè)葉結(jié)點(diǎn)構(gòu)造出的最優(yōu)二叉樹共有幾個(gè)結(jié)點(diǎn)？構(gòu)造最優(yōu)樹時(shí)共執(zhí)行n-1次循環(huán)，每次增加一個(gè)新結(jié)點(diǎn)，共增加了n-1個(gè)結(jié)點(diǎn)，所以結(jié)點(diǎn)總數(shù)一定是n+n-1=2n-1因?yàn)閚0=n2+1,所以n2=n0-1,又由于在最優(yōu)二叉樹中沒有度為1的結(jié)點(diǎn),所以在最優(yōu)二叉樹中總的結(jié)點(diǎn)數(shù)為

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