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

了解樹型結(jié)構(gòu)結(jié)點之間的層次關(guān)系；掌握樹和二叉樹的定義及其相關(guān)的術(shù)語；重點掌握二叉樹的結(jié)構(gòu)、性質(zhì)，存儲表示和四種遍歷算法；掌握二叉樹線索化的實質(zhì)及線索化的過程；了解樹的結(jié)構(gòu)性質(zhì)、存儲表示方法和遍歷算法；掌握森林(樹)與二叉樹的對應(yīng)關(guān)系和相互轉(zhuǎn)換方法。要求線性表：元素之間的線性關(guān)系樹：元素之間的層次關(guān)系主要內(nèi)容3.1基本術(shù)語3.2二叉樹3.3堆3.4選擇樹實驗2二叉樹的建立及基本操作3.5樹3.6森林與二叉樹間的轉(zhuǎn)換3.7樹的應(yīng)用3.1基本術(shù)語【定義一】（1）一個結(jié)點x組成的集{x}是一棵樹(Tree)，這個結(jié)點x也是這棵樹的根；（2）假設(shè)x是一個結(jié)點，D1，D2，…，Dk是k棵互不相交的樹，我們可以構(gòu)造一棵新樹：令x為根，并有k條邊由x指向樹D1，D2，…，Dk。這些邊也叫做分支，D1，D2，…，Dk稱作根x的樹之子樹（SubTree）?！径x二】樹是n(≥0)個結(jié)點的有限集。在任意一棵非空樹中：（1）有且僅有特定的稱為根（Root）的結(jié)點；（2）當n＞1時，其余結(jié)點可分為k（＞0）個互不相交的有限集D1，D2，…，Dk，其中每一個集合本身又是一棵樹，并且稱為根的子樹（SubTree

）。1、樹的定義T=（D，R）D：具有相同類型的數(shù)據(jù)元素的集合。R：若D為空集，則稱為空樹；若D僅含一個數(shù)據(jù)元素，則R為空集，否則R={H}，H是如下的二元關(guān)系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下

無前驅(qū)；（2）若D-{root}≠￠，則存在D-{root}的一個劃分D1，D2，…，

Dk（k＞0），對任意j≠l（1≤j，l

≤k）有Dj∩Dl=￠，對任意

的i（1≤i≤k），唯一存在數(shù)據(jù)元素xi∈Di，有<root,xi>∈H;（3）對應(yīng)于D-{root}的劃分，H-{<root,x1>,…,<root,xk>}有唯一的一個劃分H1，H2，…，Hk

（k＞0）,對任意j≠l（1≤j，l≤k）有Hj∩Hl≠￠,且對任意的i

（1≤i≤k），Hi是Di上的二元關(guān)系，（Di，{Hi}）是一棵符合本定義的樹，稱為根root的子樹?！径x三】三個定義的共同點：1、相同類型的元素構(gòu)成的集合；2、特定的結(jié)點---根；3、除了根之外，組成k個劃分，且互不相交；4、每一個劃分又是一棵樹---遞歸；幾點說明：遞歸定義，但不會產(chǎn)生循環(huán)定義；構(gòu)造性定義便于樹型結(jié)構(gòu)的建立；一株樹的每個結(jié)點都是這株樹的某株子樹的根。ABCDEFGHIJKLM圖一第1層第2層第3層第4層第5層ABCDEFGHIJKLM圖二樹高為52、常用術(shù)語結(jié)點度葉（終端結(jié)點）非終端結(jié)點分支路長父親雙親兒子兄弟子孫祖先層結(jié)點的高樹的高（深度）有序樹

&無序樹ABCACB≠森林forest：是n≥0棵互不相交的樹的集合。3.2二叉樹(BinaryTree)1、二叉樹的定義【定義一】二叉樹是有限個結(jié)點的集合，這個集合或者是空集，或者是由一個根結(jié)點和兩棵互不相交的二叉樹組成，其中一棵叫根的做左子樹，另一棵叫做根的右子樹。3.2.1二叉樹的定義和基本性質(zhì)【定義二】BinaryTree=(D,R)D：指數(shù)據(jù)對象，是由相同類型的數(shù)據(jù)元素組成的集合。R：為數(shù)據(jù)元素間的關(guān)系：若D＝￠,則R=￠

，稱Binarytree為空樹；若D≠￠,則R={H}，H是如下二元關(guān)系：⑴在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；⑵若D-{root}≠￠，則存在D-{root}={Dl，Dr}，且Dl∩Dr=￠；⑶若Dl

≠￠，則Dl中存在唯一的元素xl，<root,xl

>∈H，且存在Dl上的關(guān)系Hl∈H；若Dr≠￠，則Dr中存在唯一的元素

xr，<root,xr>∈H，且存在Dr上的關(guān)系Hr∈H；

H={<root,xl>，<root,xr>，Hl，Hr}；⑷（Dl，{Hl}）是符合本定義的二叉樹，稱為根的左子樹；（Dr，{Hr}）是符合本定義的二叉樹，稱為根的右子樹。與樹的定義對比：1、相同類型的元素構(gòu)成的集合；2、特定的結(jié)點---根；3、除了根之外，組成k個劃分，且互不相交；4、每一個劃分又是一棵二叉樹---遞歸。k<=2分左、右二叉樹是有序的ABCDEFGHIJKLMABCDEFGHIJKLM分析圖（1）和圖（2）的區(qū)別：問題：具有三個結(jié)點的樹和二叉樹各有多少棵？2、二叉樹的性質(zhì)性質(zhì)1：在二叉樹中第i層的結(jié)點數(shù)最多為2i-1（i≥1）。性質(zhì)2：高度為k的二叉樹其結(jié)點總數(shù)最多為2k－1（k≥1）。性質(zhì)3：對任意的非空二叉樹T，如果葉結(jié)點的個數(shù)為n0，而其度為2的結(jié)點數(shù)為n2，則：

n0=n2+1?！径x】深度為k且有2k－1個結(jié)點的二叉樹稱為滿二叉樹。層序編號：對滿二叉樹的結(jié)點進行連續(xù)編號。從根結(jié)點開始，從上而下，自左至右?！径x】深度為k的，有n個結(jié)點的二叉樹，當且僅當其每個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)，稱之為完全二叉樹。二叉樹的性質(zhì)(續(xù))：性質(zhì)4

具有n個結(jié)點的完全二叉樹的深度為└

log2n┘+1。性質(zhì)5

如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序

編號，則對任一結(jié)點i有：⑴如果i=1，則結(jié)點i是二叉樹的根，無雙親；如果

i＞1，則其雙親結(jié)點是i/2；⑵如果2i＞

n，則結(jié)點i無左孩子結(jié)點，否則其左孩

子結(jié)點是2i；⑶如果2i+1＞

n，則結(jié)點i無右孩子結(jié)點，否則其右孩子結(jié)點是2i+1。3、二叉樹的遍歷DLR【遍歷】根據(jù)原則，按照一定的順序訪問二叉樹中的每一個結(jié)點，使每個結(jié)點只能被訪問一次。

根（D）、左孩子（L）和右孩子（R）三個結(jié)點可能出現(xiàn)的順序有：①DLR②DRL③LDR④LRD⑤RLD⑥RDL【原則】左孩子結(jié)點一定要在右孩子結(jié)點之前被訪問。要討論的三種操作分別為：①先根順序DLR，②中根順序LDR，③后根順序LRD①先根順序遍歷二叉樹：若二叉樹非空則：

{訪問根結(jié)點；先根順序遍歷左子樹；先根順序遍歷右子樹；

}；②中根順序遍歷二叉樹：若二叉樹非空則：

{中根順序遍歷左子樹；

訪問根結(jié)點；中根順序遍歷右子樹；

}；③后根順序遍歷二叉樹：若二叉樹非空則：

{后根順序遍歷左子樹；后根順序遍歷右子樹；

訪問根結(jié)點；

}；3.2.2抽象數(shù)據(jù)型二叉樹ADT操作：①Empty(BT);②IsEmpty(BT);③CreateBT(V,LT,RT);④Lchild(BT);⑤Rchild(BT);⑥D(zhuǎn)ata(BT);【例3-1】寫一個遞歸函數(shù)，按先根順序列出二叉樹中每個結(jié)點的Data域之值。VoidPreOrder(BT)BTREEBT;{if(!IsEmpty(BT)){visit(Data(BT));PreOrder(Lchild(BT));PreOrder(Rchild(BT));}}【例3-2】寫一個遞歸函數(shù)，按中根順序列出二叉樹中每個結(jié)點的Data域之值。VoidInOrder(BT)BTREEBT;{if(!IsEmpty(BT)){InOrder(Lchild(BT));

visit(Data(BT));InOrder(Rchild(BT));}}【例3-3】寫一個遞歸函數(shù)，按后根順序列出二叉樹中每個結(jié)點的Data域之值。VoidPostOrder(BT)BTREEBT;{if(!IsEmpty(BT)){PostOrder(Lchild(BT));PostOrder(Rchild(BT));

visit(Data(BT));}}ABCDEFGHIJKLM例*二叉樹的遍歷的非遞歸過程先序：ABDJHECFIGKLM中序：JDHBEAFICGLKM后序：JHDEBIFLMKGCAVoidInOrder(BT)BTREEBT;{if(!IsEmpty(BT)){InOrder(Lchild(BT));

visit(Data(BT));InOrder(Rchild(BT));}}No.指針BT棧輸出1A→#2B→#A3D→#AB4J→#ABD5^#ABDJ→J6^#ABD→D7H→#AB8^#ABH→H9^#AB→B10E→#A11^#AE→E12^#A→A13C→#14F→#C15^#CF→F16I→#C17^#CI→I18^#C→C19G→#20^#G→G21K→#22L→#K23^#KL→L24^#K→K25M→#26^#M→M27^#結(jié)束算法:Loop:{if(BT非空){進棧;

左一步;}else{退棧；

輸出;

右一步;}};數(shù)據(jù)結(jié)構(gòu):

設(shè)棧S:

用以保留當前結(jié)點;二叉樹的遍歷的非遞歸過程VoidNInOrder(BT)BTREEBT;{STACKS;BTREET;MakeNull(S);T=BT;while(!IsEmpty(T)||Empty(S))if(!IsEmpty(T)){Push(T,S);T=Lchild(T);}else{T=TOP(S);POP(S);visit(Data(T));T=Rchild(T);}}進棧;左走一步退棧;右走一步先序遍歷非遞歸算法Loop:{if(BT非空){輸出;

進棧;

左一步;}else{退棧；

輸出;

右一步;}};中序遍歷非遞歸算法Loop:{if(BT非空){進棧;

左一步;}else{退棧;

輸出;

右一步;}};后序遍歷非遞歸算法Loop:{if(BT非空){進棧;

左一步;}else{當棧頂指針所指結(jié)點的右子樹不存在或已訪問,

退棧并訪問;

否則右一步;}};中序遍歷非遞歸算法：voidInOrder(BTREE*root{BTREE*stack[MAX];inttop=0;do{ while(root!=Null) {top++;if(top>MAX) printf("棧滿!\n");else stack[top]=root;root=Lchild(root);}if(top!=0){root=stack[top];top--;printf("%c",Data(root));root=Rchild(root); }}while((top!=0)||(root!=Null));}Loop:{if(BT非空){輸出;

進棧;

左一步;}else{退棧;

右一步;}};先序遍歷非遞歸算法：voidPreOrder(BTREE*root{BTREE*stack[MAX];inttop=0;do{while(root!=Null) { printf("%c",Data(root));top++;if(top>MAX) printf("棧滿!\n");elsestack[top]=root;root=Lchild(root); }if(top!=0) { root=stack[top];top--;root=Rchild(root); }}while((top!=0)||(root!=Null));}Loop:{if(BT非空){進棧;

左一步;}else{退棧;

輸出;

右一步;}};后序遍歷非遞歸算法：voidPostOrder(BTREE*root)//后序遍歷，非遞歸{BTREE*stack[MAX],*p;inttop=0,b;do{while(root!=Null){top++;if(top>MAX) printf("棧滿!\n");else stack[top]=root;root=Lchild(root); }p=Null; b=1;while((top!=0)&&b)//右子樹不存在或已訪問

{root=stack[top];if(root->rchild==p){printf("%c",Data(root));//訪問根結(jié)點

top--; p=root; }//p指向剛訪問

else {root=Rchild(root);

b=0; }}}while(top!=0);}Loop:{if(BT非空){進棧;

左一步;}else{當棧頂指針所指結(jié)點的右子樹不存在或已訪問,

退棧并訪問;

否則右一步;}};3.2.3二叉樹的表示1、順序存儲（1）完全（或滿）二叉樹根據(jù)性質(zhì)5，如已知某結(jié)點的層序編號i,則可求得該結(jié)點的雙親結(jié)點、左孩子結(jié)點和右孩子結(jié)點。ABCDEFGIHJABCDEFG12345678910HIJ采用一維數(shù)組，按層序順序依次存儲二叉樹的每一個結(jié)點。如下圖所示：（2）一般二叉樹ABC*E*G12345678910**J根據(jù)性質(zhì)5，如已知某結(jié)點的層序編號i,則可求得該結(jié)點的雙親結(jié)點、左孩子結(jié)點和右孩子結(jié)點，然后檢測其值是否為虛設(shè)的特殊結(jié)點*。通過虛設(shè)部分結(jié)點，使其變成相應(yīng)的完全二叉樹。ABC*E*G**JABCEGJ

A

B

C

D

E^^F^^G^^H^^I^^J^StructNode{StructNode*lchild;StructNode*rchild;datatypedata;};TypedefstructNode*BTREE;2、二叉樹的左右鏈表示ABCDEFGIJH例:(P102)BTREECreateBT(v,ltree,rtree)datatypev;BTREEltree,rtree;{BTREEroot;root=NewNode;

root->data=v;root->lchild=ltree;root->rchild=rtree;returnroot;}lchilddatarchild證明：n個結(jié)點的二叉樹中，共有n+1個空鏈接域。證：設(shè)其空鏈域數(shù)為x

分支數(shù)B入

=n–1B出=2×n–x∵B入

=B出∴n–1=2×n–x

得出x=n+1ABCDEFGHIJKLM結(jié)點總數(shù)：13空鏈域的個數(shù)：14【例3-4】二叉樹建立方法之一按先序序列建立二叉樹的左右鏈結(jié)構(gòu)。如下圖所示二叉樹,輸入:ABDH##I##E##CF#J##G##其中:#表示空ABCDEFGIJHBTREE*Setup2(){BTREE*bt;charch;

fflush(stdin);scanf("%c",&ch);if(ch=='#') bt=Null;else{ bt=NewBNODE; if(!bt)exit(0); bt->data=ch; bt->lchild=Setup2(); bt->rchild=Setup2();}return(bt);}【例3-5】二叉樹的遍歷（二叉鏈表結(jié)構(gòu)）VoidPreOrder(

BTREE

T){if(T){visit(T->data);PreOrder(T->lchild);PreOrder(T->rchild);}}VoidInOrder(

BTREE

T){if(T){InOrder(T->lchild);visit(T->data);InOrder(T->rchild);}}VoidPostOrder(

BTREE

T){if(T){PostOrder(T->lchild);PostOrder(T->rchild);visit(T->data);}}【例3-6】按層序遍歷二叉樹（二叉鏈表結(jié)構(gòu)）

從二叉樹的第一層開始，直到最后一層，每層從左到右訪問每一個結(jié)點，是的每個結(jié)點只能被訪問一次。ABCDEFGIJH右圖所示二叉樹按層序遍歷結(jié)果為：ABCDEFGHIJ設(shè)立一個隊列，隊列元素為結(jié)點的指針；首先將根結(jié)點指針排隊；當隊列非空時，從隊首刪除一個結(jié)點，如果該結(jié)點的左子樹非空，則其左子樹結(jié)點指針指針排隊；如果該結(jié)點的右子樹非空，則其右子樹結(jié)點指針指針排隊；重復(fù)上述過程，直到隊列為空。A^B^C^D^E^F^G^H^I^J^QfrontrearStructnode{Structnode*lchild;Structnode*rchild;datatypedata;};Typedefstructnode*BTREE;VoidLeverList(BTREET){QUEUEQ；BTREEp=T;MakeNull(Q)；if(T){EnQueue(p,Q);while(!Empty(Q)){p=DeQueue(Q);visit(P-data);if(p->lchild)EnQueue(p->lchild);if(p->rchild)EnQueue(p->rchild);}}StructQUEUE{Structnode*data[maxlength];intfront；

intrear；}；【例3-7】一棵二叉樹的先序、中序和后序序列分別如下，其中一部分未顯示出來，試求出空格處的內(nèi)容，并畫出該二叉樹。先序：_B_F_ICEH_G；

中序：D_KFIA_EJC_；

后序：_K_FBHJ_G_A；

先序：ABDFKICEHJG

中序：DBKFIAHEJCG

后序：DKIFBHJEGCAABCDEFGHIJK【例3-8】二叉樹中序序列為：ABCEFGHD，

后序序列為：ABFHGEDC。請畫出此二叉樹。ABCDEFGH已知：①已知先序和中序？②已知中序和后序？③已知先序和后序？能否唯一還原二叉樹？【例3-10】完全二叉樹的某結(jié)點若無左孩子結(jié)點，則它必是葉結(jié)點，為什么？先序遍歷和中序遍歷相同的二叉樹？先序遍歷和后序遍歷相同的二叉樹？中序遍歷和后序遍歷相同的二叉樹？【例3-9】試舉出：【例3-11】設(shè)高為h的二叉樹只有度為0和度為2的結(jié)點，則此類二叉樹的結(jié)點樹至少為

，至多為

。

2h-12h-1【例3-12】一棵有124個葉子結(jié)點（n0）的完全二叉樹，

最多有

？

個結(jié)點（n）?n0=n2+1n=n0+n1+n2n=n1+2n0-1但在完全二叉樹中，n1不是0就是1只有n1=1時，n取最大值為2n0【例3-13】證明任一棵滿二叉樹T中的分支數(shù)B滿足:

B=2(n0-1)

，其中n0為葉子結(jié)點數(shù)。證明：滿二叉樹中不存在度為1的節(jié)點，設(shè)度為2的結(jié)點數(shù)為n2則：n=n0+n2又：n=B+1所以有：B=n0+n2-1,而n0=n2+1,n2=n0-1

B=n0+n0-1-1=2(n0-1)【例3-14】具有n

個結(jié)點的滿二叉樹，其葉子結(jié)點的個數(shù)

為多少？【例3-15】n個結(jié)點的完全二叉樹，其葉子結(jié)點的個數(shù)為多少？方法一：設(shè)滿二叉樹的高度為ｈ；則根據(jù)二叉樹的性質(zhì)，葉子結(jié)點數(shù)為2h-1；

二叉樹總結(jié)點數(shù)n=2h-1；

可導出:２h-1=(n+1)/2；方法二：結(jié)點總數(shù)：n=n0+n1+n2；

但對滿二叉樹，除有n0=n2+1外，還有n1=0；

故有：n=n0+n0-1

n0=(n+1)/2BTREE*Setup3(BTREE*bt,intn)//交互問答方式創(chuàng)建二叉樹{charch;if(n==0)printf("根結(jié)點:");fflush(stdin);scanf("%ch",&ch);fflush(stdin);if(ch!='#'){n=1;bt=NewBNODE;bt->data=ch;bt->lchild=Null;bt->rchild=Null;printf("%c的左孩子是:",bt->data);bt->lchild=Setup3(bt->lchild,n);printf("%c的右孩子是:",bt->data);bt->rchild=Setup3(bt->rchild,n);}return(bt);}【例3-16】二叉樹建立方法之二【例3-17】求任意二叉樹的寬度。intWidth(BTREE*T){//求二叉樹的寬度inti,n=0,front=0,rear=0,max=0,lev=1,

maxlev[10]={0};structW{BTREE*Node;intNodelev;}Q[50];Q[front].Node=T;Q[front].Nodelev=1;while(front<=rear){if(Q[front].Node->lchild){Q[++rear].Node=Q[front].Node->lchild;Q[rear].Nodelev=Q[front].Nodelev+1;}if(Q[front].Node->rchild){Q[++rear].Node=Q[front].Node->rchild;Q[rear].Nodelev=Q[front].Nodelev+1;}front++;}for(i=0;i<=rear;i++)maxlev[Q[i].Nodelev]++;for(i=0;i<10;i++)

if(max<maxlev[i])max=maxlev[i];return(max);}intDepth(BTREE*bt)//求二叉樹的深度{intldepth,rdepth;if(bt==Null) return(0);else{ ldepth=Depth(bt->lchild); rdepth=Depth(bt->rchild); if(ldepth>rdepth) return(ldepth+1); else return(rdepth+1);}}【例3-18】求任意二叉樹的深度。討論：如果讓你設(shè)計一棵三叉樹，你會怎么做？ABCDEHFGT2ABCDEHFGT1IJKADHFGBECT3typedefstructBiTPNode{ElementTypedata;structBiTPNode*parent,*lchild,*rchild;}*BiPTree;二叉樹的三叉鏈表存儲表示parentlchilddatarchildBiTPNoden個結(jié)點的二叉樹有n+2個空指針！很顯然：相對二叉鏈表表示的二叉樹，除了找父結(jié)點的操作變得很容易外，其它基本操作沒有什么變化。問題：

對二叉樹的先序/中序/后序的非遞歸遍歷，不需要再使用棧。voidInOrder(TriTreePT,void(*visit)(TElemType)){TriTreep=PT,pr;while(p){if(p->lchild)p=p->lchild;//找最左結(jié)點else{visit(p->data);//訪問最左節(jié)點if(p->rchild)p=p->rchild;//若有右子樹，找右子樹最左結(jié)點

else{pr=p;//否則返回其父親p=p->parent;while(p&&(p->lchild!=pr||!p->rchild)){if(p->lchild==pr)visit(p->data);pr=p;//父親已被訪問，故返回上一級p=p->parent;}if(p){visit(p->data);p=p->rchild;}}}}}//若其不是從左子樹回溯來的，或左結(jié)點的父親并沒有右孩子

//該while循環(huán)沿雙親鏈一直查找，若無右孩子則訪問，直至找到第一個有右孩子的結(jié)點為止（但不訪問該結(jié)點，留給下步if語句訪問）//訪問父親，并轉(zhuǎn)到右孩子（經(jīng)上步while處理，可以確定此時p有右孩子）不用棧非遞歸遍歷思考題：（1）如何判斷一顆任意二叉樹是否為滿二叉樹？（2）如何判斷一顆任意二叉樹是否為完全二叉樹？（3）求二叉樹任意結(jié)點所在的層？（4）求任意結(jié)點的所有祖先結(jié)點（根到該結(jié)點的路徑）（5）統(tǒng)計任意二叉樹中的結(jié)點個數(shù)？總結(jié)點、度為2、度為1、度為0的結(jié)點個數(shù)。6、將二叉鏈表存儲的二叉樹轉(zhuǎn)換到按照完全二叉樹存儲的數(shù)組中?！?’表示空結(jié)點。BDEHGCCBD--EG-------H3.2.4線索二叉樹問題的提出：（1）在n個結(jié)點的二叉樹左右鏈表示中，有n+1個空鏈域。如何利用n+1個空鏈域，使二叉樹的操作更加方便；（2）在二叉樹左右鏈表示中，為求某個結(jié)點的（中序）前驅(qū)$P或（中序）后繼p$，每次都要從樹根開始進行查找，很不方便?！径x】若結(jié)點p有左孩子，則p->lchild指向其左孩子結(jié)點，否則令其指向其（中序）前驅(qū)；若結(jié)點p有右孩子，則p->rchild指向其右孩子結(jié)點，否則令其指向其（中序）后繼。lchildltagrchildrtagdata結(jié)點類型LNodeStructLNode{ElementTypedata;StructLNode*lchild,*rchild;intltag,rtag;}P->ltag=p->lchild指向左孩子0p->lchild指向（中序）前驅(qū)P->rtag=p->rchild指向右孩子0p->rchild指向（中序）后繼討論：為方便操作利用了n+1個指針，但為實現(xiàn)操作卻多

用了2n個標志位，如何理解？TypdefStructLNode*THTREE;類似線性鏈表，為每個線索樹增加一個頭結(jié)點。并設(shè)：

head->lchild=T(二叉樹的根);head->rchild=head;head->ltag=1;head->rtag=1;當線索樹為空時：

head->lchild=head;head->rchild=head;head->ltag=0;head->rtag=1;中序線索化：1、將二叉樹的空指針改為指向前驅(qū)或后繼的線索；2、前驅(qū)或后繼的信息只有在遍歷時才能得到；3、線索化：在遍歷的過程中修改線索；

pre始終指向剛剛訪問過的節(jié)點；

p指向當前訪問過的節(jié)點，pre指向他的前驅(qū)；StatusInOrderThreading(THTREE&Thrt,THTREET){if(!(Thrt=(THTREE)malloc(Sizeof(LNode))))exit(OVERFLOW);//頭結(jié)點

Thrt->ltag=1;Thrt->rtag=1;Thrt->rchild=Thrt;//右指針回指

if(!T){Thrt->lchild=Thrt;Thrt->ltag=0;}//若二叉樹空則左指針回指

else{Thrt->lchild=T;pre=Thrt;

InThreading(T);//中序線索化

Pre->rchild=Thrt;pre->rtag=0;//最后結(jié)點線索化

Thrt->rchild=pre;//另外一種定義方式

}returnOK;}VoidInThreading(THTREEp){if(p){InThreading(p->lchild);//左子樹線索化

if(!p->lchild){p->ltag=0;p->lchild=pre;}//左線索

if(!pre->rchild){pre->rtag=0;pre->rchild=p;}//右線索

pre=p;//pre指向p的前驅(qū)

InThreading(p->rchild);//右子樹線索化

}}中序線索化算法THTREEInNext(THTREEp){THTREEQ;Q=p->rchild;if(p->rtag==1)while(Q->ltag==1)Q=Q->lchild;return(Q);}【例3-19】求p$（中序后繼）分析：(1)當p->rtag=0時，p->rchild既為所求（線索）；

(2)當p->rtag=1時，p$為p的右子樹的最左結(jié)點。THTREEInPre(THTREEp){THTREEQ;Q=p->lchild;if(p->ltag==1)while(Q->rtag==1)Q=Q->rchild;return(Q);}【例3-20】求$p（中序前驅(qū)）分析：(1)當p->ltag=0時，p->lchild既為所求（線索）；

(2)當p->ltag=1時，$p為p的左子樹的最右結(jié)點。p$pp$p【例3-21】利用InNext算法，中序遍歷線索二叉樹。VoidTHInOrder(THTREEHEAD){THTREEtemp;temp=HEAD;do{temp=

InNext(temp);if(temp!=HEAD)visit(temp->data);}while(temp!=HEAD);}head->lchild=Thead->rchild=head;head->ltag=1;head->rtag=1;voidInOrderTraverse_Thr(THTREET){

p=T->lchild;

while(p!=T)

{

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

visit(p->data);

while(p->rtag==0&&p->rchild!=T)

{

p=p->rchild;

visit(p->data);

}

p=p->rchild;}非遞歸，不利用棧，中序遍歷（中序）線索二叉樹。

而在線索樹中結(jié)點的插入與刪除操作則不同，因為要同時考慮修正線索的操作。

在二叉樹中一般不討論結(jié)點的插入與刪除操作，原因是其插入與刪除的操作與線性表相同，所不同的是需要詳細說明操作的具體要求。例：將結(jié)點R插入作為結(jié)點S的右孩子結(jié)點。（1）若S的右子樹為空，插入比較簡單;

（2）若S的右子樹非空，則R插入后原來S的右子樹作為R的右子樹。操作：VoidRINSERT(

THTREE

S,

THTREE

R){THTREE

W;

R->rchild=S->rchild;R->rtag=S->rtag;

R->lchild=S;R->ltag=0;

S->rchild=R;S->rtag=1;

if(R->rtag==1){w=InNext(R);w->lchild=R;}3.2.5二叉樹的復(fù)制1、二叉樹的相似與等價兩棵二叉樹具有相同結(jié)構(gòu)指：（1）它們都是空的；（2）它們都是非空的，且左右子樹分別具有相同結(jié)構(gòu)?！径x】具有相同結(jié)構(gòu)的二叉樹為相似二叉樹?！径x】相似且相應(yīng)結(jié)點包含相同信息的二叉樹稱為

等價二叉樹?！靶螤睢毕嗤袛鄡煽枚鏄涫欠竦葍r算法：intEqual(firstbt,secondbt)BTREEfirstbt,secondbt;{intx;x=0;if(IsEmpty(firstbt)&&IsEmpty(secondbt))x=1;elseif(!IsEmpty(firstbt)&&!IsEmpty(secondbt))if(Data(firstbt)==Data(secondbt))if(Equal(Lchild(firstbt),Lchild(secondbt)))x=Equal(Rchild(firstbt),Rchild(secondbt))return(x);}/*Equal*/2、二叉樹的復(fù)制BTREECopy(BTREEoldtree){BTREEtemp;if(oldtree!=Null){temp=NewNode;temp->lchild=Copy(oldtree->lchild);temp->rchild=Copy(oldtree->rchild);temp->data=oldtree->data;return(temp);}return(Null);}/*Copy*/3.3堆（Heap）

如果一棵完全二叉樹的任意一個非終端結(jié)點的元素都不小于其左兒子結(jié)點和右兒子結(jié)點（如果有的話）的元素，則稱此完全二叉樹為最大堆。同樣，如果一棵完全二叉樹的任意一個非終端結(jié)點的元素都不大于其左兒子結(jié)點和右兒子結(jié)點（如果有的話）的元素，則稱此完全二叉樹為最小堆。堆的特點：

最大堆的根結(jié)點中的元素在整個堆中是最大的；最小堆的根結(jié)點中的元素在整個堆中是最小的。（最大堆）操作：1、MaxHeap(heap)創(chuàng)建一個空堆

2、HeapFull(heap)判斷堆是否為滿

3、Insert(heap,item)插入一個元素

4、HeapEmpty(heap)判斷堆是否為空

5、DeleteMax(heap)刪除最大元素#defineMaxsize200（最大堆）類型定義Typedefstruct{intkey;/*otherfields*/}ElementType;Typedefstruct{ElementTypeelements[MaxSize];intn;/*當前元素個數(shù)計數(shù)器*/}HEAP;VoidMaxHeap(Heapheap){heap.n=0;}BoolHeapEmpty(HEAPheap){return(!heap.n);}BoolHeapFull(HEAPheap){return(heap.n==MaxSize-1);}堆ADT操作453018152794312850453018155094312827455018153094312827504518153094312827453018152794312850Insert(HEAPheap,ElementTypeelement)453018152794312850…504518153094312827…VoidInsert(HEAPheap,ElementTypeelement){inti;if(！HeapFull(heap)){i=heap.n+1;while((i!=1)&&(element>heap.element[i/2])){heap.elements[i]=heap.elements[i/2];

i/=2;}heap.elements[i]=element;}heap.n++;}i/2i樹的高度為┏log(n+1)┓Tn=O(logn)830181527943124530818152794312302718158943124530181527943128DeleteMax(HEAPheap)4530181527943128…3027181589431245…VoidDeleteMax(HEAPheap)刪除堆中的最大元素（根）{intparent=1,child=2;ElementTypeelement,tmp;if(！HeapEmpty(heap)){element=heap.elements[1];tmp=heap.elements[heap.n--];while(child<=heap.n){if((child<heap.n)&&(heap.element[child]<heap.elements[child+1]))child++;if(tmp>=heap.elements[child])break;heap.elements[parent]=heap.elements[child];parent=child;

child*=2;}heap.elements[parent]=tmp;returnelement;}}2i+1n2ii樹的高度為┏log(n+1)┓Tn=O(logn)3.4選擇樹（SelectionTree）610920689901796817681516203820301525152011161001101820123456789101112131415

順串12345678一棵選擇樹是一棵二叉樹，其中每一個結(jié)點都代表該結(jié)點兩個兒子中的較小者。這樣，樹的根結(jié)點就表示樹中最小元素的結(jié)點。順串4中的6為勝利者81092015899017915817981516203820302525152011161001101820123456789101112131415√√√√810920689901710209909171234567891011121314156

順串12345678最終獲勝者競賽在兄弟結(jié)點之間進行結(jié)果放在父結(jié)點中。3.5樹3.5.1抽象數(shù)據(jù)型樹Parent(n,T)求結(jié)點n的雙親；LeftMost-Child(n,T)返回結(jié)點n的最左兒子；Right-Sibling(n,T)返回結(jié)點n的右兄弟；Data(n,T)返回結(jié)點n的信息；Createk(v,T1,T2,……,Tk),k=1,2,……

建立data域v的根結(jié)點r,有k棵子樹T1,T2,……,Tk

且自左至右排列；返回r；Root(T)返回樹T的根結(jié)點。樹的三種遍歷先(根)序

訪問根結(jié)點；先根順序遍歷T1;

先根順序遍歷T2;…

先根順序遍歷Tk;T1T2TknT…中(根)序中根順序遍歷T1;

訪問根結(jié)點；中根順序遍歷T2;…

中根順序遍歷Tk;后(根)序后根順序遍歷T1;

后根順序遍歷T2;…

后根順序遍歷Tk;

訪問根結(jié)點；【例3-22】假設(shè)樹的類型為TREE，結(jié)點的類型為Node，數(shù)據(jù)項的類型為elementtype，用遞歸方法給出樹的先根遍歷如下：VoidPreOrder(n,T)Noden;TREET;{Nodec;visit(Data(T));c=LeftMost-Child(n,T);while(c!=Null){PreOrder(c,T);c=Right-Sibling(c,T);}}3.5.2樹的存儲結(jié)構(gòu)1、樹的雙親表示法（數(shù)組實現(xiàn)方法）樹的結(jié)點依次編號為1，2，3，…，n；設(shè)數(shù)組A[i]A[i]=j若結(jié)點i的父親是j0若結(jié)點i是根1234567890111223012345678944A123456789一般有：Parent(i)=A[i]StructNode{intparent;chardata;};TypdefNodeTREE[11];TREET;面向特定的操作，設(shè)計