數(shù)據(jù)結(jié)構(gòu)與算法：第3章 樹

3.1基本術(shù)語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ù)語[定義]

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

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

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

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

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

二[定義三]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，…，

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

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

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

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

二叉樹是有限個結(jié)點(diǎn)的集合，這個集合或者是空集，或者是由一個根結(jié)點(diǎn)和兩株互不相交的二叉樹組成，其中一株叫根的做左子樹，另一棵叫做根的右子樹。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é)點(diǎn)---根3、除了根之外，組成k個劃分，且互不相交4、每一個劃分又是一棵二叉樹---遞歸k<=2分左、右二叉樹是有序的問題：具有三個結(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：對任意的非空二叉樹T，如果葉結(jié)點(diǎn)的個數(shù)為n0，而其度為2的結(jié)點(diǎn)數(shù)為n2，則：

n0=n2+1[定義]

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

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

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

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

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

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

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

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

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

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

{中根順序遍歷左子樹；

訪問根結(jié)點(diǎ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：寫一個遞歸函數(shù)，按先根順序列出二叉樹中每個結(jié)點(diǎn)的DATA

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

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

visit(DATA(BT));INORDER(RCHILD(BT));}}例1-3：寫一個遞歸函數(shù)，按后根順序列出二叉樹中每個結(jié)點(diǎn)的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非空){進(jìn)棧;

左一步;}else{退棧;

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

設(shè)棧S:

用以保留當(dāng)前結(jié)點(diǎn);二叉樹的遍歷的非遞歸過程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)的右子樹不存在或已訪問,

退棧并訪問;

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

a、完全（或滿）二叉樹根據(jù)性質(zhì)5，如已知某結(jié)點(diǎn)的層序編號i,則可求得該結(jié)點(diǎn)的雙親結(jié)點(diǎn)、左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)。ABCDEFGIHJABCDEFG12345678910HIJ采用一維數(shù)組，按層序順序依次存儲二叉樹的每一個結(jié)點(diǎn)。如下圖所示：b、一般二叉樹ABC*E*G12345678910**J根據(jù)性質(zhì)5，如已知某結(jié)點(diǎn)的層序編號i,則可求得該結(jié)點(diǎn)的雙親結(jié)點(diǎn)、左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)，然后檢測其值是否為虛設(shè)的特殊結(jié)點(diǎn)*。通過虛設(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個結(jié)點(diǎn)的二叉樹中，共有n+1個空鏈接域。證：設(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空鏈域的個數(shù)：14例:按先序序列建立二叉樹的左右鏈結(jié)構(gòu).如由圖所示二叉樹,輸入:ABDH##I##E##CF#J##G##其中:#表示空ABCDEFGIJHStatusCreateBtree(BTREE&T){cin>>ch;if(ch==‘’)T=NULL;else{if(!(T=newBTREE))exit;T→data=ch;CreateBtree(T→lchild);CreateBtree(T→rchild);}returnOK;}

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

中序：D_KFIA_EJC_

后序：_K_FBHJ_G_A

先序：ABDFKICEHJG

中序：DBKFIAHEJCG

后序：DKIFBHJEGCAABCDEFGHIJK二叉樹中序序列為：ABCEFGHD，后序序列為：ABFHGEDC畫出此二叉樹ABCDEFGH完全二叉樹的某結(jié)點(diǎn)若無左孩子結(jié)點(diǎn)，則它必是葉結(jié)點(diǎn)？先序遍歷和中序遍歷相同的二叉樹？先序遍歷和后序遍歷相同的二叉樹？中序遍歷和后序遍歷相同的二叉樹？試舉出：一棵有124個葉子結(jié)點(diǎn)的完全二叉樹，最多有

？

個結(jié)點(diǎn)。n0=n2+1n=n0+n1+n2n=n1+2n0-1但在完全二叉樹中，n1不是0就是1只有n1=1時，n取最大值為2n0證明任一棵滿二叉樹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)具有n

個結(jié)點(diǎn)的滿二叉樹，其葉子結(jié)點(diǎn)的個數(shù)為多少？具有n個結(jié)點(diǎn)的完全二叉樹，其葉子結(jié)點(diǎn)的個數(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

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

故有：n=n0+n0-1

n0=(n+1)/2設(shè)高為h的二叉樹只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹的結(jié)點(diǎn)樹至少為

，至多為

。答案：2h-1

和

2h-1線索二叉樹問題的提出：1、在n個結(jié)點(diǎn)的二叉樹左右鏈表示中，有n+1個空鏈域。如何利用n+1個空鏈域，使二叉樹的操作更加方便。2、在二叉樹左右鏈表示中，為求某個結(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個結(jié)點(diǎn)，但為實(shí)現(xiàn)操作卻多用了2n個標(biāo)志位。TypdefStructLNode*THTREE;類似線性鏈表，為每個線索樹增加一個頭結(jié)點(diǎn)。并設(shè)：

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

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

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

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

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

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

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

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

Pre->rchild=Thrt;pre->rtag=1;//最后結(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)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時，p->rchild既為所求（線索）。

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

INPRE(THTREEp)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時，p->lchild既為所求（線索）。

(2)當(dāng)p->ltag=1時，$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考慮修正線索的操作。

在二叉樹中一般不討論結(jié)點(diǎn)的插入與刪除，原因是其插入與刪除的操作與線性表相同，所不同的是需要詳細(xì)說明操作的具體要求。例：將結(jié)點(diǎn)p插入作為結(jié)點(diǎn)S的右孩子結(jié)點(diǎn)。（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二叉樹的復(fù)制二叉樹的相似與等價兩株二叉樹具有相同結(jié)構(gòu)指：（1）它們都是空的；（2）它們都是非空的，且左右子樹分別具有相同結(jié)構(gòu)。定義具有相同結(jié)構(gòu)的二叉樹為相似二叉樹。相似且相應(yīng)結(jié)點(diǎn)包含相同信息的二叉樹稱為等價二叉樹?！靶螤睢毕嗤袛鄡芍甓鏄涫欠竦葍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*/二叉樹的復(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）

如果一棵完全二叉樹的任意一個非終端結(jié)點(diǎn)的元素都不小于其左兒子結(jié)點(diǎn)和右兒子結(jié)點(diǎn)（如果有的話）的元素，則稱此完全二叉樹為最大堆。同樣，如果一棵完全二叉樹的任意一個非終端結(jié)點(diǎn)的元素都不大于其左兒子結(jié)點(diǎn)和右兒子結(jié)點(diǎn)（如果有的話）的元素，則稱此完全二叉樹為最小堆。最大堆的根結(jié)點(diǎn)中的元素在整個堆中是最大的；最小堆的根結(jié)點(diǎn)中的元素在整個堆中是最小的。（最大堆）操作：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;/*當(dāng)前元素個數(shù)計(jì)數(shù)器*/}HEAP;VoidMaxHeap(Heapheap){heap.n=0;}BoolHeapEmpty(HEAPheap){return(!heap.n);}BoolHeapFull(HEAPheap){return(heap.n==MaxSize-1);}堆操作453018152794312850453018155094312827455018153094312827504518153094312827453018152794312850Insert(HEAPheap,Elementtypeelement)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;}i/2i樹的高度為┏log(n+1)┓Tn=O(logn)83018152794312830818152794312302718158943124530181527943128DeleteMax(HEAPheap)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é)點(diǎn)都代表該結(jié)點(diǎn)兩個兒子中的較小者。這樣，樹的根結(jié)點(diǎn)就表示樹中最小元素的結(jié)點(diǎn)。順串4中的6為勝利者81092015899017915817981516203820302525152011161001101820123456789101112131415√√√√810920689901710209909171234567891011121314156

順串12345678最終獲勝者競賽在兄弟結(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)樹的三種遍歷先(根)序

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

先根順序遍歷T2;…

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

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

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

后根順序遍歷T2;…

后根順序遍歷Tk;

訪問根結(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樹的存儲結(jié)構(gòu)1、樹的雙親表示法（數(shù)組實(shí)現(xiàn)方法）樹的結(jié)點(diǎn)依次編號為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ì)合適的存儲結(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、二叉樹的樹根連接起來ABCDEFGHIJAEFGHIJBCDAFHIJBCDEG森林與二叉樹對應(yīng)樹與二叉樹對應(yīng)樹根相連遍歷森林與遍歷二叉樹的對應(yīng)關(guān)系遍歷森林遍歷相應(yīng)的二叉樹先根訪問第一棵樹的根先根順序遍歷第一棵樹的全部子樹先根順序遍歷其余全部樹先根訪問樹根先根順序遍歷左子樹先根順序遍歷右子樹后根后根順序遍歷第一棵樹的全部子樹訪問第一棵樹的根后根順序遍歷其余的樹中根中根順序遍歷左子樹訪問樹根中根順序遍歷右子樹遍歷森林與遍歷樹的對應(yīng)關(guān)系遍歷森林遍歷樹先根訪問第一棵樹的根先根順序遍歷第一棵樹的全部子樹先根順序遍歷其余全部樹先根訪問根先根順序遍歷全部子樹后根后根順序遍歷第一棵樹的全部子樹訪問第一棵樹的根后根順序遍歷其余的樹后根中根順序遍歷全部子樹訪問根3.7樹的應(yī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)路徑長度I=2×1+3×2+1×3=11外結(jié)點(diǎn)路徑長度E=1×2+5×3+2×4=25如內(nèi)結(jié)點(diǎn)路徑長度為I，則外結(jié)點(diǎn)路徑長度E=I＋2×n114232341111423(a)(b)(c)設(shè)：

w

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

lj（加權(quán)路長）（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)的增長樹，其中∑wi·li最小的一棵二叉樹稱為哈夫曼樹。哈夫曼算法（P113）例：輸入一批學(xué)生成績，將百分制轉(zhuǎn)換成五級分制。并且已知：

分?jǐn)?shù)0-5960-6970-7980-8990-100比例數(shù)0.050.150.400.300.10If(a<60)b=“fail”Elseif(a<70)b=“pass”elseif(a<80)b=“general”elseif(a<90)b=“good”elseb=“excellent”如圖（a）所示以5，15，40，30，10為權(quán)構(gòu)造哈夫曼樹如圖(b)所示，將判定框中的條件分開，可得到(c)70<=a<8080<=a<9060<=a<70a<60

中等

良好

及格

優(yōu)良

不及格10000個分?jǐn)?shù)a<60a<70a<80a<90不及格

及格

中等

優(yōu)良

良好31500次a<80a<90a<70a<60不及格

及格

中等

優(yōu)良

良好22000次(a)(b)(c)YNYYYYYYYYYYYNNNNNNNNNNN最優(yōu)編碼（Huffman編碼）問題的提出：編碼（如電報(bào)碼）等長編碼不等長編碼特點(diǎn):編碼長度譯碼速度傳輸速度前綴碼與非前綴碼例：CASTCATSSATATATASAD={A,C,S,T}按出現(xiàn)的頻率w={7,2,4,5}SC18