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

樹型結構是一種非常重要的非線性數據結構，可廣泛應用于描述家族關系或行政組織機構。

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

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

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

=φ，且對任意的i(1≤i≤m)，唯一存在數據元素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上的二元關系，且(Di,Hi)也是一棵符合本定義的樹，稱為root的子樹。樹的一些基本術語：結點的度（degree）結點所擁有的子樹的數目。葉子結點（leaf--又稱終端結點terminalnode）度為零的結點。度不為零的結點。孩子（

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

）雙親（

parent）結點是其孩子的雙親。祖先（

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

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

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

2、若左右孩子存在，則分別為2i和2i+1結點。二叉樹的存儲結構：ABDEFC1、順序存儲結構：A、按完全二叉樹存儲ABCDEF1234567ABDEFCB、用父母指針存儲ABCDEF0-11-2-331234562、鏈式存儲結構：用二叉鏈表存儲A

B

C

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

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

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

個度為i的結點，則該樹中有多少個葉子結點。§6.3二叉樹的遍歷和線索二叉樹遍歷二叉樹（traversingbinarytree）即按某種搜索順序對二叉樹中每個結點訪問且僅訪問一次。根據搜索路徑的不同，二叉樹的遍歷分為八種：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，不能分出左右孩子。二叉樹遍歷的應用：作業15.

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

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

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

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

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

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

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

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

，則該樹的帶權外路徑長度為：

WPL=∑wklk

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