數(shù)據(jù)結(jié)構(gòu)第06章 樹

1、第六章 樹v教學(xué)目的與要求教學(xué)目的與要求v本章目的是介紹二叉樹的定義、性質(zhì)、存儲結(jié)構(gòu)、二叉樹遍歷、線索化，樹的定義、存儲結(jié)構(gòu)、樹遍歷，樹和森林與二叉樹的轉(zhuǎn)換，哈夫曼樹和哈夫曼編碼等內(nèi)容。要求在熟悉這些內(nèi)容的基礎(chǔ)上，重點掌握二叉樹的遍歷算法及其有關(guān)應(yīng)用。 v重點和難點重點和難點v重點掌握二叉樹的遍歷算法及其有關(guān)應(yīng)用。難點是使用本章所學(xué)到的有關(guān)知識設(shè)計出有效算法，解決與樹或二叉樹有關(guān)的應(yīng)用問題。 樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)v6.1 樹的定義定義v定義：樹(tree)是n(n0)個結(jié)點的有限集T，其中：有且僅有一個特定的結(jié)點，稱為樹的根(root)當(dāng)n1時，其余結(jié)點可分

2、為m(m0)個互不相交的有限集T1,T2,Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)v特點：樹中至少有一個結(jié)點根樹中各子樹是互不相交的集合A只有根結(jié)點的樹ABCDEFGHIJKLM有子樹的樹根子樹基本術(shù)語v結(jié)點(node)表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支v結(jié)點的度(degree)結(jié)點擁有的子樹數(shù)v葉子(leaf)度為0的結(jié)點v孩子(child)結(jié)點子樹的根稱為該結(jié)點的孩子v雙親(parents)孩子結(jié)點的上層結(jié)點叫該結(jié)點的v兄弟(sibling)同一雙親的孩子v樹的度一棵樹中最大的結(jié)點度數(shù)v結(jié)點的層次(level)從根結(jié)點算起，根為第一層，它的孩子為第二

3、層v深度(depth)樹中結(jié)點的最大層次數(shù)v森林(forest)m(m0)棵互不相交的樹的集合ABCDEFGHIJKLM結(jié)點A的度：3結(jié)點B的度：2結(jié)點M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點A的孩子：B，C，D結(jié)點B的孩子：E，F(xiàn)結(jié)點I的雙親：D結(jié)點L的雙親：E結(jié)點B，C，D為兄弟結(jié)點K，L為兄弟樹的度：3結(jié)點A的層次：1結(jié)點M的層次：4樹的深度：4結(jié)點F，G為堂兄弟結(jié)點A是結(jié)點F，G的祖先v6.2 二叉樹定義v定義：二叉樹是n(n0)個結(jié)點的有限集，它或為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成v特點每個結(jié)點至多有二棵子樹(即不存在度大于2的結(jié)

4、點)二叉樹的子樹有左、右之分，且其次序不能任意顛倒v基本形態(tài)A只有根結(jié)點的二叉樹空二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空二叉樹性質(zhì)v性質(zhì)1：) 1(21iii個結(jié)點層上至多有在二叉樹的第證明：用歸納法證明之 i=1時，只有一個根結(jié)點， 是對的 假設(shè)對所有j(1j1，則ki的雙親編號為；若i1，則ki是根結(jié)點，無雙親；v若2in，則ki的左孩子編號為2i；否則，ki無左孩子。即完全 二叉樹中編號i的結(jié)點必定是葉子結(jié)點。v若2i+1n，則ki的右孩子編號為2i+1。v若i為奇數(shù)且不為1，則ki的左兄弟編號為i-1。v若i為偶數(shù)且小于n，則ki的右兄弟編號為i+1。 6.3 二叉樹

5、的遍歷v二叉樹的遍歷是指沿著某條搜索路線，對樹中每個結(jié)點做一次且僅一次訪問。 v方法按層次遍歷：從上到下、從左到右訪問各結(jié)點先序遍歷：先訪問根結(jié)點,然后分別先序遍歷左子樹、右子樹中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點，最后中序遍歷右子樹后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點DLRLDR、LRD、DLRRDL、RLD、DRLADBCD L RAD L RD L RBDCD L R先序遍歷序列：A B D C先序遍歷:ADBCL D RBL D RL D RADCL D R中序遍歷序列：B D A C中序遍歷:ADBC L R DL R DL R DADCL R D后序遍歷序列： D

6、B C A后序遍歷:B-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：層次遍歷：- + a * b - c d / e f-+a*b-cd/ef- +a *b - c d/e f-+a*b-c d/e f-+/a*b-efcd-+/a*b-efcd-+/a*b-efcd-+/a*b-efcd-+/a*b-efcda+b*c-d-e/fv自然語言描述的遍歷算法v（1）先序遍歷算法v若二叉樹非空，則：v訪問根結(jié)點；v先序遍歷左子樹；v先序遍歷右子樹。 vC語言描述的遍歷算法（以先序遍歷算法為例）v void preorder(Bintree T)v/先序遍歷T所指二叉樹，算法中、是為說明方便額

7、外添加的v if(T) v printf(%c,T-data); /這里用printf語句代表一般訪問vpreorder(T-lchild); vpreorder(T-rchild);v/preorderv中序遍歷算法v若二叉樹非空，則：v中序遍歷左子樹；v訪問根結(jié)點；v中序遍歷右子樹。v中序遍歷算法將語句、互換，函數(shù)名作對應(yīng)改變即可 v后序遍歷算法v若二叉樹非空，則：v后序遍歷左子樹；v后序遍歷右子樹；v訪問根結(jié)點。 v后序遍歷算法將語句移至語句之后即可。v可以看出，二叉樹是一個遞歸定義，上述算法也是遞歸算法，若用非遞歸算法，則應(yīng)引入工作棧方可。遍歷過程訪問結(jié)點所得結(jié)點序列稱為遍歷序列，即先

8、序遍歷序列、中序遍歷序列、后序遍歷序列。遍歷算法的時間復(fù)雜度為O(n)。 void preorder(Bintree T) if(T) printf(%c,T-data); preorder(T-lchild); preorder(T-rchild);/preorder主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空

9、返回T右是空返回pre(T R);先序序列：A B D C算法遞歸算法遍歷算法的應(yīng)用 v遍歷是二叉樹的最重要的運算之一，它是二叉樹上其它運算的基礎(chǔ)。能夠訪問到每一個結(jié)點，就可以對結(jié)點做各種操作。因此，許多涉及二叉樹的操作都是二叉樹遍歷算法的直接應(yīng)用或變形。例如：統(tǒng)計二叉樹中某類結(jié)點的個數(shù)；將二叉樹中各結(jié)點的左、右子樹互換；求某個結(jié)點的位置；建立二叉樹；求二叉樹的高；釋放二叉樹中所有結(jié)點；建立線索二叉樹等。 創(chuàng)建根創(chuàng)建左子樹創(chuàng)建右子樹訪問根訪問左子樹訪問右子樹A B C D E G F A B C D E G FGABDEFCABCDEFG例 1：建立二叉樹v void creatbintree

10、(Bintree *T)v /先序建立二叉樹v char ch;v if(chgetchar() )v*TNULL;v else v*T(Bintnode *)malloc(sizeof(Bintnode); /申請新結(jié)點v(*T)-datach; /新結(jié)點數(shù)據(jù)域賦值v creatbintree(&(*T)-lchild); /建立左子樹v creatbintree(&(*T)-rchild); /建立右子樹vv v【分析】該算法以先序遍歷算法為基礎(chǔ)，先序遍歷算法中訪問根結(jié)點在這里體現(xiàn)為構(gòu)造新結(jié)點。算法中的形式參數(shù)T是二級指針，在調(diào)用時，實參應(yīng)為根指針的地址。輸入數(shù)據(jù)應(yīng)是先序遍

11、歷序列并加入虛結(jié)點已示空指針的位置。算法的時間復(fù)雜度與先序遍歷算法相同，為O(n)。該算法也可以通過中序、后序遍歷算法實現(xiàn)。 ABCDEFG例 2：求二叉樹的高(深度)12345樹的深度為其左、右子樹中最深的子樹加1，空樹的深度為0訪問左子樹訪問右子樹訪問根求左子樹的高求右子樹的高求樹的高vint depbintree(Bintree T)v/求T所指二叉樹的高(深度)v int depl,depr, dep;v if(TNULL) dep0;/空二叉樹的高為0v else vdepl creatbintree(T-lchild); /遞歸調(diào)用求左子樹的高(深度)vdeprcreatbintr

12、ee(T-rchild); /遞歸調(diào)用求右子樹的高(深度)vdepdepldepr?depl+1:depr+1;/左子樹、右子樹高最大值加1v return(dep); vv【分析】該算法可以看成是后序遍歷算法的變形。若二叉樹為空，則高為0；否則，遞歸調(diào)用求左、右子樹的高，（可以看成是后序遍歷左、右子樹），最后，在左子樹、右子樹高最大值上加1作為二叉樹的高（可以看成是遍歷算法中訪問根結(jié)點操作）。算法中的形式參數(shù)T是一級指針，算法的時間復(fù)雜度為O(n)。 例 3：將二叉樹中各結(jié)點的左、右子樹互換ABCDEFGABCDEFG將樹的左、右子樹互換將左子樹的左、右子樹互換將右子樹的左、右子樹互換訪問根

13、訪問左子樹訪問右子樹 A B C D E F G vvoid swaptree (Bintree T)v/T所指二叉樹各結(jié)點的左、右子樹互換v Bintnode *p;v if(T) pT-lchild;v T-lchildT-rchild;v T-rchildp;v swaptree(T-lchild); v swaptree(T-rchild);v/ swaptreev【分析】該算法實際上就是先序遍歷算法，訪問根結(jié)點在該算法中體現(xiàn)為交換根結(jié)點左、右指針。64 線索二叉樹線索二叉樹v對二叉樹的遍歷，可以得到相應(yīng)的遍歷序列，其是一個線性序列。從這一角度看對二叉樹的遍歷實際上是一個把非線性結(jié)構(gòu)轉(zhuǎn)

14、化為線性結(jié)構(gòu)操作。利用這一點，我們可以存儲結(jié)點遍歷序列的前趨和后繼結(jié)點的地址（指針），使得二叉樹的遍歷由在非線性結(jié)構(gòu)上操作轉(zhuǎn)化為線性結(jié)構(gòu)操作。線索二叉樹就是為了實現(xiàn)上述目的而引出的一個概念。v在n個結(jié)點的二叉鏈表中，存在n+1個空指針域，利用這些空指針域，存放結(jié)點的某種遍歷序列的前趨或后繼結(jié)點的指針，這種附加的指針稱為線索，帶有線索的二叉樹稱為線索二叉樹，帶有線索的二叉鏈表稱為線索鏈表。使二叉樹成為線索二叉樹的過程稱為線索化。v定義：前驅(qū)與后繼：在二叉樹的先序、中序或后序遍歷序列中兩個相鄰的結(jié)點互稱為線索：指向前驅(qū)或后繼結(jié)點的指針稱為線索二叉樹：加上線索的二叉鏈表表示的二叉樹叫線索化：對二叉樹

15、按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫v實現(xiàn) 0：lchild（rchild）指向結(jié)點的左(右)孩子的指針 ltag(rtag) 1：lchild（rchild）是指向結(jié)點的前趨(后繼)的線索typedef enum link,thread pointtag; /枚舉常量枚舉常量link,thread的值為的值為0和和1 typedef struct node Datatype data; pointtag ltag,rtag;/左右標(biāo)志左右標(biāo)志 struct node *lchild, *rchild; Binthrnode; typedef Binthrnode *Binthrtree;

16、 lchild ltag data rtag rchildABCDE A B D C ET先序序列：ABCDE先序線索二叉樹00001111 11ABCDE A B D C ET中序序列：BCAED中序線索二叉樹0000111111ABCDE A B D C ET后序序列：CBEDA后序線索二叉樹0000111111ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED帶頭結(jié)點的中序線索二叉樹 0 1頭結(jié)點：ltag=0, lchild指向根結(jié)點rtag=1, rchild指向遍歷序列中最后一個結(jié)點遍歷序列中第一個結(jié)點的lchild域和最后一個結(jié)點的rc

17、hild域都指向頭結(jié)點 A B D C ET中序序列：BCAED中序線索二叉樹0000111111v算法按中序線索化二叉樹ABCDE輸出: B C A E D A B D C Et 0 11111110000Binthrnode *preNULL; void inthread(Binthrtree p)/ if (p) inthread( p-lchild); p-ltagp-lchild ? link:thread; p-rtagp-rchild ? link:thread; if (pre) if (pre-rtagthread) pre-rchildp; if (pre-ltagthre

18、ad) p-lchildpre; inthread( p-rchild);/ endif /inthreadv【分析】對二叉樹進(jìn)行線索化就是進(jìn)行遍歷。中序線索化左子樹，就是中序遍歷左子樹；中序線索化右子樹，就是中序遍歷右子樹；對當(dāng)前結(jié)點的標(biāo)志域處理和線索化可理解為對根結(jié)點的訪問。同理，只需修改先序遍歷，后序遍歷算法中訪問根結(jié)點操作，就不難得到先序線索化和后序線索化算法。算法的時間復(fù)雜度為O(n)。在中序線索二叉樹中找結(jié)點后繼的方法：（1）若rtag=1, 則rchild域直接指向其后繼（2）若rtag=0, 則結(jié)點的后繼應(yīng)是其右子樹的左鏈尾（ltag=1)的結(jié)點在中序線索二叉樹中找結(jié)點前驅(qū)的方

19、法：（1）若lt=1, 則lc域直接指向其前驅(qū)（2）若lt=0, 則結(jié)點的前驅(qū)應(yīng)是其左子樹的右鏈尾（rt=1)的結(jié)點ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED帶頭結(jié)點的中序線索二叉樹 0 1v求中序后繼結(jié)點的算法求中序后繼結(jié)點的算法v Binthrnode *inordsucc(Binthrnode *p)v/在中序線索二叉樹上找結(jié)點*p的中序后繼v Binthrnode *q;v if (p-rtagthread)v return p-rchild; /*p右子樹為空，則右孩子域所指結(jié)點即為其直接后繼v else v qp-rchild;

20、/q指向右子樹v whild (q-ltaglink) v qq-lchild; /查找右子樹上最左下的結(jié)點v return q;v v【分析】在中序線索二叉樹上找結(jié)點*p的中序后繼，若*p右標(biāo)志為線索說明右子樹為空，則右孩子域所指結(jié)點即為其直接后繼；否則，*p的右子樹上最左下的結(jié)點為其直接后繼。v算法時間復(fù)雜度主要體現(xiàn)在查找*p右子樹最左下結(jié)點的過程,這一過程是沿左孩子指針向下查找的過程，所以，算法時間復(fù)雜度不超過樹的高度h,即O(n)。v遍歷線索二叉樹（與中序線索二叉樹為例）遍歷線索二叉樹（與中序線索二叉樹為例）v void Trainordthrtree( Binthrtree p)v/

21、中序遍歷線索二叉樹vif (p) v while p-ltaglink)v pp-lchild; /查找開始結(jié)點v do v printf(%c,p-data);v pinordsucc(p);v while (p); /循環(huán)輸出當(dāng)前結(jié)點，并求其后繼結(jié)點直到p為空v v65 樹和森林樹和森林v1樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)v樹的存儲結(jié)構(gòu)通常采用下列三種方式：v雙親鏈表表示法v孩子鏈表表示法及帶雙親的孩子雙親鏈表表示法v孩子兄弟鏈表表示法v樹、森林與二叉樹的轉(zhuǎn)換v雙親表示法實現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點，每個結(jié)點含兩個域：v數(shù)據(jù)域：存放結(jié)點本身信息v雙親域：指示本結(jié)點的雙親結(jié)點在數(shù)組中位置特點：找雙

22、親容易，找孩子難typedef struct node datatype data; int parent;JD;JD tM;abcdefhgiacdefghib012235551096012345789dataparent0號單元不用或存結(jié)點個數(shù)如何找孩子結(jié)點v孩子表示法多重鏈表：每個結(jié)點有多個指針域，分別指向其子樹的根v結(jié)點同構(gòu)：結(jié)點的指針個數(shù)相等，為樹的度Dv結(jié)點不同構(gòu)：結(jié)點指針個數(shù)不等，為該結(jié)點的度ddata child1 child2 . childDdata degree child1 child2 . childd孩子鏈表：每個結(jié)點的孩子結(jié)點用單鏈表存儲，再用含n個元素的結(jié)構(gòu)數(shù)組

23、指向每個孩子鏈表孩子結(jié)點：typedef struct node int child; /該結(jié)點在表頭數(shù)組中下標(biāo) struct node *next; /指向下一孩子結(jié)點 JD;表頭結(jié)點：typedef struct tnode datatype data; /數(shù)據(jù)域 struct node *fc; /指向第一個孩子結(jié)點 TD; TD tM; /t0不用abcdefhgi6012345789acdefghibdatafc 2 3 4 5 9 7 8 6如何找雙親結(jié)點帶雙親的孩子鏈表612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parenta

24、bcdefhgiv孩子兄弟表示法（二叉樹表示法）實現(xiàn)：用二叉鏈表作樹的存儲結(jié)構(gòu)，鏈表中每個結(jié)點的兩個指針域分別指向其第一個孩子結(jié)點和下一個兄弟結(jié)點特點v操作容易v破壞了樹的層次typedef struct node datatype data; struct node *fch, *nsib;JD;abcdefhgi a b c d e f g h i樹與二叉樹轉(zhuǎn)換ACBED樹ABCDE二叉樹 A B C D E A B C D E A B C D E 對應(yīng)存儲存儲解釋解釋v將樹轉(zhuǎn)換成二叉樹加線：在兄弟之間加一連線抹線：對每個結(jié)點，除了其左孩子外，去除其與其余孩子之間的關(guān)系旋轉(zhuǎn)：以樹的根結(jié)點為

25、軸心，將整樹順時針轉(zhuǎn)45ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹轉(zhuǎn)換成的二叉樹其右子樹一定為空v將二叉樹轉(zhuǎn)換成樹加線：若p結(jié)點是雙親結(jié)點的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用線連起來抹線：抹掉原二叉樹中雙親與右孩子之間的連線調(diào)整：將結(jié)點按層次排列，形成樹結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIv森林轉(zhuǎn)換成二叉樹將各棵樹分別轉(zhuǎn)換成二叉樹將每棵樹的根結(jié)點用線相連以第一棵樹根結(jié)點為二叉樹的根，再以根結(jié)點為軸心，順時針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)ABCDEFGH

26、IJABCDEFGHIJABCDEFGHIJABCDEFGHIJv二叉樹轉(zhuǎn)換成森林抹線：將二叉樹中根結(jié)點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹還原：將孤立的二叉樹還原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJv6.4 樹和森林的遍歷樹的遍歷v遍歷按一定規(guī)律走遍樹的各個頂點，且使每一頂點僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結(jié)點的一個線性排列v常用方法先根（序）遍歷：先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點按層次遍歷：先訪問第一層上的結(jié)

27、點，然后依次遍歷第二層，第n層的結(jié)點v森林的遍歷森林的遍歷v與樹的遍歷相類似，森林的遍歷有前序遍歷森林和后序遍歷森林兩種方法。v前序遍歷森林算法：v 若森林非空，則v訪問森林中第一棵樹的根結(jié)點；v前序遍歷森林第一棵樹的根結(jié)點的各棵子樹所構(gòu)成的森林；v前序遍歷森林除第一棵樹外剩余各棵樹所構(gòu)成的森林。v后序遍歷森林算法：v 若森林非空，則v 后序遍歷森林第一棵樹的根結(jié)點的各棵子樹所構(gòu)成的森林；v 訪問森林中第一棵樹的根結(jié)點；v 后遍歷森林除第一棵樹外剩余各棵樹所構(gòu)成的森林。v重要結(jié)論：先根遍歷一棵樹等價于先序遍歷對應(yīng)二叉樹，后根遍歷一棵樹等價于中序遍歷對應(yīng)二叉樹；前序遍歷森林等價于先序遍歷對應(yīng)二叉

28、樹，后序遍歷森林等價于中序遍歷對應(yīng)二叉樹。由此可知，樹和森林的前序遍歷和后序遍歷可用對應(yīng)二叉樹的先序先序遍歷和中序遍歷算法來實現(xiàn)。v6.6 二叉樹的應(yīng)用哈夫曼樹(Huffman)帶權(quán)路徑長度最短的樹v定義路徑：從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點間的路徑長度：路徑上的分支數(shù)樹的路徑長度：從樹根到每一個結(jié)點的路徑長度之和樹的帶權(quán)路徑長度：樹中所有帶權(quán)結(jié)點的路徑長度之和結(jié)點到根的路徑長度權(quán)值其中：記作：kknkkklwlwwpl1Huffman樹設(shè)有n個權(quán)值w1,w2,wn，構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉子的權(quán)值為wi,則wpl最小的二叉樹叫例 有4個結(jié)點，權(quán)值分別為7，5，

29、2，4，構(gòu)造有4個葉子結(jié)點的二叉樹abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35nkKKLWWPL1v構(gòu)造Huffman樹的方法Huffman算法構(gòu)造Huffman樹步驟v根據(jù)給定的n個權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點的二叉樹，令起權(quán)值為wjv在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和v在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中v重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100Huffman算法實現(xiàn)Ch5_8.cv一棵有n個葉子結(jié)點的Huffman樹