算法與數(shù)據(jù)結(jié)構(gòu)課件-DSC6

第六章.樹和二叉樹（Chapter6.TreeandBinaryTree)§6.1樹的定義及基本操作

樹型結(jié)構(gòu)是一種非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，可廣泛應(yīng)用于描述家族關(guān)系或行政組織機(jī)構(gòu)。

樹是n(n≥0)個(gè)結(jié)點(diǎn)的有限集。在一棵非空樹中，有且僅有唯一的根（root）結(jié)點(diǎn)，當(dāng)n>1時(shí)，除根結(jié)點(diǎn)外其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集，它們本身也是一棵樹，稱為根的子樹（subtree）。ABCEFGD一棵樹如右圖所示：

樹還可以用下面的形式化描述來表示：Tree=（D,R）其中：D={ai|ai∈D0,i=1,2,…,n,n≥0}R={H}H為如下描述的二元關(guān)系：1、在D中存在唯一的根元素root，它在關(guān)系H下無前驅(qū)；2、若D-{root}≠φ，則存在D-{root}的一個(gè)劃分D1,...,

Dm(m>0)，對(duì)任意一對(duì)j≠k(1≤j,k≤m)有Dj∩Dk

=φ，且對(duì)任意的i(1≤i≤m)，唯一存在數(shù)據(jù)元素xi∈Di，有<root,xi>∈H；3、對(duì)于D-{root}的劃分，H-{<root,x1>,…,

<root,

xm>}有唯一的劃分H1,

H2,...,

Hm(m>0)，對(duì)任意一對(duì)j≠k(1≤j,k≤m)有Hj∩Hk=φ，且對(duì)任意的i(1≤i≤m)，Hi是Di上的二元關(guān)系，且(Di,Hi)也是一棵符合本定義的樹，稱為root的子樹。樹的一些基本術(shù)語：結(jié)點(diǎn)的度（degree）結(jié)點(diǎn)所擁有的子樹的數(shù)目。葉子結(jié)點(diǎn)（leaf--又稱終端結(jié)點(diǎn)terminalnode）度為零的結(jié)點(diǎn)。度不為零的結(jié)點(diǎn)。孩子（

child--也稱兒子son）結(jié)點(diǎn)的子樹的根稱為結(jié)點(diǎn)的孩子。分支結(jié)點(diǎn)（branchnode--又稱非終端結(jié)點(diǎn)non-terminalnode

）雙親（

parent）結(jié)點(diǎn)是其孩子的雙親。祖先（

forefather）從樹根到雙親的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的祖先。子孫（progeny）以結(jié)點(diǎn)為根的子樹的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子孫。兄弟（sibling）同一父母的所有孩子互稱兄弟。層次（level）樹根為第一層，其孩子為第二層，孫子為第三層，以此類推。有序樹（orderedtree）結(jié)點(diǎn)各子樹從左至右是有秩序的樹稱為有序樹。無序樹（unorderedtree）結(jié)點(diǎn)各子樹沒有秩序的樹稱為無序樹。森林（forest）森林是m(m≥0)棵互不相交的樹的集合。堂兄弟（cousin）雙親在同一層的結(jié)點(diǎn)互稱堂兄弟。深度（depth）樹中結(jié)點(diǎn)的最大層次稱為樹的深度。樹的基本操作：InitiateRootTraverseChildCrt_TreeClearIns_ChildDel_ChildRight_SiblingParent§6.2二叉樹二叉樹（binarytree）是一棵度為二的樹，其孩子有左右之分，也分別都是二叉樹。二叉樹的基本操作：InitiateRootParentL(R)childCrt_btClearIns_L(R)childDel_L(R)childTraverseL(R)sibling性質(zhì)一、在二叉樹的第i層上最多有2i-1

個(gè)結(jié)點(diǎn)（i≥1）。性質(zhì)二、深度為k的二叉樹最多有2k-1個(gè)結(jié)點(diǎn)（k≥1）。性質(zhì)三、對(duì)任一二叉樹，葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。性質(zhì)四、具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。滿二叉樹（fullbinarytree）：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。二叉樹的性質(zhì)：完全二叉樹（completebinarytree）：一棵深度為k的滿二叉樹的第k層的右邊幾個(gè)結(jié)點(diǎn)不存在則為完全二叉樹。性質(zhì)五、對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹從上到下、從左到右進(jìn)行連續(xù)編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1≤i≤n)有：

1、i=1的結(jié)點(diǎn)是樹根，i>1的結(jié)點(diǎn)的父母為i/2；

2、若左右孩子存在，則分別為2i和2i+1結(jié)點(diǎn)。二叉樹的存儲(chǔ)結(jié)構(gòu)：ABDEFC1、順序存儲(chǔ)結(jié)構(gòu)：A、按完全二叉樹存儲(chǔ)ABCDEF1234567ABDEFCB、用父母指針存儲(chǔ)ABCDEF0-11-2-331234562、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：用二叉鏈表存儲(chǔ)A

B

C

DEF∧∧∧∧∧∧∧#definemaxlenuser_supplytypedefelemtypecomptree[maxlen];#definemaxlenuser_supplytypedefstruct{elemtypedata;intparent;}node;structnodebtree[maxlen];typedefstructnode{elemtypedata;structnode*lchild,*rchild;}node,*bitptr;作業(yè)13.

一棵滿k叉樹按層次順序從1開始對(duì)全部結(jié)點(diǎn)編號(hào)，若所求結(jié)點(diǎn)存在，則：1、各層的結(jié)點(diǎn)數(shù)目是多少？2、編號(hào)為n的結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)是多少？3、結(jié)點(diǎn)n的第i個(gè)兒子的編號(hào)是多少？4、結(jié)點(diǎn)n有右兄弟的條件是什么？14.

已知一棵度為m的樹中有ni

個(gè)度為i的結(jié)點(diǎn)，則該樹中有多少個(gè)葉子結(jié)點(diǎn)?！?.3二叉樹的遍歷和線索二叉樹遍歷二叉樹（traversingbinarytree）即按某種搜索順序?qū)Χ鏄渲忻總€(gè)結(jié)點(diǎn)訪問且僅訪問一次。根據(jù)搜索路徑的不同，二叉樹的遍歷分為八種：1、前序遍歷（preordertraversal）DLR2、中序遍歷（inordertraversal）

LDR3、后序遍歷（postordertraversal）LRD4、逆前序遍歷（inverse

preordertraversal）DRL5、逆中序遍歷（inverse

inordertraversal）

RDL6、逆后序遍歷（inverse

postordertraversal）RLD7、按層次遍歷（level-by-leveltraversal）8、按層次逆遍歷（inverselevel-by-leveltraversal）√√√√ABDEFC1、ABDCEF2、DBAECF3、DBEFCA4、ACFEBD5、FCEABD6、FECDBA7、ABCDEF8、ACBFEDvoidPreorder(structnode*t){if(t){visit(t);Preorder(t->lchild);Preorder(t->rchild);}}voidInorder(bitptrt){if(t){

Inorder(t->lchild);visit(t);

Inorder(t->rchild);}}voidPostorder(structnode*t){if(t){

Postorder(t->lchild);

Postorder(t->rchild);visit(t);}}voidPreorder(structnode*t){//前序遍歷的非遞歸算法

Inistack(s);if(t)Push(s,t);while(!Empty(s){Pop(s,t);visit(t);if(t->rchild)Push(s,t->rchild);

if(t->lchild)Push(s,t->lchild);}}voidPostorder(structnode*t){//后序遍歷的非遞歸算法

Inistack(s);while(t||!Empty(s)){while(t){Push(s,(t,‘L’));t=t->lchild;}tag=‘R’;while(!Empty(s)&&(tag==‘R’)){(t,tag)=Pop(s);if(tag=‘L’){Push(s,(t,‘R’));t=t->rchild;}else{visit(t);t=NULL;}}}}voidLevelorder(structnode*t){//按層次遍歷的算法

Iniqueue(q);if(t)Enqueue(q,t);while(!Empty(q)){t=Dequeue(q);visit(t);if(t->lchild)Enqueue(q,t->lchild);if(t->rchild)Eequeue(q,t->rchild);}}能否用任意兩種遍歷的序列來生成一棵唯一的二叉樹？*+aef+/b-cd前序：*+a/b-cd+ef中序：a+b/c-d*e+f表達(dá)式：

(a+b/(c-d))*(e+f)后序：abcd-/+ef+*中序遍歷時(shí)括號(hào)怎么加上？能夠用前序遍歷和中序遍歷或者用中序遍歷和后序遍歷唯一的確定一棵二叉樹，但不能用前序遍歷和后序遍歷唯一的確定一棵樹，為什么？中序遍歷序列是LDR，可以用來分出左右孩子。而前序和后序遍歷是DLR和LRD，不能分出左右孩子。二叉樹遍歷的應(yīng)用：作業(yè)15.

已知在二叉鏈表表示的二叉樹中，root為根結(jié)點(diǎn)，p↑和q↑為二叉樹中兩個(gè)結(jié)點(diǎn)，試編寫算法求距離它們最近的共同祖先。16.

試給出算法求二叉鏈表表示的二叉樹的直徑（高度、最大層次數(shù)）以及長度等于直徑的一條路經(jīng)（從根到葉子的結(jié)點(diǎn)序列）。作業(yè)17.

試給出算法將二叉樹表示的表達(dá)式按中序遍歷輸出并加上相應(yīng)的擴(kuò)號(hào)。線索二叉樹（threadedbinarytree）

在二叉樹的遍歷序列中很容易就找到每個(gè)結(jié)點(diǎn)的前驅(qū)和后繼，但要在二叉樹中找這個(gè)結(jié)點(diǎn)的前驅(qū)和后繼就很困難。如何解決這個(gè)問題呢？

方法之一是將二叉鏈表擴(kuò)展為四叉鏈表，亦即加上指向前驅(qū)和后繼的指針，但這將浪費(fèi)許多空間。有沒有更好的辦法呢?

方法之二即是使用線索二叉樹，該方法是由A.J.Perlis和C.Thornton二人提出的。一棵二叉鏈表表示的二叉樹有n+1個(gè)空指針，可以利用這些空指針來存儲(chǔ)結(jié)點(diǎn)的前驅(qū)和后繼，這即是線索。為了區(qū)分到底是孩子指針還是線索，還需在每個(gè)結(jié)點(diǎn)內(nèi)設(shè)置兩個(gè)標(biāo)志位ltag和rtag，標(biāo)志位為0，表示是孩子指針；標(biāo)志位為1，則表示是線索。其中l(wèi)child指向前驅(qū)，rchild指向后繼。對(duì)二叉樹以某種遍歷使其變?yōu)榫€索二叉樹的過程即稱為線索化。下面是一棵二叉樹的中序線索樹：A

B

C

DEF∧∧∧∧∧∧∧000000000000A

B

C

DEF∧∧∧∧∧∧∧D∧∧10D∧

11B

∧00D∧

11B

01A

00B

01A

00E∧10A

00E11C

00E11C

00F∧01C

00F∧11∧∧F∧11∧將一棵二叉樹線索化的步驟：1、設(shè)前驅(qū)指針為空，當(dāng)前指針為樹根；2、按某種順序遍歷二叉樹：4、若前驅(qū)結(jié)點(diǎn)的右子樹為空，則將標(biāo)志位rtag置為1，并將當(dāng)前指針賦值給rchild；5、將當(dāng)前指針賦值給前驅(qū)指針；6、反復(fù)此過程，直至整棵二叉樹遍歷完為止；7、將前驅(qū)結(jié)點(diǎn)的標(biāo)志位rtag置為1。也可以為線索二叉樹設(shè)置一個(gè)頭結(jié)點(diǎn)，則線索為空時(shí)均指向該頭結(jié)點(diǎn)。3、若當(dāng)前結(jié)點(diǎn)的左子樹為空，則將標(biāo)志位ltag置為1，并將前驅(qū)指針賦值給lchild；如何遍歷一棵二叉線索樹呢？

二叉線索樹的遍歷不需要遞歸，因?yàn)樵诙婢€索樹中能夠很方便地找到當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)。因此，對(duì)有n個(gè)結(jié)點(diǎn)的二叉線索樹，可以在O(n)時(shí)間內(nèi)遍歷完該樹。

線索二叉樹優(yōu)點(diǎn)是節(jié)省了空間，但插入和刪除結(jié)點(diǎn)則非常麻煩，時(shí)間復(fù)雜度和線索化一棵二叉樹相同。因此，在插入和刪除結(jié)點(diǎn)時(shí)可先將線索二叉樹還原為一般二叉樹，待插入和刪除結(jié)點(diǎn)完成后再對(duì)其線索化?！?.4樹和森林樹的存儲(chǔ)結(jié)構(gòu)：1、雙親表示法ABCEFGDABCDEFG011214412345672、孩子表示法可以用多重鏈表來表示，但由于各結(jié)點(diǎn)的度不一樣，因此，用多重鏈表表示會(huì)有很多浪費(fèi)空間。解決的方法是將各結(jié)點(diǎn)的所有孩子組成一個(gè)單鏈表即可。3、孩子兄弟表示法用二叉鏈表表示，因此又稱為二叉樹表示法。左鏈指向結(jié)點(diǎn)的第一個(gè)孩子，右鏈指向結(jié)點(diǎn)的兄弟。A∧B∧CD∧∧E∧∧F∧G∧ABCDEFG234576∧∧∧∧∧∧∧12345674、帶右鏈的先根序表示法主體順序按樹的先根序遍歷，右鏈指向兄弟。5、帶左鏈的層次序列表示法按孩子兄弟表示法進(jìn)行轉(zhuǎn)換。ABECDFG04050701234567ABCDEFG25060001234567森林與二叉樹的轉(zhuǎn)換：孩子鏈兄弟鏈樹的遍歷：1、先根序遍歷：與相應(yīng)二叉樹的前序遍歷序列相同。2、后根序遍歷：與相應(yīng)二叉樹的什么遍歷序列相同？主體順序按樹的層次遍歷，左鏈指向孩子。2、后根序遍歷：與相應(yīng)二叉樹的中序遍歷相同。第三次上機(jī)作業(yè)設(shè)二叉樹結(jié)點(diǎn)值為大寫字母，輸入二叉樹的前序遍歷和中序遍歷序列，生成此二叉樹，輸出該二叉樹的后序遍歷和按層次遍歷序列。輸入某結(jié)點(diǎn)值，在二叉樹中查找該結(jié)點(diǎn)，若該結(jié)點(diǎn)存在，則輸出從根到該結(jié)點(diǎn)的路徑，否則給出不存在信息?！?.5霍夫曼樹及其應(yīng)用霍夫曼樹（Huffmantree），也稱最優(yōu)樹（optimaltree），是一種帶權(quán)外路徑長度（weightedpathlength）最短的樹。路徑長度是指樹中兩個(gè)結(jié)點(diǎn)間路徑上所含有的分支數(shù)目。樹的路徑長度是指從樹根到每一結(jié)點(diǎn)的路徑長度之和。帶權(quán)路徑長度是指結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)的權(quán)之積。設(shè)各葉子結(jié)點(diǎn)的路徑長度為lk，權(quán)為wk

，則該樹的帶權(quán)外路徑長度為：

WPL=∑wklk

。k=1n則WPL最小的二叉樹即為最優(yōu)二叉樹或霍夫曼樹。樹的帶權(quán)外路徑長度是樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和?；舴蚵鼧涞臉?gòu)造：1、把給定的n個(gè)權(quán)值集合的各結(jié)點(diǎn)均作為一棵樹；2、從這n棵樹中選取兩個(gè)權(quán)值最小的結(jié)點(diǎn)組成新樹；3、將這兩個(gè)結(jié)點(diǎn)的權(quán)值之和作為新樹樹根的權(quán)值；4、將這兩個(gè)結(jié)點(diǎn)從n棵樹中刪去，把新樹樹根加入；5、原來的n棵樹減少為n-1棵樹；6、重復(fù)步驟2--5，直到n=1即為所求?；舴蚵鼧渲谐~子結(jié)點(diǎn)外，所有分支結(jié)點(diǎn)的度均為2，葉子結(jié)點(diǎn)（外部結(jié)點(diǎn)）可看成是由分支結(jié)點(diǎn)（內(nèi)部結(jié)點(diǎn)）組成的樹擴(kuò)充出來的，因此，霍夫曼樹是一棵擴(kuò)充二叉樹（extendedbinarytree）。例：已知字符A、B、C、D、E、F、G，使用頻度分別為：0.25、0.1、0.15、0.06、0.3、0.05、0.09，試以此構(gòu)造霍夫曼樹。GB0.19A0.44FD0.11C0.26E0.5611、0.250.10.150.06