數據結構 3第3章：樹學習課件

3.1基本術語3.2二叉樹*3.3堆3.4選擇樹3.5樹3.6森林與二叉樹間的轉換3.7樹的應用第3章樹（Tree）線性表——元素之間的線性關系樹——元素之間的層次關系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

）。[定義]

二[定義三]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≤m），唯一存在數據元素xi∈Di，有<root,xi>∈H;3、對應于D-{root}的劃分，H-{<root,x1>,…,<root,xk>}有唯一的一個劃分H1，H2，…，Hk

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

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

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

二叉樹是有限個結點的集合，這個集合或者是空集，或者是由一個根結點和兩株互不相交的二叉樹組成，其中一株叫根的做左子樹，另一棵叫做根的右子樹。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分左、右二叉樹是有序的問題：具有三個結點的樹和二叉樹各有多少棵？為什么？二叉樹的性質：性質1：在二叉樹中第i層的結點數最多為2i-1（i≥1）。性質2：高度為k的二叉樹其結點總數最多為2k－1（k≥1）性質3：對任意的非空二叉樹T，如果葉結點的個數為n0，而其度為2的結點數為n2，則：

n0=n2+1[定義]

深度為k且有2k－1個結點的二叉樹稱為滿二叉樹。層序編號：對滿二叉樹的結點進行連續(xù)編號。從根結點開始，從上而下，自左至右。[定義]

深度為k的，有n個結點的二叉樹，當且僅當其每個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應，稱之為完全二叉樹。二叉樹的性質(續(xù))：性質4

具有n個結點的完全二叉樹的深度為log2n+1。性質5

如果對一棵有n個結點的完全二叉樹的結點按層序編號，則對任一結點i有：⑴如果i=1，則結點i是二叉樹的根，無雙親；如果

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

n，則結點i無左孩子結點，否則其左孩子結點是2i；⑶如果2i+1＞

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

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

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

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

{中根順序遍歷左子樹；

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

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

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

訪問根結點；

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

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

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

visit(DATA(BT));INORDER(RCHILD(BT));}}例1-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=root->lchild;}if(top!=0){root=stack[top];top--;printf("%c",root->data);root=root->rchild; }}while((top!=0)||(root!=NULL));}Loop:{if(BT非空){輸出;

進棧;

左一步;}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非空){進棧;

左一步;}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)//右子樹不存在或已訪問

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

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

else { root=root->rchild;//結點

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

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

退棧并訪問;

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

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

分支數B入

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

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

得出x=n+1ABCDEFGHIJKLM結點總數：13空鏈域的個數：14例1:二叉樹建立方法之一按先序序列建立二叉樹的左右鏈結構.如下圖所示二叉樹,輸入: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：一棵二叉樹的先序、中序和后序序列分別如下，其中一部分未顯示出來，試求出空格處的內容，并畫出該二叉樹。先序：_B_F_ICEH_G

中序：D_KFIA_EJC_

后序：_K_FBHJ_G_A

先序：ABDFKICEHJG

中序：DBKFIAHEJCG

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

，至多為

。答案：2h-1

和

2h-1例6：一棵有124個葉子結點的完全二叉樹，最多有

？

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

B=2(n0-1)

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

個結點的滿二叉樹，其葉子結點的個數為多少？具有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)/2例9：BTREE*Setup3(BTREE*bt,intn)//交互問答方式創(chuàng)建二叉樹{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);}例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）求二叉樹任意結點所在的層？（4）求任意結點的所有祖先結點（根到該結點的路徑）（5）統(tǒng)計任意二叉樹中的結點個數？總結點、度為2、度為1、度為0的結點個數線索二叉樹問題的提出：1、在n個結點的二叉樹左右鏈表示中，有n+1個空鏈域。如何利用n+1個空鏈域，使二叉樹的操作更加方便。2、在二叉樹左右鏈表示中，為求某個結點的（中序）前驅$P或（中序）后繼p$，每次都要從樹根開始進行查找，很不方便。定義：若結點p有左孩子，則p->lchild指向其左孩子結點，否則令其指向其（中序）前驅。若結點p有右孩子，則p->rchild指向其右孩子結點，否則令其指向其（中序）后繼。lchildltagrchildrtagdata結點類型NodeStructLNode{Elementtypedata;StructLNode*lchild,*rchild;intltag,rtag;}P->ltag=p->lchild指向左孩子0p->lchild指向（中序）前驅P->rtag=p->rchild指向右孩子0p->lchild指向（中序）后繼討論：為方便操作利用了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始終指向剛剛訪問過的節(jié)點；

p指向當前訪問過的節(jié)點，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);}例一：求p$（中序后繼）：分析：(1)當p->rtag=0時，p->rchild既為所求（線索）。

(2)當p->rtag=1時，p$為p的右子樹的最左結點。THTREE

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

(2)當p->ltag=1時，$p為p的左子樹的最右結點。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;

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

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

（2）若S的右子樹非空，則p插入后原來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二叉樹的復制二叉樹的相似與等價兩株二叉樹具有相同結構指：（1）它們都是空的；（2）它們都是非空的，且左右子樹分別具有相同結構。定義具有相同結構的二叉樹為相似二叉樹。相似且相應結點包含相同信息的二叉樹稱為等價二叉樹?！靶螤睢毕嗤袛鄡芍甓鏄涫欠竦葍rintEQUAL(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*/二叉樹的復制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）

如果一棵完全二叉樹的任意一個非終端結點的元素都不小于其左兒子結點和右兒子結點（如果有的話）的元素，則稱此完全二叉樹為最大堆。同樣，如果一棵完全二叉樹的任意一個非終端結點的元素都不大于其左兒子結點和右兒子結點（如果有的話）的元素，則稱此完全二叉樹為最小堆。最大堆的根結點中的元素在整個堆中是最大的；最小堆的根結點中的元素在整個堆中是最小的。（最大堆）操作：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;/*當前元素個數計數器*/}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一棵選擇樹是一棵二叉樹，其中每一個結點都代表該結點兩個兒子中的較小者。這樣，樹的根結點就表示樹中最小元素的結點。順串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;

訪問根結點；例：假設樹的類型為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;T[7].parent=5;T[7].data=1;面向特定的操作，設計合適的存儲結構ABCDEFG0123456789HIT011122344123456789ABCDEFGHI樹的雙親表示法的改進方案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森林與二叉樹森林轉換為二叉樹：1、先將森林中每棵樹轉換成二叉樹2、二叉樹的樹根連接起來ABCDEFGHIJAEFGHIJBCDAFHIJBCDEG森林與二叉樹對應樹與二叉樹對應樹根相連遍歷森林與遍歷二叉樹的對應關系遍歷森林遍歷相應的二叉樹先根訪問第一棵樹的根先根順序遍歷第一棵樹的全部子樹先根順序遍歷其余全部樹先根訪問樹根先根順序遍歷左子樹先根順序遍歷右子樹后根后根順序遍歷第一棵樹的全部子樹訪問第一棵樹的根后根順序遍歷其余的樹中根中根順序遍歷左子樹訪問樹根中根順序遍歷右子樹遍歷森林與遍歷樹的對應關系遍歷森林遍歷樹先根訪問第一棵樹的根先根順序遍歷第一棵樹的全部子樹先根順序遍歷其余全部樹先根訪問根先根順序遍歷全部子樹后根后根順序遍歷第一棵樹的全部子樹訪問第一棵樹的根后根順序遍歷其余的樹后根中根順序遍歷全部子樹訪問根3.7樹的應用路徑長度增長樹內結點外結點如內結點數為n，則外結點S=n+1內結點路徑長度I=2×1+3×2+1×3=11外結點路徑長度E=1×2+5×3+2×4=25如內結點路徑長度為I，則外結點路徑長度E=I＋2×n114232341111423(a)(b)(c)設：

w

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

lj（加權路長）（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哈夫曼樹及其應用哈夫曼（Huffman）樹給定實數w={w1,w2,…,wm}，構造以wi為權的增長樹，其中∑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^