3.1基本術(shù)語(yǔ)3.2二叉樹*3.3堆3.4選擇樹3.5樹3.6森林與二叉樹間的轉(zhuǎn)換3.7樹的應(yīng)用第3章樹（Tree）線性表——元素之間的線性關(guān)系樹——元素之間的層次關(guān)系3.1基本術(shù)語(yǔ)[定義]

一1、一個(gè)結(jié)點(diǎn)x組成的集{x}是一株樹(Tree)，這個(gè)結(jié)點(diǎn)x也是這株樹的根。2、假設(shè)x是一個(gè)結(jié)點(diǎn)，D1，D2，…，Dk是k株互不相交的樹，我們可以構(gòu)造一株新樹：令x為根，并有k條邊由

x指向樹D1，D2，…，Dk。這些邊也叫做分支，D1，D2，

…，Dk稱作根x的樹之子樹（SubTree）。樹是n（≥0）個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中：

1、有且僅有特定的稱為根（Root）的結(jié)點(diǎn)；

2、當(dāng)n＞1時(shí)，其余結(jié)點(diǎn)可分為k（＞0）個(gè)互不相交的有限集D1，D2，…，Dk，其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹（SubTree

）。[定義]

二[定義三]T=（D，R）D：具有相同類型的數(shù)據(jù)元素的集合。R：若D為空集，則稱為空樹；若D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則R={H}，H是如下的二元關(guān)系：1、在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)；2、若D-{root}≠￠，則存在D-{root}的一個(gè)劃分D1，D2，…，

Dk（k＞0），對(duì)任意j≠l（1≤j，l

≤k）有Dj∩Dl=￠，且對(duì)任意的i（1≤i≤m），唯一存在數(shù)據(jù)元素xi∈Di，有<root,xi>∈H;3、對(duì)應(yīng)于D-{root}的劃分，H-{<root,x1>,…,<root,xk>}有唯一的一個(gè)劃分H1，H2，…，Hk

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

（1≤i≤k），Hi是Di上的二元關(guān)系，（Di，{Hi}）是一棵符合本定義的樹，稱為根root的子樹。三個(gè)定義的共同點(diǎn)：1、相同類型的元素構(gòu)成的集合2、特定的結(jié)點(diǎn)---根3、除了根之外，組成k個(gè)劃分，且互不相交4、每一個(gè)劃分又是一棵樹---遞歸ABCDEFGHIJKLM圖一第1層第2層第3層第4層第5層ABCDEFGHIJKLM圖二樹高為5常用術(shù)語(yǔ)：結(jié)點(diǎn)度葉（終端結(jié)點(diǎn)）非終端結(jié)點(diǎn)分支路長(zhǎng)父親雙親兒子兄弟子孫祖先層結(jié)點(diǎn)的高樹的高（深度）有序樹

&無(wú)序樹ABCACB≠森林forest：是n≥0株互不相交的樹的集合。3.2二叉樹(binarytree)[定義一]

二叉樹是有限個(gè)結(jié)點(diǎn)的集合，這個(gè)集合或者是空集，或者是由一個(gè)根結(jié)點(diǎn)和兩株互不相交的二叉樹組成，其中一株叫根的做左子樹，另一棵叫做根的右子樹。3.2.1二叉樹的定義和基本性質(zhì)[定義二]BinaryTree=(D,R)D：指數(shù)據(jù)對(duì)象，是由相同類型的數(shù)據(jù)元素組成的集合。R：為數(shù)據(jù)元素間的關(guān)系：若D＝￠，則R=￠，稱Binarytree為空樹；若D≠￠；則R={H}，H是如下二元關(guān)系：⑴在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(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}）是符合本定義的二叉樹，稱為根的右子樹；與樹的定義對(duì)比：1、相同類型的元素構(gòu)成的集合2、特定的結(jié)點(diǎn)---根3、除了根之外，組成k個(gè)劃分，且互不相交4、每一個(gè)劃分又是一棵二叉樹---遞歸k<=2分左、右二叉樹是有序的問(wèn)題：具有三個(gè)結(jié)點(diǎn)的樹和二叉樹各有多少棵？為什么？二叉樹的性質(zhì)：性質(zhì)1：在二叉樹中第i層的結(jié)點(diǎn)數(shù)最多為2i-1（i≥1）。性質(zhì)2：高度為k的二叉樹其結(jié)點(diǎn)總數(shù)最多為2k－1（k≥1）性質(zhì)3：對(duì)任意的非空二叉樹T，如果葉結(jié)點(diǎn)的個(gè)數(shù)為n0，而其度為2的結(jié)點(diǎn)數(shù)為n2，則：

n0=n2+1[定義]

深度為k且有2k－1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。層序編號(hào)：對(duì)滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)。從根結(jié)點(diǎn)開始，從上而下，自左至右。[定義]

深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)，稱之為完全二叉樹。二叉樹的性質(zhì)(續(xù))：性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。性質(zhì)5

如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i有：⑴如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無(wú)雙親；如果

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

n，則結(jié)點(diǎn)i無(wú)左孩子結(jié)點(diǎn)，否則其左孩子結(jié)點(diǎn)是2i；⑶如果2i+1＞

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

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

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

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

{中根順序遍歷左子樹；

訪問(wèn)根結(jié)點(diǎn)；中根順序遍歷右子樹；

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

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

訪問(wèn)根結(jié)點(diǎn)；

}；3.2.2抽象數(shù)據(jù)型二叉樹操作：①EMPTY(BT);②ISEMPTY(BT);③CREATEBT(V,LT,RT);④LCHILD(BT);⑤RCHILD(BT);⑥D(zhuǎn)ATA(BT);例1-1：寫一個(gè)遞歸函數(shù)，按先根順序列出二叉樹中每個(gè)結(jié)點(diǎn)的DATA

域之值。VoidPREORDER(BT)BTREEBT;{if(!ISEMPTY(BT)){visit(DATA(BT));PREORDER(LCHILD(BT));PREORDER(RCHILD(BT));}}例1-2：寫一個(gè)遞歸函數(shù)，按中根順序列出二叉樹中每個(gè)結(jié)點(diǎn)的DATA

域之值。VoidINORDER(BT)BTREEBT;{if(!ISEMPTY(BT)){INORDER(LCHILD(BT));

visit(DATA(BT));INORDER(RCHILD(BT));}}例1-3：寫一個(gè)遞歸函數(shù)，按后根順序列出二叉樹中每個(gè)結(jié)點(diǎn)的DATA

域之值。VoidPOSTORDER(BT)BTREEBT;{if(!ISEMPTY(BT)){POSTORDER(LCHILD(BT));POSTORDER(RCHILD(BT));

visit(DATA(BT));}}ABCDEFGHIJKLM例二叉樹的遍歷的非遞歸過(guò)程先序：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非空){進(jìn)棧;

左一步;}else{退棧;

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

設(shè)棧S:

用以保留當(dāng)前結(jié)點(diǎn);二叉樹的遍歷的非遞歸過(guò)程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);}}進(jìn)棧;左走一步退棧;右走一步先序遍歷非遞歸算法Loop:{if(BT非空){輸出;

進(jìn)棧;

左一步;}else{退棧;

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

左一步;}else{退棧;

輸出;

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

左一步;}else{當(dāng)棧頂指針?biāo)附Y(jié)點(diǎn)的右子樹不存在或已訪問(wèn),

退棧并訪問(wèn);

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

進(jìn)棧;

左一步;}else{退棧;

右一步;}};voidPreOrder(BTREE*root)//先序遍歷，非遞歸{BTREE*stack[MAX];inttop=0;do{while(root!=NULL) { printf("%c",root->data);top++;if(top>MAX) printf("棧滿!\n");elsestack[top]=root;root=root->lchild; }if(top!=0) { root=stack[top];top--;root=root->rchild; }}while((top!=0)||(root!=NULL));}Loop:{if(BT非空){進(jìn)棧;

左一步;}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=root->lchild; }p=NULL; b=1;while((top!=0)&&b)//右子樹不存在或已訪問(wèn)

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

top--; p=root; }//p指向剛訪問(wèn)

else { root=root->rchild;//結(jié)點(diǎn)

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

左一步;}else{當(dāng)棧頂指針?biāo)附Y(jié)點(diǎn)的右子樹不存在或已訪問(wèn),

退棧并訪問(wèn);

否則右一步;}};3.2.3二叉樹的表示1、順序存儲(chǔ)

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

A

B

C

D

E^^F^^G^^H^^I^^J^lchildrchilddataStructnode{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;}2、二叉樹的左右鏈表示證明：n個(gè)結(jié)點(diǎn)的二叉樹中，共有n+1個(gè)空鏈接域。證：設(shè)其空鏈域數(shù)為x

分支數(shù)B入

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

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

得出x=n+1ABCDEFGHIJKLM結(jié)點(diǎn)總數(shù)：13空鏈域的個(gè)數(shù)：14例1:二叉樹建立方法之一按先序序列建立二叉樹的左右鏈結(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);}例2：一棵二叉樹的先序、中序和后序序列分別如下，其中一部分未顯示出來(lái)，試求出空格處的內(nèi)容，并畫出該二叉樹。先序：_B_F_ICEH_G

中序：D_KFIA_EJC_

后序：_K_FBHJ_G_A

先序：ABDFKICEHJG

中序：DBKFIAHEJCG

后序：DKIFBHJEGCAABCDEFGHIJK例3：二叉樹中序序列為：ABCEFGHD，后序序列為：ABFHGEDC畫出此二叉樹ABCDEFGH完全二叉樹的某結(jié)點(diǎn)若無(wú)左孩子結(jié)點(diǎn)，則它必是葉結(jié)點(diǎn)？先序遍歷和中序遍歷相同的二叉樹？先序遍歷和后序遍歷相同的二叉樹？中序遍歷和后序遍歷相同的二叉樹？試舉出：例4：例5：設(shè)高為h的二叉樹只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹的結(jié)點(diǎn)樹至少為

，至多為

。答案：2h-1

和

2h-1例6：一棵有124個(gè)葉子結(jié)點(diǎn)的完全二叉樹，最多有

？

個(gè)結(jié)點(diǎn)。n0=n2+1n=n0+n1+n2n=n1+2n0-1但在完全二叉樹中，n1不是0就是1只有n1=1時(shí)，n取最大值為2n0例7：證明任一棵滿二叉樹T中的分支數(shù)B滿足:

B=2(n0-1)

，其中n0為葉子結(jié)點(diǎn)數(shù)證明：滿二叉樹中不存在度為1的節(jié)點(diǎn)，設(shè)度為2的結(jié)點(diǎn)數(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)例8：具有n

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

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

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

但對(duì)滿二叉樹，除有n0=n2+1外，還有n1=0

故有：n=n0+n0-1

n0=(n+1)/2例9：BTREE*Setup3(BTREE*bt,intn)//交互問(wèn)答方式創(chuàng)建二叉樹{charch;if(n==0)printf("根結(jié)點(diǎn):");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);}例10：二叉樹建立方法之二例11：求任意二叉樹的寬度。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);}}例12：求任意二叉樹的深度。思考題：（1）如何判斷一顆任意二叉樹是否為滿二叉樹？（2）如何判斷一顆任意二叉樹是否為完全二叉樹？（3）求二叉樹任意結(jié)點(diǎn)所在的層？（4）求任意結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)（根到該結(jié)點(diǎn)的路徑）（5）統(tǒng)計(jì)任意二叉樹中的結(jié)點(diǎn)個(gè)數(shù)？總結(jié)點(diǎn)、度為2、度為1、度為0的結(jié)點(diǎn)個(gè)數(shù)線索二叉樹問(wèn)題的提出：1、在n個(gè)結(jié)點(diǎn)的二叉樹左右鏈表示中，有n+1個(gè)空鏈域。如何利用n+1個(gè)空鏈域，使二叉樹的操作更加方便。2、在二叉樹左右鏈表示中，為求某個(gè)結(jié)點(diǎn)的（中序）前驅(qū)$P或（中序）后繼p$，每次都要從樹根開始進(jìn)行查找，很不方便。定義：若結(jié)點(diǎn)p有左孩子，則p->lchild指向其左孩子結(jié)點(diǎn)，否則令其指向其（中序）前驅(qū)。若結(jié)點(diǎn)p有右孩子，則p->rchild指向其右孩子結(jié)點(diǎn)，否則令其指向其（中序）后繼。lchildltagrchildrtagdata結(jié)點(diǎn)類型NodeStructLNode{Elementtypedata;StructLNode*lchild,*rchild;intltag,rtag;}P->ltag=p->lchild指向左孩子0p->lchild指向（中序）前驅(qū)P->rtag=p->rchild指向右孩子0p->lchild指向（中序）后繼討論：為方便操作利用了n+1個(gè)結(jié)點(diǎn)，但為實(shí)現(xiàn)操作卻多用了2n個(gè)標(biāo)志位。TypdefStructLNode*THTREE;類似線性鏈表，為每個(gè)線索樹增加一個(gè)頭結(jié)點(diǎn)。并設(shè)：

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

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

pre始終指向剛剛訪問(wèn)過(guò)的節(jié)點(diǎn)；

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

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é)點(diǎn)線索化

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);}例一：求p$（中序后繼）：分析：(1)當(dāng)p->rtag=0時(shí)，p->rchild既為所求（線索）。

(2)當(dāng)p->rtag=1時(shí)，p$為p的右子樹的最左結(jié)點(diǎn)。THTREE

INPRE(THTREEp){THTREEQ;Q=p->lchild;if(p->ltag==1)while(Q->rtag==1)Q=Q->rchild;return(Q);}例二：求$p（中序前驅(qū)）：分析：(1)當(dāng)p->ltag=0時(shí)，p->lchild既為所求（線索）。

(2)當(dāng)p->ltag=1時(shí)，$p為p的左子樹的最右結(jié)點(diǎn)。p$pp$p例三：利用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;

而在線索樹中結(jié)點(diǎn)的插入與刪除則不同，因?yàn)橐瑫r(shí)考慮修正線索的操作。

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

（2）若S的右子樹非空，則p插入后原來(lái)S的右子樹作為p的右子樹操作：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.4二叉樹的復(fù)制二叉樹的相似與等價(jià)兩株二叉樹具有相同結(jié)構(gòu)指：（1）它們都是空的；（2）它們都是非空的，且左右子樹分別具有相同結(jié)構(gòu)。定義具有相同結(jié)構(gòu)的二叉樹為相似二叉樹。相似且相應(yīng)結(jié)點(diǎn)包含相同信息的二叉樹稱為等價(jià)二叉樹。“形狀”相同判斷兩株二叉樹是否等價(jià)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*/二叉樹的復(fù)制BTREE

COPY(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）

如果一棵完全二叉樹的任意一個(gè)非終端結(jié)點(diǎn)的元素都不小于其左兒子結(jié)點(diǎn)和右兒子結(jié)點(diǎn)（如果有的話）的元素，則稱此完全二叉樹為最大堆。同樣，如果一棵完全二叉樹的任意一個(gè)非終端結(jié)點(diǎn)的元素都不大于其左兒子結(jié)點(diǎn)和右兒子結(jié)點(diǎn)（如果有的話）的元素，則稱此完全二叉樹為最小堆。最大堆的根結(jié)點(diǎn)中的元素在整個(gè)堆中是最大的；最小堆的根結(jié)點(diǎn)中的元素在整個(gè)堆中是最小的。（最大堆）操作：1、MaxHeap(heap)創(chuàng)建一個(gè)空堆

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

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

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

5、DeleteMax(heap)刪除最大元素#defineMaxsize200（最大堆）類型定義Typedefstruct{intkey;/*otherfields*/}Elementtype;Typedefstruct{Elementtypeelements[MaxSize];intn;/*當(dāng)前元素個(gè)數(shù)計(jì)數(shù)器*/}HEAP;VoidMaxHeap(Heapheap){heap.n=0;}BoolHeapEmpty(HEAPheap){return(!heap.n);}BoolHeapFull(HEAPheap){return(heap.n==MaxSize-1);}堆操作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一棵選擇樹是一棵二叉樹，其中每一個(gè)結(jié)點(diǎn)都代表該結(jié)點(diǎn)兩個(gè)兒子中的較小者。這樣，樹的根結(jié)點(diǎn)就表示樹中最小元素的結(jié)點(diǎn)。順串4中的6為勝利者81092015899017915817981516203820302525152011161001101820123456789101112131415√√√√810920689901710209909171234567891011121314156

順串12345678最終獲勝者競(jìng)賽在兄弟結(jié)點(diǎn)之間進(jìn)行結(jié)果放在父結(jié)點(diǎn)中3.5樹3.5.1抽象數(shù)據(jù)型樹PARENT(n,T)求結(jié)點(diǎn)n的雙親LEFTMOST-CHILD(n,T)返回結(jié)點(diǎn)n的最左兒子RIGHT-SIBLING(n,T)返回結(jié)點(diǎn)n的右兄弟DATA(n,T)返回結(jié)點(diǎn)n的信息CREATEk(v,T1,T2,……,Tk),k=1,2,……

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

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

訪問(wèn)根結(jié)點(diǎn)；先根順序遍歷T1;

先根順序遍歷T2;…

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

訪問(wèn)根結(jié)點(diǎn)；中根順序遍歷T2;…

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

后根順序遍歷T2;…

后根順序遍歷Tk;

訪問(wèn)根結(jié)點(diǎn)；例：假設(shè)樹的類型為TREE，結(jié)點(diǎn)的類型為node，數(shù)據(jù)項(xiàng)的類型為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樹的存儲(chǔ)結(jié)構(gòu)1、樹的雙親表示法（數(shù)組實(shí)現(xiàn)方法）樹的結(jié)點(diǎn)依次編號(hào)為1，2，3，…，n；設(shè)數(shù)組A[i]A[i]=j若結(jié)點(diǎn)i的父親是j0若結(jié)點(diǎn)i是根1234567890111223012345678944A123456789一般有：PARENT(i)=A[i]Structnode{intparent;chardata;};TypdefnodeTREE[11];TREET;T[7].parent=5;T[7].data=1;面向特定的操作，設(shè)計(jì)合適的存儲(chǔ)結(jié)構(gòu)ABCDEFG0123456789HIT011122344123456789ABCDEFGHI樹的雙親表示法的改進(jìn)方案Typedefintnode;TypedefnodeTREE[maxnodes];nodeLEFTMOST-CHILD(n,T)noden;TREET;{nodei;for(i=n+1;i<=maxnodes–1;i++)if(T[i]==n)return(i);i為最左孩子

return(0);n是葉子}算法LEFTMOST-CHILD2、樹的孩子表示法（鄰接表表示法）RABCDEFGKHtypedefstructCTNode{intchild;structCTNode*next;}*ChildPtr;typedefstruct{Telementtypedata;ChildPtrfirstchild;}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;}Ctree;04A14B∧24C30D∧4-1R50E∧62F74G∧84H∧94K∧35∧6∧01789∧2∧0A1B∧2C3D∧4R5E∧6F7G∧8H∧9K∧35∧6∧01789∧2∧3、樹的孩子兄弟表示法（二叉樹表示法）RABCDEFGKHRABCDEFGKHRABCDEFGKH類型：typedefstructCSNode{ElemTypedata;structCSNode*firstchild,*nextsibling;};遍歷先序RADEBCFGHKRADEBCFGHK中序DAERBGFHKCDEABGHKFCR后序DEABGHKFCREDKHGFCBAR樹二叉樹3.6森林與二叉樹森林轉(zhuǎn)換為二叉樹：1、先將森林中每棵樹轉(zhuǎn)換成二叉樹2、二叉樹的樹根連接起來(lái)ABCDEFGHIJAEFGHIJBCDAFHIJBCDEG森林與二叉樹對(duì)應(yīng)樹與二叉樹對(duì)應(yīng)樹根相連遍歷森林與遍歷二叉樹的對(duì)應(yīng)關(guān)系遍歷森林遍歷相應(yīng)的二叉樹先根訪問(wèn)第一棵樹的根先根順序遍歷第一棵樹的全部子樹先根順序遍歷其余全部樹先根訪問(wèn)樹根先根順序遍歷左子樹先根順序遍歷右子樹后根后根順序遍歷第一棵樹的全部子樹訪問(wèn)第一棵樹的根后根順序遍歷其余的樹中根中根順序遍歷左子樹訪問(wèn)樹根中根順序遍歷右子樹遍歷森林與遍歷樹的對(duì)應(yīng)關(guān)系遍歷森林遍歷樹先根訪問(wèn)第一棵樹的根先根順序遍歷第一棵樹的全部子樹先根順序遍歷其余全部樹先根訪問(wèn)根先根順序遍歷全部子樹后根后根順序遍歷第一棵樹的全部子樹訪問(wèn)第一棵樹的根后根順序遍歷其余的樹后根中根順序遍歷全部子樹訪問(wèn)根3.7樹的應(yīng)用路徑長(zhǎng)度增長(zhǎng)樹內(nèi)結(jié)點(diǎn)外結(jié)點(diǎn)如內(nèi)結(jié)點(diǎn)數(shù)為n，則外結(jié)點(diǎn)S=n+1內(nèi)結(jié)點(diǎn)路徑長(zhǎng)度I=2×1+3×2+1×3=11外結(jié)點(diǎn)路徑長(zhǎng)度E=1×2+5×3+2×4=25如內(nèi)結(jié)點(diǎn)路徑長(zhǎng)度為I，則外結(jié)點(diǎn)路徑長(zhǎng)度E=I＋2×n114232341111423(a)(b)(c)設(shè)：

w

i={2,3,4,11}求：∑wj·

lj（加權(quán)路長(zhǎng)）（a）11×1＋4×2＋2×3＋3×3=34（b）2×1＋3×2＋4×3＋11×3=53（c）2×2＋11×2＋3×2＋4×2=403.7.1哈夫曼樹及其應(yīng)用哈夫曼（Huffman）樹給定實(shí)數(shù)w={w1,w2,…,wm}，構(gòu)造以wi為權(quán)的增長(zhǎng)樹，其中∑wi·li最小的一棵二叉樹稱為哈夫曼樹。哈夫曼算法（P113）238voidSelectMin(HuffmanTT,intn1,int*p1,int*p2){inti,j;for(i=0;i<=n1;i++)if(T[i].parent==-1){*p1=i;break;}for(j=i+1;j<=n1;j++)if(T[j].parent==-1){*p2=j;break;}for(i=0;i<=n1;i++)if((T[*p1].weight>T[i].weight)&&(T[i].parent==-1)&&(*p2!=i))*p1=i;for(j=0;j<=n1;j++)if((T[*p2].weight>T[j].weight)&&(T[j].parent==-1)&&(*p1!=j))*p2=j;}voidCreatHT(HuffmanTT)//創(chuàng)建哈夫曼樹{inti,p1,p2;InitHT(T);for(i=n;i<m;i++){SelectMin(T,i-1,&p1,&p2);T[p1].parent=T[p2].parent=i;T[i].lchild=p1;T[i].rchild=p2;T[i].weight=T[p1].weight+T[p2].weight;}}哈夫曼樹創(chuàng)建方法11.00.400.200.600.120.250.350.150.08bceda字符概率a0.12b0.40c0.15d0.08e0.251weightparentlchildrchild00.12-1-1-110.40-1-1-120.15-1-1-130.08-1-1-140.25-1-1-15--1-1-16--1-1-17--1-1-18--1-1-1weightparentlchildrchild00.125-1-110.408-1-120.156-1-130.085-1-140.257-1-150.2063060.3575270.6086481.00-117typedefstruct{floatweight;intlchild,rchild,parent;}HTNODE;typedefHTNODEHuffmanT[m];n=5m=9n?mtypedefstructHNODE{intdata,lev; structHNODE*next,*lchild,*rchild;}HTREE;datalevnextlchildrchild00^^0.081^^字符abcde概率0.120.400.150.080.250.121^^0.151^^0.251^^0.401^^^Head0.20200^^0.081^