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

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

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

樹是n(n≥0)個結(jié)點的有限集。在一棵非空樹中，有且僅有唯一的根（root）結(jié)點，當(dāng)n>1時，除根結(jié)點外其余結(jié)點可分為m(m>0)個互不相交的有限集，它們本身也是一棵樹，稱為根的子樹（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}的一個劃分D1,...,

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

=φ，且對任意的i(1≤i≤m)，唯一存在數(shù)據(jù)元素xi∈Di，有<root,xi>∈H；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的子樹。樹的一些基本術(shù)語：結(jié)點的度（degree）結(jié)點所擁有的子樹的數(shù)目。葉子結(jié)點（leaf--又稱終端結(jié)點terminalnode）度為零的結(jié)點。度不為零的結(jié)點。孩子（

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

）雙親（

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

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

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

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

2、若左右孩子存在，則分別為2i和2i+1結(jié)點。二叉樹的存儲結(jié)構(gòu)：ABDEFC1、順序存儲結(jié)構(gòu)：A、按完全二叉樹存儲ABCDEF1234567ABDEFCB、用父母指針存儲ABCDEF0-11-2-331234562、鏈?zhǔn)酱鎯Y(jié)構(gòu)：用二叉鏈表存儲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開始對全部結(jié)點編號，若所求結(jié)點存在，則：1、各層的結(jié)點數(shù)目是多少？2、編號為n的結(jié)點的父結(jié)點的編號是多少？3、結(jié)點n的第i個兒子的編號是多少？4、結(jié)點n有右兄弟的條件是什么？14.

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

個度為i的結(jié)點，則該樹中有多少個葉子結(jié)點?！?.3二叉樹的遍歷和線索二叉樹遍歷二叉樹（traversingbinarytree）即按某種搜索順序?qū)Χ鏄渲忻總€結(jié)點訪問且僅訪問一次。根據(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表達式：

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

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

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

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

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

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

方法之二即是使用線索二叉樹，該方法是由A.J.Perlis和C.Thornton二人提出的。一棵二叉鏈表表示的二叉樹有n+1個空指針，可以利用這些空指針來存儲結(jié)點的前驅(qū)和后繼，這即是線索。為了區(qū)分到底是孩子指針還是線索，還需在每個結(jié)點內(nèi)設(shè)置兩個標(biāo)志位ltag和rtag，標(biāo)志位為0，表示是孩子指針；標(biāo)志位為1，則表示是線索。其中l(wèi)child指向前驅(qū)，rchild指向后繼。對二叉樹以某種遍歷使其變?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é)點的右子樹為空，則將標(biāo)志位rtag置為1，并將當(dāng)前指針賦值給rchild；5、將當(dāng)前指針賦值給前驅(qū)指針；6、反復(fù)此過程，直至整棵二叉樹遍歷完為止；7、將前驅(qū)結(jié)點的標(biāo)志位rtag置為1。也可以為線索二叉樹設(shè)置一個頭結(jié)點，則線索為空時均指向該頭結(jié)點。3、若當(dāng)前結(jié)點的左子樹為空，則將標(biāo)志位ltag置為1，并將前驅(qū)指針賦值給lchild；如何遍歷一棵二叉線索樹呢？

二叉線索樹的遍歷不需要遞歸，因為在二叉線索樹中能夠很方便地找到當(dāng)前結(jié)點的后繼結(jié)點。因此，對有n個結(jié)點的二叉線索樹，可以在O(n)時間內(nèi)遍歷完該樹。

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

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

WPL=∑wklk

。k=1n則WPL最小的二叉樹即為最優(yōu)二叉樹或霍夫曼樹。樹的帶權(quán)外路徑長度是樹中所有葉子結(jié)點的帶權(quán)路徑長度之和?；舴蚵鼧涞臉?gòu)造：1、把給定的n個權(quán)值集合的各結(jié)點均作為一棵樹；2、從這n棵樹中選取兩個權(quán)值最小的結(jié)點組成新樹；3、將這兩個結(jié)點的權(quán)值之和作為新樹樹根的權(quán)值；4、將這兩個結(jié)點從n棵樹中刪去，把新樹樹根加入；5、原來的n棵樹減少為n-1棵樹；6、重復(fù)步驟2--5，直到n=1即為所求?；舴蚵鼧渲谐~子結(jié)點外，所有分支結(jié)點的度均為2，葉子結(jié)點（外部結(jié)點）可看成是由分支結(jié)點（內(nèi)部結(jié)點）組成的樹擴充出來的，因此，霍夫曼樹是一棵擴充二叉樹（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