數(shù)據(jù)結構與算法-第五章 Trees

數(shù)據(jù)結構與算法DataStructuresandAlgorithmAnalysis信息工程學院SchoolofInformationEngineering第5章樹形結構(Trees)5.1樹的基本概念(Basicconceptoftree)

5.2二叉樹概念和性質(Propertyandconceptofbinarytree)5.3二叉樹存儲結構(Physicalstoragestructureofbinarytree)5.4二叉樹的遍歷(Binarytreetraversals)5.5二叉樹的基本運算及其實現(xiàn)(Algorithmimplementationandbasicoperationsofbinarytree)5.6二叉樹的構造(Constructionofbinarytree)5.8哈夫曼樹(Huffmantree)

Summary5.7線索二叉樹(Threadedbinarytree)5.1.1樹的定義(Definition)

5.1.3樹的基本術語(Basicterminology)5.1.2樹的表示(Representation)5.1.4樹的性質(Property)5.1.5樹的基本運算(Basicoperation)5.1.6樹的存儲結構(Physicalstructure)5.1樹的基本概念(Basicconceptoftree)

5.1.1樹的定義(Definition)形式化定義：

樹：T＝{K,R}。K是包含n個結點的有窮集合(n>0),關系R滿足以下條件:

(1)有且僅有一個結點k0∈K,它對于關系R來說沒有前驅結點,結點k0稱作樹的根。(2)除結點k0外,K中的每個結點對于關系R來說都有且僅有一個前驅結點。(3)K中每個結點對于關系R來說可以有多個后繼結點。遞歸定義：樹是由n(n≥0)個結點組成的有限集合(記為T)。其中,

如果n=0,它是一棵空樹,這是樹的特例；如果n>0,這n個結點中存在(有僅存在)一個結點作為樹的根結點,簡稱為根(root),其余結點可分為m(m>0)個互不相交的有限集T1,,T2,…,Tm,其中每一棵子集本身又是一棵符合本定義的樹,稱為根root的子樹。A只有根結點的樹ABCDEFGHIJKLM有子樹的樹根子樹5.1.2樹的表示(Representation)(1)樹形表示法。這是樹的最基本的表示,使用一棵倒置的樹表示樹結構,非常直觀和形象。下圖就是采用這種表示法。(2)文氏圖表示法。使用集合以及集合的包含關系描述樹結構。下圖就是樹的文氏圖表示法。(3)凹入表示法。使用線段的伸縮描述樹結構。下圖是樹的凹入表示法。(4)括號表示法。

將樹的根結點寫在括號的左邊,除根結點之外的其余結點寫在括號中并用逗號間隔來描述樹結構。下圖是樹的括號表示法。5.1.3樹的基本術語(Basicterminology)結點(node)——度不為零的結點稱為非終端結點，又叫分支結點。度為零的結點稱為終端結點或葉結點。結點的度(degree)——結點擁有的子樹數(shù)葉子(leaf)——度為0的結點孩子(child)——在一棵樹中，每個結點的后繼雙親(parents)——孩子結點的上層結點叫該結點的~兄弟(sibling)——同一雙親的孩子樹的度(degree)——一棵樹中最大的結點度數(shù)結點的層次(level)——從根結點算起，根為第一層，它的孩子為第二層……深度(depth)——樹中結點的最大層次數(shù)祖先(ancestor)----從根到該結點所經(jīng)分支上的所有結點堂兄弟(cousin)——雙親在同一層次的結點有序樹(orderedtree)——將樹中結點的各個子樹看成從左至右是有次序的第一孩子(firstchild)----有序樹中最左邊的子樹的根森林(forest)——m(m0)棵互不相交的樹的集合對樹中各個結點而言，其子樹的集合即為森林ABCDEFGHIJKLM結點A的度：3結點B的度：2結點M的度：0葉子：K，L，F(xiàn)，G，M，I，J結點A的孩子：B，C，D結點B的孩子：E，F(xiàn)結點I的雙親：D結點L的雙親：E結點B，C，D為兄弟結點K，L為兄弟樹的度：3結點A的層次：1結點M的層次：4樹的深度：4結點F，G為堂兄弟結點A是結點F，G的祖先5.1.4樹的性質(Property)Property1樹中的結點數(shù)等于所有結點的度數(shù)加1。Prove：根據(jù)樹的定義,在一棵樹中,除樹根結點外,每個結點有且僅有一個前驅結點。也就是說,每個結點與指向它的一個分支一一對應,所以除樹根之外的結點數(shù)等于所有結點的分支數(shù)(度數(shù)),從而可得樹中的結點數(shù)等于所有結點的度數(shù)加1。Property2度為m的樹中第i層上至多有mi-1個結點,這里應有i≥1。

Prove(采用數(shù)學歸納法)

對于第一層,因為樹中的第一層上只有一個結點,即整個樹的根結點,而由i=1代入mi-1,得mi-1=m1-1=1,也同樣得到只有一個結點,顯然結論成立。

假設對于第(i-1)層(i＞1)命題成立,即度為m的樹中第(i-1)層上至多有mi-2個結點,則根據(jù)樹的度的定義,度為m的樹中每個結點至多有m個孩子結點,所以第i層上的結點數(shù)至多為第(i-1)層上結點數(shù)的m倍,即至多為mi-2×m=mi-1個,這與命題相同,故命題成立。Property3高度為h的m次樹至多有個結點。Prove：由樹的性質2可知,第i層上最多結點數(shù)為mi-1(i=1,2,…,h),顯然當高度為h的m次樹(即度為m的樹)上每一層都達到最多結點數(shù)時,整個m次樹具有最多結點數(shù),因此有：整個樹的最多結點數(shù)=每一層最多結點數(shù)之和=m0+m1+m2+…+mh-1=。Property4具有n個結點的m次樹的最小高度為logm(n(m-1)+1)。Prove：設具有n個結點的m次樹的高度為h,若在該樹中前h-1層都是滿的,即每一層的結點數(shù)都等于mi-1個(1≤i≤h-1),第h層(即最后一層)的結點數(shù)可能滿,也可能不滿,則該樹具有最小的高度。其高度h可計算如下：根據(jù)樹的性質3可得： ＜n≤乘(m-1)后得： mh-1＜n(m-1)+1≤mh以m為底取對數(shù)后得：h-1＜logm(n(m-1)+1)≤h即 logm(n(m-1)+1)≤h＜logm(n(m-1)+1)+1因h只能取整數(shù),所以 h=logm(n(m-1)+1)結論得證。5.1.5樹的基本運算(Basicoperation)Treeoperationcanbeclassfiedintothreetypes:

First,尋找滿足某種特定關系的結點,如尋找當前結點的雙親結點等；Second,插入或刪除某個結點,如在樹的當前結點上插入一個新結點或刪除當前結點的第i個孩子結點等；Third,遍歷樹中每個結點,這里著重介紹。樹的遍歷(traversal)運算是指按某種方式訪問樹中的每一個結點且每一個結點只被訪問一次。樹的遍歷運算的算法主要有先根遍歷和后根遍歷兩種。注意,下面的先根遍歷和后根遍歷算法都是遞歸的。1.先根遍歷(PreorderTraversal)

先根遍歷過程為：(1)訪問根結點；(2)按照從左到右的次序先根遍歷根結點的每一棵子樹。2.后根遍歷(PostorderTraversal)后根遍歷過程為：(1)按照從左到右的次序后根遍歷根結點的每一棵子樹；(2)訪問根結點。ABCDEFGHIJKLMNO先根遍歷：后根遍歷：層次遍歷：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO5.1.6樹的存儲結構(Physicalstructure)1.雙親存儲結構

這種存儲結構是一種順序存儲結構,用一組連續(xù)空間存儲樹的所有結點,同時在每個結點中附設一個偽指針指示其雙親結點的位置。樹的雙親存儲結構示意圖2.孩子鏈存儲結構孩子鏈存儲結構可按樹的度(即樹中所有結點度的最大值)設計結點的孩子結點指針域個數(shù)。下圖(a)的樹對應的孩子鏈存儲結構如圖(b)所示。樹的孩子鏈存儲結構示意圖3.孩子兄弟鏈存儲結構

孩子兄弟鏈存儲結構是為每個結點設計三個域：一個數(shù)據(jù)元素域,一個該結點的第一個孩子結點指針域,一個該結點的下一個兄弟結點指針域。下圖(a)的樹對應的孩子兄弟鏈存儲結構如圖(b)所示。樹的孩子兄弟鏈存儲結構示意圖5.2.1二叉樹概念(Concept)5.2.2二叉樹性質(Property)5.2.3二叉樹與樹、森林之間的轉換(Transformationbetweenbinarytreeandtree,binarytreeandforest)5.2二叉樹概念和性質(Propertyandconceptofbinarytree)5.2.1二叉樹的概念(Binarytree)另一種樹型結構。Characteristic每個結點至多只有二棵子樹(即不存在度大于2的結點)二叉樹的子樹有左、右之分，且其次序不能任意顛倒BasicformsA只有根結點的二叉樹空二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空在一棵二叉樹中,如果所有分支結點都有左孩子結點和右孩子結點,并且葉結點都集中在二叉樹的最下一層,稱為滿二叉樹(FullBinaryTree)?？梢詫M二叉樹的結點進行連續(xù)編號,約定編號從樹根為1開始,按照層數(shù)從小到大、同一層從左到右的次序進行。若二叉樹中最多只有最下面兩層的結點的度數(shù)可以小于2,并且最下面一層的葉結點都依次排列在該層最左邊的位置上,稱為完全二叉樹(CompleteBinaryTree)。

深度為k，有n個結點的二叉樹當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱為~

12311458912136710141512311458912671012345671234565.2.2二叉樹性質(Property)Property1非空二叉樹上葉結點數(shù)等于雙分支結點數(shù)加1。

證明：設二叉樹上葉結點數(shù)為n0,單分支結點數(shù)為n1,雙分支結點數(shù)為n2,則總結點數(shù)=n0+n1+n2。

在一棵二叉樹中,所有結點的分支數(shù)(即度數(shù))應等于單分支結點數(shù)加上雙分支結點數(shù)的2倍,即總的分支數(shù)=n1+2n2。由于二叉樹中除根結點以外,每個結點都有惟一的一個分支指向它,因此二叉樹中有：

總的分支數(shù)=總結點數(shù)-1。由上述三個等式可得：n1+2n2=n0+n1+n2-1即：n0=n2+1Property2非空二叉樹上第i層上至多有2i-1個結點,這里應有i≥1。證明：用歸納法證明之

i=1時，只有一個根結點，是對的假設對所有j(1j<i)命題成立，即第j層上至多有個結點那么，第i-1層至多有個結點又二叉樹每個結點的度至多為2第i層上最大結點數(shù)是第i-1層的2倍，即故命題得證Property3高度為h的二叉樹至多有2h-1個結點(h≥1)證明：由性質2，可得深度為k的二叉樹最大結點數(shù)是Property4對完全二叉樹中編號為i的結點(1≤i≤n,n≥1,n為結點數(shù))有：

(1)若i≤n/2,即2i≤n,則編號為i的結點為分支結點,否則為葉子結點。(2)若n為奇數(shù),則每個分支結點都既有左孩子結點,也有右孩子結點；若n為偶數(shù),則編號最大的分支結點(編號為)只有左孩子結點,沒有右孩子結點,其余分支結點都有左、右孩子結點。

(3)若編號為i的結點有左孩子結點,則左孩子結點的編號為2i；若編號為i的結點有右孩子結點,則右孩子結點的編號為(2i+1)。(4)除樹根結點外,若一個結點的編號為i,則它的雙親結點的編號為i/2,也就是說,當i為偶數(shù)時,其雙親結點的編號為i/2,它是雙親結點的左孩子結點,當i為奇數(shù)時,其雙親結點的編號為(i-1)/2,它是雙親結點的右孩子結點。Property5具有n個(n＞0)結點的完全二叉樹的高度為log2n+1或log2n+1。

由完全二叉樹的定義和二叉樹的性質3可推出。5.2.3二叉樹與樹、森林之間的轉換(Transformation)1、將樹轉換成二叉樹(TreetoBinaryTree)加線：在兄弟之間加一連線抹線：對每個結點，除了其左孩子外，去除其與其余孩子之間的關系旋轉：以樹的根結點為軸心，將整樹順時針轉45°ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹轉換成的二叉樹其右子樹一定為空2、將二叉樹轉換成樹(BinaryTreetoTree)加線：若p結點是雙親結點的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線連起抹線：抹掉原二叉樹中雙親與右孩子之間的連線調整：將結點按層次排列，形成樹結構ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI3、森林轉換成二叉樹(ForesttoBinaryTree)將各棵樹分別轉換成二叉樹將每棵樹的根結點用線相連以第一棵樹根結點為二叉樹的根，再以根結點為軸心，順時針旋轉，構成二叉樹型結構ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ4、二叉樹轉換成森林(BinaryTreetoForest)抹線：將二叉樹中根結點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹還原：將孤立的二叉樹還原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ5.3.1二叉樹的順序存儲結構

(Sequentstorageofbinarytree)5.3.2二叉樹的鏈式存儲結構(Linkedstorageofbinarytree)5.3二叉樹存儲結構(Physicalstoragestructureofbinarytree)

二叉樹的順序存儲結構中結點的存放次序是：對該樹中每個結點進行編號,其編號從小到大的順序就是結點存放在連續(xù)存儲單元的先后次序。若把二叉樹存儲到一維數(shù)組中,則完全二叉樹上編號為i的結點元素存儲在一維數(shù)組中下標為i-1的分量中。

樹中各結點的編號與等高度的完全二叉樹中對應位置上結點的編號相同。

5.3.1二叉樹的順序存儲結構

(Sequentstorageofbinarytree)ABCDEFGHIJK123456789101112131415順序存儲結構

在二叉樹的鏈式存儲中,結點的結構如下:

typedefstructnode{ ElemTypedata; structnode*lchild,*rchild;}BTNode;

其中,data表示值域,用于存儲對應的數(shù)據(jù)元素,lchild和rchild分別表示左指針域和右指針域,用于分別存儲左孩子結點和右孩子結點(即左、右子樹的根結點)的存儲位置。5.3.2二叉樹的鏈式存儲結構(Linkedstorageofbinarytree)Binarytreeanditslinkedstorage5.4.1二叉樹遍歷的概念(Conceptofbinarytreetraversal)5.4.2二叉樹遍歷遞歸算法(Recursivealgorithmof

binarytreetraversal)5.4.3二叉樹遍歷非遞歸算法(Non-recursivealgorithmof

binarytreetraversal)

5.4二叉樹的遍歷(Binarytreetraversal)5.4.1ConceptofBinaryTreeTraversal

BinaryTreeTraversal:

按照一定次序訪問樹中所有結點,并且每個結點僅被訪問一次的過程。它是最基本的運算,是二叉樹中所有其他運算的基礎。二叉樹遍歷方法先序遍歷(preordertraversal)：先訪問根結點，然后分別先序遍歷左子樹、右子樹。中序遍歷(inordertraversal)：先中序遍歷左子樹，然后訪問根結點，最后中序遍歷右子樹。后序遍歷(postordertraversal)：先后序遍歷左、右子樹，然后訪問根結點。按層次遍歷(level-ordertravesal)：從上到下、從左到右訪問各結點。DLRLDR、LRD、DLRRDL、RLD、DRLThreeRecursiveAlgorithms：

voidPreOrder(BTNode*b) /*先序遍歷的遞歸算法*/{

if(b!=NULL){printf("%c",b->data);/*訪問根結點*/ PreOrder(b->lchild); PreOrder(b->rchild);}}先序遍歷序列：ABDGCEF5.4.2二叉樹遍歷遞歸算法(Recursivealgorithmof

binarytreetraversal)

voidInOrder(BTNode*b) /*中序遍歷的遞歸算法*/{

if(b!=NULL){InOrder(b->lchild); printf("%c",b->data);/*訪問根結點*/ InOrder(b->rchild); }}中序遍歷序列：DGBAECF

voidPostOrder(BTNode*b)/*后序遍歷遞歸算法*/{

if(b!=NULL){PostOrder(b->lchild); PostOrder(b->rchild); printf("%c",b->data);/*訪問根結點*/ }}后序遍歷序列：GDBEFCALevelOrderTraversal其過程是：

若二叉樹非空（假設其高度為h），則：（1）訪問根結點（第1層）；（2）從左到右訪問第2層的所有結點；（3）從左到右訪問第3層的所有結點、…、第h層的所有結點。層次遍歷序列：ABCDEFGvoidLevelOrder(BTNode*b){BTNode*p;BTNode*qu[MaxSize]; /*定義環(huán)形隊列,存放結點指針*/intfront,rear; /*定義隊頭和隊尾指針*/front=rear=-1; /*置隊列為空隊列*/rear++;qu[rear]=b; /*根結點指針進入隊列*/while(front!=rear) /*隊列不為空*/{front=(front+1)%MaxSize; p=qu[front]; /*隊頭出隊列*/ printf("%c",p->data); /*訪問結點*/

if(p->lchild!=NULL) /*有左孩子時將其進隊*/ {rear=(rear+1)%MaxSize; qu[rear]=p->lchild; } if(p->rchild!=NULL) /*有右孩子時將其進隊*/ {rear=(rear+1)%MaxSize; qu[rear]=p->rchild; }}}

Example5.2假設二叉樹采用二叉鏈存儲結構存儲,試設計一個算法,輸出一棵給定二叉樹的所有葉子結點。Solution：輸出一棵二叉樹的所有葉子結點的遞歸模型f()如下：f(b)：不做任何事件 若b=NULLf(b)：輸出*b結點的data域若*b為葉子結點f(b)：f(b->lchild);f(b->rchild) 其他情況

voidDispLeaf(BTNode*b){

if(b!=NULL){ if(b->lchild==NULL&&b->rchild==NULL) printf("%c",b->data); else {DispLeaf(b->lchild); DispLeaf(b->rchild);}}}先序遍歷非遞歸算法

先將根結點進棧，在棧不空時循環(huán)：出棧p，訪問*p結點，若右孩子不空將該右孩子結點進棧，若左孩子不空再將該左孩子結點進棧。5.4.3二叉樹遍歷非遞歸算法

(Non-recursivealgorithmof

binarytreetraversal)

voidPreOrder2(BTNode*b){ BTNode*St[MaxSize],*p;inttop=-1; top++;St[top]=b;//根結點入棧 while(top>-1) //棧不為空時循環(huán) {p=St[top];top--;//退棧并訪問該結點 printf("%c",p->data);if(p->rchild!=NULL)//右孩子結點入棧 {top++;St[top]=p->rchild;}if(p->lchild!=NULL)//左孩子結點入棧 {top++;St[top]=p->lchild;}}}2.中序遍歷非遞歸算法由中序遍歷過程可知，采用一個棧保存需要返回的結點指針，先掃描（并非訪問）根結點的所有左結點并將它們一一進棧。

然后出棧一個結點，顯然該結點沒有左孩子結點或者左孩子結點已訪問過（進一步說明該結點的左子樹均已訪問），則訪問它。然后掃描該結點的右孩子結點，將其進棧，再掃描該右孩子結點的所有左結點并一一進棧，如此這樣，直到?？諡橹埂oidInOrder2(BTNode*b){ BTNode*St[MaxSize],*p;inttop=-1; p=b; while(top>-1||p!=NULL) {while(p!=NULL)//掃描*p的所有左結點并進棧 {top++;St[top]=p; p=p->lchild; } if(top>-1) {p=St[top];top--; //出棧*p結點 printf("%c",p->data);//訪問之 p=p->rchild; //掃描*p的右孩子結點 }}//endofwhile(top>-1||p!=NULL)}找*b的最左下結點3.后序遍歷非遞歸算法

由后序遍歷過程可知，采用一個棧保存需要返回的結點指針，先掃描根結點的所有左結點并一一進棧，出棧一個結點*b即當前結點，然后掃描該結點的右孩子結點并入棧，再掃描該右孩子結點的所有左結點并入棧。當一個結點的左右孩子結點均訪問后再訪問該結點，如此這樣，直到?？諡橹?。難點：如何判斷一個結點*b的右孩子結點已訪問過，為此用p保存剛剛訪問過的結點（初值為NULL），若b->rchild==p成立（在后序遍歷中，*b的右孩子結點一定剛好在*b之前訪問），說明*b的左右子樹均已訪問，現(xiàn)在應訪問*b。voidPostOrder2(BTNode*b){ BTNode*St[MaxSize];BTNode*p; intflag,top=-1; //棧指針置初值 do {while(b!=NULL) //將*b的所有左結點進棧 { top++;St[top]=b; b=b->lchild; } p=NULL; //p指向棧頂結點的前一個已訪問的結點 flag=1; //設置b的訪問標記為已訪問過找最左下結點while(top!=-1&&flag==1){b=St[top];//取出當前的棧頂元素 if(b->rchild==p)

{printf("%c",b->data); //訪問*b結點 top--;p=b; //p指向則被訪問的結點 } else {b=b->rchild; //b指向右孩子結點 flag=0; //設置未被訪問的標記 }}//endofwhile(top!=-1&&flag==1)}while(top!=-1);}b的右孩子不存在或已訪問過從上述過程可知，棧中保存的是當前結點*b的所有祖先結點（均未訪問過）。

例如，書中例子求一個結點的所有祖先結點。5.5.1二叉樹的基本運算概述（Basicoperationsofbinarytree)5.5.2二叉樹的基本運算算法實現(xiàn)(Algorithmimplementationofbasicoperations)5.5二叉樹的基本運算及其實現(xiàn)(Algorithmimplementationandbasicoperationsofbinarytree)歸納起來,二叉樹有以下基本運算：(1)創(chuàng)建二叉樹CreateBTNode(*b,*str)：根據(jù)二叉樹括號表示法的字符串*str生成對應的鏈式存儲結構。(2)查找結點FindNode(*b,x)：在二叉樹b中尋找data域值為x的結點,并返回指向該結點的指針。(3)找孩子結點LchildNode(p)和RchildNode(p)：分別求二叉樹中結點*p的左孩子結點和右孩子結點。5.5.1二叉樹的基本運算概述（Basicoperationsofbinarytree)

(4)求高度BTNodeDepth(*b)：求二叉樹b的高度。若二叉樹為空,則其高度為0；否則,其高度等于左子樹與右子樹中的最大高度加l。(5)輸出二叉樹DispBTNode(*b)：以括號表示法輸出一棵二叉樹。(1)創(chuàng)建二叉樹CreateBTNode(*b,*str)

用ch掃描采用括號表示法表示二叉樹的字符串。分以下幾種情況：①若ch='('：則將前面剛創(chuàng)建的結點作為雙親結點進棧,并置k=1,表示其后創(chuàng)建的結點將作為這個結點的左孩子結點；②若ch=')'：表示棧中結點的左右孩子結點處理完畢,退棧；③若ch=','：表示其后創(chuàng)建的結點為右孩子結點；5.5.2二叉樹的基本運算算法實現(xiàn)(Algorithmimplementationofbasicoperations)

④其他情況,表示要創(chuàng)建一個結點,并根據(jù)k值建立它與棧中結點之間的聯(lián)系,當k=1時,表示這個結點作為棧中結點的左孩子結點,當k=2時,表示這個結點作為棧中結點的右孩子結點。如此循環(huán)直到str處理完畢。算法中使用一個棧St保存雙親結點,top為其棧指針,k指定其后處理的結點是雙親結點(保存在棧中)的左孩子結點(k=1)還是右孩子結點(k=2)。

voidCreateBTNode(BTNode*&b,char*str){BTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;b=NULL; /*建立的二叉樹初始時為空*/ch=str[j];while(ch!='\0') /*str未掃描完時循環(huán)*/{ switch(ch){ case'(':top++;St[top]=p;k=1;break; /*為左孩子結點*/ case')':top--;break; case',':k=2;break; /*為孩子結點右結點*/

default:p=(BTNode*)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(b==NULL)/**p為二叉樹的根結點*/ b=p; else/*已建立二叉樹根結點*/{switch(k){ case1:St[top]->lchild=p;break; case2:St[top]->rchild=p;break; }}} j++;ch=str[j];}}

例如,對于括號表示串A(B(D(,G)),C(E,F)),建立二叉樹鏈式存儲結構的過程如下表所示。ch算法執(zhí)行的操作St中元素A建立A結點,b指向該結點(A為樹的根）空(A結點進棧,k=1AB建立B結點,因k=1,將其作為A結點的左孩子結點A(B結點進棧,k=1ABD建立D結點,因k=1,將其作為B結點的左孩子結點ABch算法執(zhí)行的操作St中元素(D結點進棧,k=1ABD,k=2ABDG建立G結點,因k=2,將其作為D結點的右孩子結點ABD)退棧一次AB)退棧一次A,k=2AC建立C結點,因k=2,將其作為A結點的右孩子結點A(C結點進棧,k=1ACE建立E結點,因k=1,將其作為C結點的左孩子結點AC,k=2ACch算法執(zhí)行的操作St中元素F建立F結點,因k=2,將其作為C結點的右孩子結點AC)退棧一次A)退棧一次空ch掃描完畢算法結束

生成的二叉樹＝＞(2)查找結點FindNode(*b,x)

采用先序遍歷遞歸算法查找值為x的結點。找到后返回其指針,否則返回NULL。算法如下：

BTNode*FindNode(BTNode*b,ElemTypex){BTNode*p;if(b==NULL)returnNULL;elseif(b->data==x)returnb;else{p=FindNode(b->lchild,x); if(p!=NULL)returnp; elsereturnFindNode(b->rchild,x);}}(3)找孩子結點LchildNode(p)和RchildNode(p)

直接返回*p結點的左孩子結點或右孩子結點的指針。算法如下：

BTNode*LchildNode(BTNode*p){

returnp->lchild;}BTNode*RchildNode(BTNode*p){

returnp->rchild;}(4)求高度BTNodeDepth(*b)求二叉樹的高度的遞歸模型f()如下：f(NULL)=0f(b)=MAX{f(b->lchild),f(b->rchild)}+1其他情況對應的算法如下：intBTNodeDepth(BTNode*b){intlchilddep,rchilddep;if(b==NULL)return(0);/*空樹的高度為0*/else{lchilddep=BTNodeDepth(b->lchild); /*求左子樹的高度為lchilddep*/ rchilddep=BTNodeDepth(b->rchild); /*求右子樹的高度為rchilddep*/ return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);}}(5)輸出二叉樹DispBTNode(*b)其過程是：對于非空二叉樹b,先輸出其元素值,當存在左孩子結點或右孩子結點時,輸出一個“(”符號,然后遞歸處理左子樹,輸出一個“,”符號,遞歸處理右子樹,最后輸出一個“)”符號。

對應的遞歸算法如下：voidDispBTNode(BTNode*b){ if(b!=NULL) {printf("%c",b->data); if(b->lchild!=NULL||b->rchild!=NULL) { printf("("); DispBTNode(b->lchild); /*遞歸處理左子樹*/ if(b->rchild!=NULL)printf(","); DispBTNode(b->rchild); /*遞歸處理右子樹*/ printf(")"); } }}

Example5.5假設二叉樹采用二叉鏈存儲結構,設計一個算法輸出從每個葉子結點到根結點的路徑。解：這里用層次遍歷方法,設計的隊列為非循環(huán)順序隊列(類似于第3章3.2.4小節(jié)中求解迷宮問題時使用的隊列),將所有已掃描過的結點指針進隊,并在隊列中保存雙親結點的位置。當找到一個葉子結點時,在隊列中通過雙親結點的位置輸出該葉子結點到根結點的路徑。對應的算法如下：voidAllPath(BTNode*b){

structsnode{BTNode*node; /*存放當前結點指針*/ intparent; /*存放雙親結點在隊列中的位置*/}q[MaxSize]; /*定義順序隊列*/intfront,rear,p; /*定義隊頭和隊尾指針*/front=rear=-1; /*置隊列為空隊列*/rear++;q[rear].node=b;/*根結點指針進入隊列*/q[rear].parent=-1; /*根結點沒有雙親結點*/

while(front<rear) /*隊列不為空*/{front++;b=q[front].node; /*隊頭出隊列*/if(b->lchild==NULL&&b->rchild==NULL) {printf("%c到根結點路徑:",b->data); p=front; while(q[p].parent!=-1) {printf("%c->",q[p].node->data); p=q[p].parent;} printf("%c\n",q[p].node->data); } if(b->lchild!=NULL) /*左孩子結點入隊列*/ {rear++; q[rear].node=b->lchild; q[rear].parent=front;}if(b->rchild!=NULL) /*右孩子結點入隊列*/ {rear++;q[rear].node=b->rchild; q[rear].parent=front;}}/*endofwhile*/}同一棵二叉樹具有惟一先序序列、中序序列和后序序列,但不同的二叉樹可能具有相同的先序序列、中序序列和后序序列。例如,教材中P176

如圖7.11所示的5棵二叉樹,先序序列都為ABC。如圖7.12所示的5棵二叉樹,中序序列都為ACB。如圖7.13所示的5棵二叉樹,后序序列都為CBA。5.6二叉樹的構造(Constructionofbinarytree)

顯然,僅由一個先序序列(或中序序列、后序序列),無法確定這棵二叉樹的樹形。如果同時知道一棵二叉樹的先序序列和中序序列,或者同時知道中序序列和后序序列,就能確定這棵二叉樹。但是，同時知道先序序列和后序序列仍不能確定二叉樹的樹形。如圖7.11和7.13中除第一棵外的4棵二叉樹先序序列都是ABC，后序序列都是CBA。

Theorem5.1：任何n(n≥0)個不同結點的二又樹,都可由它的中序序列和先序序列惟一地確定。

采用數(shù)學歸納法證明。

當n=0時,二叉樹為空,結論正確。假設結點數(shù)小于n的任何二叉樹,都可以由其先序序列和中序序列惟一地確定。已知某棵二叉樹具有n(n＞0)個不同結點,其先序序列是a0a1…an-1；中序序列是b0b1…bk-1bkbk+1…bn-1。

因為在先序遍歷過程中,訪問根結點后,緊跟著遍歷左子樹,最后再遍歷右子樹。所以,a0必定是二叉樹的根結點,而且a0必然在中序序列中出現(xiàn)。也就是說,在中序序列中必有某個bk(0≤k≤n-1)就是根結點a0。

由于bk是根結點,而在中序遍歷過程中,先遍歷左子樹,再訪問根結點,最后再遍歷右子樹。所以在中序序列中,b0b1…bk-1必是根結點bk(也就是a0)左子樹的中序序列,即bk的左子樹有k個結點(注意,k=0表示結點bk沒有左子樹。)而bk+1…bn-1必是根結點bk(也就是a0)右子樹的中序序列,即bk的右子樹有n-k-1個結點(注意,k=n-1表示結點bk沒有右子樹。)。另外,在先序序列中,緊跟在根結點a0之后的k個結點a1…ak就是左子樹的先序序列,ak+1…an-1這n-k-1就是右子樹的先序序列。根據(jù)歸納假設,由于子先序序列a1…ak和子中序序列b0b1…bk-1可以惟一地確定根結點a0的左子樹,而子先序序列ak+1…an-1和子中序序列bk+1…bn-1可以惟一地確定根結點a0的右子樹。綜上所述,這棵二叉樹的根結點己經(jīng)確定,而且其左、右子樹都惟一地確定了,所以整個二叉樹也就惟一地確定了。

Forexample,已知先序序列為ABDGCEF,中序序列為DGBAECF,則構造二叉樹的過程如下所示。

根結點：A左先序:BDG左中序:DGB右先序:CEF右中序:ECF根結點：B左先序:DG左中序:DG右先序:空右中序:空根結點：D左先序:空左中序:空右先序:G右中序:G根結點：G左先序:空左中序:空右先序:空右中序:空根結點：C左先序:E左中序:E右先序:F右中序:F根結點：E左先序:空左中序:空右先序:空右中序:空根結點：F左先序:空左中序:空右先序:空右中序:空由上述定理得到以下構造二叉樹的算法：BTNode*CreateBT1(char*pre,char*in,intn){BTNode*s;char*p;intk;if(n<=0)returnNULL;s=(BTNode*)malloc(sizeof(BTNode));/*創(chuàng)建結點*s*/s->data=*pre;for(p=in;p<in+n;p++)/*在中序中找為*ppos的位置k*/ if(*p==*pre) break;k=p-in;s->lchild=CreateBT1(pre+1,in,k); /*遞歸構造左子樹*/s->rchild=CreateBT1(pre+k+1,p+1,n-k-1);/*構造右子樹*/returns;}

Theorem5.2：任何n(n＞0)個不同結點的二又樹,都可由它的中序序列和后序序列惟一地確定。

同樣采用數(shù)學歸納法證明。

實際上,對于根結點ak的左右子樹,在確定左右子樹的子中序序列后,不需要確定左右子樹的整個子后序序列,只需確定子中序序列中全部字符在后序序列中最右邊的那個字符即可,因為這個字符就是子樹的根結點。

Forexample,已知中序序列為DGBAECF,后序序列為GDBEFCA。對應的構造二叉樹的過程如下所示。根結點：A左中序:DGB左根:B右中序:ECF右根:C根結點：B左中序:DG左根:D右中序:空右根:空根結點：D左中序:空左根:空右中序:G右根:G根結點：G左中序:空左根:空右中序:空右根:空根結點：C左中序:E左根:E右中序:F右根:F根結點：E左中序:空左根:空右中序:空右根:空根結點：F左中序:空左根:空右中序:空右根:空由上述定理得到以下構造二叉樹的算法：BTNode*CreateBT2(char*post,char*in,intn){BTNode*s;charr，*p；intk;if(n<=0)returnNULL;r=*(post+n-1);//根結點s=(BTNode*)malloc(sizeof(BTNode));s->data=r;for(p=in;p<in+n;p++)if(*p==r)break;k=p-in;s->lchild=CreateBT2(post,in,k);s->rchild=CreateBT2(post+k,p+1,n-k-1);returns;}5.7.1線索二叉樹的概念(concept)

對于具有n個結點的二叉樹,采用二叉鏈存儲結構時,每個結點有兩個指針域,總共有2n個指針域,又由于只有n-1個結點被有效指針所指向(n個結點中只有樹根結點沒有被有效指針域所指向),則共有2n-(n-1)=n+1個空鏈域,

我們知道,遍歷二叉樹的結果是一個結點的線性序列。可以利用這些空鏈域存放指向結點的前驅和后繼結點的指針。這樣的指向該線性序列中的“前驅”和“后繼”的指針,稱作線索。5.7線索二叉樹(Threadedbinarytree)在結點的存儲結構上增加兩個標志位來區(qū)分這兩種情況：左標志ltag:0表示lchild指向左孩子結點1表示lchild指向前驅結點右標志rtag:0表示rchild指向右孩子結點1表示rchild指向后繼結點這樣,每個結點的存儲結構如下：ltaglchilddatarchildrtag按上述原則在二叉樹的每個結點上加上線索的二叉樹稱作線索二叉樹。

對二叉樹以某種方式遍歷使其變?yōu)榫€索二叉樹的過程稱作按該方式對二叉樹進行線索化。

為使算法設計方便,在線索二叉樹中再增加一個頭結點。頭結點的data域為空；lchild指向無線索時的根結點,ltag為0；rchild指向按某種方式遍歷二叉樹時的最后一個結點,rtag為1。

(a)是中序線索二叉樹(中序序列為：DGBAECF).(b)是先序線索二叉樹(先序序列為：ABDGCEF).(c)是后序線索二叉樹(后序序列為：GDBEFCA)。圖中實線表示二叉樹原來指針所指的結點,虛線表示線索二叉樹所添加的線索。5.7.2線索化二叉樹(Threadingbinarytree)建立線索二叉樹,或者說,對二叉樹線索化,實質上就是遍歷一棵二叉樹,在遍歷的過程中,檢查當前結點的左、右指針域是否為空。如果為空,將它們改為指向前驅結點或后繼結點的線索。另外,在對一棵二叉樹添加線索時,我們創(chuàng)建一個頭結點,并建立頭結點與二叉樹的根結點的線索。對二叉樹線索化后,還須建立最后一個結點與頭結點之間的線索。下面以中序線索二叉樹為例,討論建立線索二叉樹的算法。

為了實現(xiàn)線索化二叉樹,將前面二叉樹結點的類型定義修改如下：typedefstructnode{ElemTypedata; /*結點數(shù)據(jù)域*/intltag,rtag; /*增加的線索標記*/structnode*lchild; /*左孩子或線索指針*/structnode*rchild; /*右孩子或線索指針*/}TBTNode; /*線索樹結點類型定義*/下面是建立中序線索二叉樹的算法。

CreaThread(b)算法是將以二叉鏈存儲的二叉樹b進行中序線索化,并返回線索化后頭結點的指針root。Thread(p)算法用于對于以*p為根結點的二叉樹中序線索化。在整個算法中p總是指向當前被線索化的結點,而pre作為全局變量,指向剛剛訪問過的結點,*pre是*p的前驅結點,*p是*pre的后繼結點。

CreaThread(b)算法思路是：

先創(chuàng)建頭結點*root,其lchild域為鏈指針,rchild域為線索。將rchild指針指向*b,如果b二叉樹為空,則將其lchild指向自身。否則將*root的lchild指向*b結點,p指向*b結點,pre指向*root結點。再調用Thread(b)對整個二叉樹線索化。最后加入指向頭結點的線索,并將頭結點的rchild指針域線索化為指向最后一個結點(由于線索化直到p等于NULL為止,所以最后一個結點為*pre)。TBTNode*CreaThread(TBTNode*b)/*中序線索化二叉樹*/{TBTNode*root;root=(TBTNode*)malloc(sizeof(TBTNode));/*創(chuàng)建頭結點*/root->ltag=0;root->rtag=1;root->rchild=b;if(b==NULL)root->lchild=root; /*空二叉樹*/else{root->lchild=b; pre=root; /*pre是*p的前驅結點,供加線索用*/ Thread(b); /*中序遍歷線索化二叉樹*/ pre->rchild=root; /*最后處理,加入指向頭結點的線索*/ pre->rtag=1; root->rchild=pre; /*頭結點右線索化*/}returnroot;}Thread(p)算法思路是：類似于中序遍歷的遞歸算法,在p指針不為NULL時,先對*p結點的左子樹線索化；若*p結點沒有左孩子結點,則將其lchild指針線索化為指向其前驅結點*pre,否則表示lchild指向其左孩子結點,將其ltag置為0；若*pre結點的rchild指針為NULL,將其rchild指針線索化為指向其后繼結點*p,否則rchild表示指向其右孩子結點,將其rtag置為0,再將pre指向*p；最后對*p結點的右子樹線索化。TBTNode*pre; /*全局變量*/voidThread(TBTNode*&p)/*對二叉樹b進行中序線索化*/{if(p!=NULL) {Thread(p->lchild); /*左子樹線索化*/ if(p->lchild==NULL)/*前驅線索*/ {p->lchild=pre;p->ltag=1;}/*建立當前結點的前驅線索*/ elsep->ltag=0; if(pre->rchild==NULL) /*后繼線索*/ {pre->rchild=p;pre->rtag=1;}/*建立前驅結點的后繼線索*/ elsepre->rtag=0;pre=p; Thread(p->rchild); /*遞歸調用右子樹線索化*/}}中序遍歷(遞歸)遍歷某種次序的線索二叉樹,就是從該次序下的開始結點出發(fā),反復找到該結點在該次序下的后繼結點,直到終端結點。

先序線索二叉樹和后序線索二叉樹較少用到。

在中序線索二叉樹中,開始結點就是根結點的最左下結點,而求當前結點在中序序列下的后繼和前驅結點的方法如教材中表7.6所示,最后一個結點的rchild指針被線索化為指向頭結點。利用這些條件,在中序線索化二叉樹中實現(xiàn)中序遍歷的算法如下：5.7.3遍歷線索化二叉樹(Traversingthreadedbinarytree)voidThInOrder(TBTNode*tb){TBTNode*p=tb->lchild; /*p指向根結點*/while(p!=tb){while(p->ltag==0)p=p->lchild; /*找開始結點*/ printf("%c",p->data); /*訪問開始結點*/ while(p->rtag==1&&p->rchild!=tb) {p=p->rchild;//后繼結點 printf("%c",p->data); } p=p->rchild; }}5.8哈夫曼樹(Huffmantree)

5.8.1哈夫曼樹的定義(DefinitionofHuffmantree)5.8.2構造哈夫曼樹(ConstructingHuffmantree)5.8.3哈夫曼編碼(Huffmancoding)

設二叉樹具有n個帶權值的葉子結點,那么從根結點到各個葉子結點的路徑長度與相應結點權值的乘積的和,叫做二叉樹的帶權路徑長度。

其中,n表示葉子結點的數(shù)目,wi和li分別表示葉子結點ki的權值和根到ki之間的路徑長度(即從葉子結點到達根結點的分支數(shù))。具有最小帶權路徑長度的二叉樹稱為哈夫曼樹。

5.8.1哈夫曼樹的定義(DefinitionofHuffmantree)例有4個結點，權值分別為7，5，2，4，構造有4個葉子結點的二叉樹abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35

根據(jù)哈夫曼樹的定義,一棵二叉樹要使其WPL值最小,必須使權值越大的葉子結點越靠近根結點,而權值越小的葉子結點越遠離根結點。那么如何構造一棵哈夫曼樹呢?其方法如下:(1)由給定的n個權值{W1,W2,...,Wn},

構造n棵只有一個葉子結點的二叉樹,從而得到一個二叉樹的集合F={T1,T2,...,Tn};5.8.2構造哈夫曼樹(ConstructingHuffmantree)

(2)在F中選取根結點的權值最小和次小的兩棵二叉樹作為左、右子樹構造一棵新的二叉樹,這棵新的二叉樹根結點的權值為其左、右子樹根結點權值之和;(3)在集合F中刪除作為左、右子樹的兩棵二叉樹,并將新建立的二叉樹加入到集合F中;(4)重復(2)、(3)兩步,當F中只剩下一棵二叉樹時,這棵二叉樹便是所要建立的哈夫曼樹。例2w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100

為了實現(xiàn)構造哈夫曼樹的算法,設計哈夫曼樹中每個結點類型如下：typedefstruct{ chardata; /*結點值*/ floatweight; /*權重*/ intparent; /*雙親結點*/ intlchild; /*左孩子結點*/ intrchild; /*右孩子結點*/}HTNode;

用ht[]數(shù)組存放哈夫曼樹,對于具有n個葉子結點的哈夫曼樹,總共有2n-1個結點（定理7.3）。其算法思路是：n個葉子結點只有data和weight域值,先將所有2n-1個結點的parent、lchild和rchild