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

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

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

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

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

的i（1≤i≤k），唯一存在數據元素xi∈Di，有<root,xi>∈H;（3）對應于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上的二元關系，（Di，{Hi}）是一棵符合本定義的樹，稱為根root的子樹。【定義三】三個定義的共同點：1、相同類型的元素構成的集合；2、特定的結點---根；3、除了根之外，組成k個劃分，且互不相交；4、每一個劃分又是一棵樹---遞歸；幾點說明：遞歸定義，但不會產生循環定義；構造性定義便于樹型結構的建立；一株樹的每個結點都是這株樹的某株子樹的根。ABCDEFGHIJKLM圖一第1層第2層第3層第4層第5層ABCDEFGHIJKLM圖二樹高為52、常用術語結點度葉（終端結點）非終端結點分支路長父親雙親兒子兄弟子孫祖先層結點的高樹的高（深度）有序樹

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

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

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

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

xr，<root,xr>∈H，且存在Dr上的關系Hr∈H；

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

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

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

log2n┘+1。性質5

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

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

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

n，則結點i無左孩子結點，否則其左孩

子結點是2i；⑶如果2i+1＞

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

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

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

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

{中根順序遍歷左子樹；

訪問根結點；中根順序遍歷右子樹；

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

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

訪問根結點；

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

visit(Data(BT));InOrder(Rchild(BT));}}【例3-3】寫一個遞歸函數，按后根順序列出二叉樹中每個結點的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^#結束算法:Loop:{if(BT非空){進棧;

左一步;}else{退棧；

輸出;

右一步;}};數據結構:

設棧S:

用以保留當前結點;二叉樹的遍歷的非遞歸過程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{當棧頂指針所指結點的右子樹不存在或已訪問,

退棧并訪問;

否則右一步;}};中序遍歷非遞歸算法：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));//訪問根結點

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

else {root=Rchild(root);

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

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

退棧并訪問;

否則右一步;}};3.2.3二叉樹的表示1、順序存儲（1）完全（或滿）二叉樹根據性質5，如已知某結點的層序編號i,則可求得該結點的雙親結點、左孩子結點和右孩子結點。ABCDEFGIHJABCDEFG12345678910HIJ采用一維數組，按層序順序依次存儲二叉樹的每一個結點。如下圖所示：（2）一般二叉樹ABC*E*G12345678910**J根據性質5，如已知某結點的層序編號i,則可求得該結點的雙親結點、左孩子結點和右孩子結點，然后檢測其值是否為虛設的特殊結點*。通過虛設部分結點，使其變成相應的完全二叉樹。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個結點的二叉樹中，共有n+1個空鏈接域。證：設其空鏈域數為x

分支數B入

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

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

得出x=n+1ABCDEFGHIJKLM結點總數：13空鏈域的個數：14【例3-4】二叉樹建立方法之一按先序序列建立二叉樹的左右鏈結構。如下圖所示二叉樹,輸入: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】二叉樹的遍歷（二叉鏈表結構）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】按層序遍歷二叉樹（二叉鏈表結構）

從二叉樹的第一層開始，直到最后一層，每層從左到右訪問每一個結點，是的每個結點只能被訪問一次。ABCDEFGIJH右圖所示二叉樹按層序遍歷結果為：ABCDEFGHIJ設立一個隊列，隊列元素為結點的指針；首先將根結點指針排隊；當隊列非空時，從隊首刪除一個結點，如果該結點的左子樹非空，則其左子樹結點指針指針排隊；如果該結點的右子樹非空，則其右子樹結點指針指針排隊；重復上述過程，直到隊列為空。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】一棵二叉樹的先序、中序和后序序列分別如下，其中一部分未顯示出來，試求出空格處的內容，并畫出該二叉樹。先序：_B_F_ICEH_G；

中序：D_KFIA_EJC_；

后序：_K_FBHJ_G_A；

先序：ABDFKICEHJG

中序：DBKFIAHEJCG

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

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

，至多為

。

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

最多有

？

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

B=2(n0-1)

，其中n0為葉子結點數。證明：滿二叉樹中不存在度為1的節點，設度為2的結點數為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

個結點的滿二叉樹，其葉子結點的個數

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

二叉樹總結點數n=2h-1；

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

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

故有：n=n0+n0-1

n0=(n+1)/2BTREE*Setup3(BTREE*bt,intn)//交互問答方式創建二叉樹{charch;if(n==0)printf("根結點:");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】求任意二叉樹的深度。討論：如果讓你設計一棵三叉樹，你會怎么做？ABCDEHFGT2ABCDEHFGT1IJKADHFGBECT3typedefstructBiTPNode{ElementTypedata;structBiTPNode*parent,*lchild,*rchild;}*BiPTree;二叉樹的三叉鏈表存儲表示parentlchilddatarchildBiTPNoden個結點的二叉樹有n+2個空指針！很顯然：相對二叉鏈表表示的二叉樹，除了找父結點的操作變得很容易外，其它基本操作沒有什么變化。問題：

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

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;}}}}}//若其不是從左子樹回溯來的，或左結點的父親并沒有右孩子

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

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

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、將二叉樹的空指針改為指向前驅或后繼的線索；2、前驅或后繼的信息只有在遍歷時才能得到；3、線索化：在遍歷的過程中修改線索；

pre始終指向剛剛訪問過的節點；

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

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;//最后結點線索化

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的前驅

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

(2)當p->ltag=1時，$p為p的左子樹的最右結點。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;}非遞歸，不利用棧，中序遍歷（中序）線索二叉樹。

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

在二叉樹中一般不討論結點的插入與刪除操作，原因是其插入與刪除的操作與線性表相同，所不同的是需要詳細說明操作的具體要求。例：將結點R插入作為結點S的右孩子結點。（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二叉樹的復制1、二叉樹的相似與等價兩棵二叉樹具有相同結構指：（1）它們都是空的；（2）它們都是非空的，且左右子樹分別具有相同結構。【定義】具有相同結構的二叉樹為相似二叉樹。【定義】相似且相應結點包含相同信息的二叉樹稱為

等價二叉樹。“形狀”相同判斷兩棵二叉樹是否等價算法：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、二叉樹的復制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）

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

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

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

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

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

5、DeleteMax(heap)刪除最大元素#defineMaxsize200（最大堆）類型定義Typedefstruct{intkey;/*otherfields*/}ElementType;Typedefstruct{ElementTypeelements[MaxSize];intn;/*當前元素個數計數器*/}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一棵選擇樹是一棵二叉樹，其中每一個結點都代表該結點兩個兒子中的較小者。這樣，樹的根結點就表示樹中最小元素的結點。順串4中的6為勝利者81092015899017915817981516203820302525152011161001101820123456789101112131415√√√√810920689901710209909171234567891011121314156

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

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

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

訪問根結點；先根順序遍歷T1;

先根順序遍歷T2;…

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

訪問根結點；中根順序遍歷T2;…

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

后根順序遍歷T2;…

后根順序遍歷Tk;

訪問根結點；【例3-22】假設樹的類型為TREE，結點的類型為Node，數據項的類型為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樹的存儲結構1、樹的雙親表示法（數組實現方法）樹的結點依次編號為1，2，3，…，n；設數組A[i]A[i]=j若結點i的父親是j0若結點i是根1234567890111223012345678944A123456789一般有：Parent(i)=A[i]StructNode{intparent;chardata;};TypdefNodeTREE[11];TREET;面向特定的操作，設計