數(shù)據(jù)結(jié)構(gòu)-第5章-樹課件

1、主要教學(xué)目標(biāo)：了解樹和森林的概念和性質(zhì)；熟練掌握二叉樹的結(jié)構(gòu)特性及二叉樹的遍歷方法；掌握樹和二叉樹的轉(zhuǎn)換。了解二叉樹的線索化，掌握中序線索化二叉樹上求前驅(qū)和后繼的方法。教學(xué)方法及教學(xué)手段：理論講授與上機實踐相結(jié)合教學(xué)重點及難點：二叉樹的性質(zhì)，建樹、遍歷等基本算法 第五章 樹 樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)5.1 樹的定義定義定義：樹(tree)是n(n0)個結(jié)點的有限集T，其中：有且僅有一個特定的結(jié)點，稱為樹的根(root)當(dāng)n1時，其余結(jié)點可分為m(m0)個互不相交的有限集T1,T2,Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)特點：樹中至少有

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

3、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的祖先結(jié)點A的度：結(jié)點C的度：結(jié)點K的度：葉子：結(jié)點D的孩子：結(jié)點E的孩子：結(jié)點H的雙親：結(jié)點F的雙親：結(jié)點 為兄弟樹的度：結(jié)點A的層次：1結(jié)點N的層次：4樹的深度：結(jié)點為堂兄弟結(jié)點是結(jié)點F，G的祖先ABCDEFGHIJKLMNO5.2 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)樹的標(biāo)準(zhǔn)形式存貯結(jié)構(gòu)實現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點，每個結(jié)點含兩個域：數(shù)據(jù)域：存放結(jié)點本

4、身信息指針域：指向本結(jié)點的孩子結(jié)點data child1,child2,childmabcdefhgiabdcefghiabdcefghi樹的逆形式存貯結(jié)構(gòu)實現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點，每個結(jié)點含兩個域：數(shù)據(jù)域：存放結(jié)點本身信息指針域：指向本結(jié)點的雙親結(jié)點 data parentabcdefhgi a b c g h i d e f樹的擴充標(biāo)準(zhǔn)形式存貯結(jié)構(gòu)實現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點，每個結(jié)點含兩個域：數(shù)據(jù)域：存放結(jié)點本身信息指針域：指向本結(jié)點的雙親結(jié)點和孩子結(jié)點data child1,child2,childm parentabcdefhgibacghidef5.3 用樹表示集合例如 0

5、,1,2,3,4,5,6,7,8,9分成三個互不相交的集合：S0=0,6,7,8,S1=1,4,9,S2=2,3,5用樹表示集合，如圖：0678S0149S1235S2兩個集合的并集：先用樹表示集合，再將一棵樹作為另一棵樹的子集。UNION（ S0， S1 ）067814914906785.4 樹的遍歷樹的遍歷遍歷按一定規(guī)律走遍樹的各個頂點，且使每一頂點僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結(jié)點的一個線性排列常用方法先根（序）遍歷：先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點按層次遍歷：先訪問第一層上的結(jié)點，然后依次遍歷

6、第二層，第n層的結(jié)點葉子結(jié)點：從左到右訪問葉子ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO葉子遍歷：EIGHGCJKNOM5.5 樹的線性表示層號表示和括號表示層號表示：按前序?qū)懗鰳渲腥拷Y(jié)點，并在結(jié)點之前帶上結(jié)點的層號。若k是樹中的一個結(jié)點，有一個lev(k),滿足以下兩個條件：1、k是k的子結(jié)點，則lev(k)lev(k)2、k,k”同是k的子結(jié)點，則lev(k)=lev(k”)則稱lev(k)是結(jié)點k的層號。abcdefhgi(0,a),(1,b),(2,d),(2,e),(3,g)

7、,(3,h),(3,i),(1,c),(2,f)(10,a),(20,b),(30,d),(30,e),(40,g),(40,h),(40,i),(15,c),(25,f)5.5 樹的線性表示層號表示和括號表示括號表示 若T由根結(jié)點A和子樹T0，T1，,Tm-1組成，則樹T的括號表示為 A（T0的括號表示,T1的括號表示,Tm-1的括號表示）abcdefhgia(b(d,e(g,h,i),c(f)5.6 二叉樹定義定義：二叉樹是n(n0)個結(jié)點的有限集，它或為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成特點每個結(jié)點至多有二棵子樹(即不存在度大于2的結(jié)點)二叉

8、樹的子樹有左、右之分，且其次序不能任意顛倒基本形態(tài)A只有根結(jié)點的二叉樹空二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空二叉樹性質(zhì)性質(zhì)1：性質(zhì)2：深度為k的二叉樹至多有 個結(jié)點(k1)性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1滿二叉樹：順序二叉樹定義：深度為k，有n個結(jié)點的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱為特點葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)對任一結(jié)點，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為l 或l+1特點：每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)123114589121

9、3671014151231145891267101234567123456性質(zhì)5：如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號，則對任一結(jié)點i(1in)，有： (1) 如果i=1，則結(jié)點i是二叉樹的根，無雙親；如果i1，則其雙親是i/2 (2) 如果2in，則結(jié)點i無左孩子；如果2in，則其左孩子是2i (3) 如果2i+1n，則結(jié)點i無右孩子；如果2i+1n，則其右孩子是2i+1性質(zhì)4：樹與二叉樹轉(zhuǎn)換ACBED樹ABCDE二叉樹 A B C D E A B C D E A B C D E 對應(yīng)存儲存儲解釋解釋將樹轉(zhuǎn)換成二叉樹加線：在兄弟之間加一連線抹線：對每個結(jié)點，除了其左孩子外，去除其

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

11、轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉樹轉(zhuǎn)換成森林抹線：將二叉樹中根結(jié)點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹還原：將孤立的二叉樹還原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ小結(jié)：本節(jié)講述了四個內(nèi)容：（1）樹轉(zhuǎn)換成二叉樹（2）二叉樹轉(zhuǎn)換成樹（3）樹轉(zhuǎn)換成二叉樹（4）樹轉(zhuǎn)換成二叉樹ABCDFHIG先序:中序:后序:ABDEFGHIC5.7 二叉樹的遍歷方法先序遍歷：先訪問根結(jié)點,然后分別先序遍歷左子樹、右子樹中序遍歷：先中序遍歷左子樹，然后訪問根

12、結(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 B C A后序遍歷:B-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef算法遞歸算法void preorder(JD *bt) if(bt!=NUL

13、L) printf(%dt,bt-data); preorder(bt-lchild); preorder(bt-rchild); 主程序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左是空返回T右是空返回pre(T R);先序序列：A B D C非遞歸算法ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDE

14、FGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B訪問：C(4)pABCDEFGiP-A訪問：C B(5)ABCDEFGiP-AP-D訪問：C Bp(6)ABCDEFGiP-AP-DP-E訪問：C Bp(7)ABCDEFGiP-AP-D訪問：C B Ep(8)ABCDEFGiP-AP-DP-G訪問：C B EP=NULL(9)ABCDEFGiP-A訪問：C B E G Dp(11)ABCDEFGiP-AP-F訪問：C B E G Dp(12)ABCDEFGiP-AP-D訪問：C B E Gp(10)ABCDEFGiP-A訪問：C B E G D Fp=NULL(13)AB

15、CDEFGi訪問：C B E G D F Ap(14)ABCDEFGi訪問：C B E G D F Ap=NULL(15)遍歷算法應(yīng)用按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為： A B C D E G F 求二叉樹深度算法ABCDEFG A B C D E F G 統(tǒng)計二叉樹中葉子結(jié)點個數(shù)算法中序遍歷序列：B C A E D G H F I先序遍歷序列：A B C D E F G H I5.8 二叉樹的順序存儲按層次序的存貯方式按前序的存貯方式附加左標(biāo)志位和右指針ltag=0,結(jié)點k后面的結(jié)點是k的左子結(jié)點ltag=1,結(jié)點k無左子結(jié)點rchild=-1,無右子結(jié)點rchild=編號

16、，有右子結(jié)點ltag data rchild ABDFCEGH01234567ltagdatarchild0A41B20D-11F-10C-10E-11G71H-1附加兩個標(biāo)志位ltag data rtag ltag=0,結(jié)點k后面的結(jié)點是k的左子結(jié)點ltag=1,結(jié)點k無左子結(jié)點rtag=0,結(jié)點k后面的結(jié)點是k的右子結(jié)點rtag=1,結(jié)點k無右子結(jié)點ABDFCEGH01234567ltagdatartag0A01B00D11F10C10E11G01H15.9 穿線樹和穿線排序定義：前驅(qū)與后繼：在二叉樹的先序、中序或后序遍歷序列中兩個相鄰的結(jié)點互稱為線索：指向前驅(qū)或后繼結(jié)點的指針稱為穿線樹：

17、加上線索的二叉鏈表表示的二叉樹叫線索化：對二叉樹按某種遍歷次序使其變?yōu)榇┚€樹的過程叫實現(xiàn)在有n個結(jié)點的二叉鏈表中必定有n+1個空鏈域在線索二叉樹的結(jié)點中增加兩個標(biāo)志域ltag :若 ltag =0, lchild 域指向左孩子；若 ltag=1, lchild域指向其前驅(qū)rtag :若 rtag =0, rchild域指向右孩子；若 rtag=1, rchild域指向其后繼ABCDE A B D C ET先序序列：ABCDE先序線索二叉樹0000111111lchild ltag data rtag rchildABCDE A B D C ET中序序列：BCAED中序線索二叉樹00001111

18、11ABCDE 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é)點：lt=0, lc指向根結(jié)點rt=1, rc指向遍歷序列中最后一個結(jié)點遍歷序列中第一個結(jié)點的lc域和最后一個結(jié)點的rc域都指向頭結(jié)點 A B D C ET中序序列：BCAED中序線索二叉樹0000111111二叉排序樹定義：二叉排序樹或是一棵空樹，或是具有下列性質(zhì)的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值若它的右子樹不空，則右子樹上所有結(jié)點的值均大

19、于或等于它的根結(jié)點的值它的左、右子樹也分別為二叉排序樹二叉排序樹的插入插入原則：若二叉排序樹為空，則插入結(jié)點應(yīng)為新的根結(jié)點；否則，繼續(xù)在其左、右子樹上查找，直至某個葉子結(jié)點的左子樹或右子樹為空為止，則插入結(jié)點應(yīng)為該葉子結(jié)點的左孩子或右孩子二叉排序樹生成：從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，可生成一棵二叉排序樹5.5 二叉樹的應(yīng)用哈夫曼樹(Huffman)帶權(quán)路徑長度最短的樹定義路徑：從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點間的路徑長度：路徑上的分支數(shù)樹的路徑長度：從樹根到每一個結(jié)點的路徑長度之和樹的帶權(quán)路徑長度：樹中所有帶權(quán)結(jié)點的路徑長度之和Huffman樹設(shè)有n個權(quán)值w1,

20、w2,wn，構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉子的權(quán)值為wi,則wpl最小的二叉樹叫例 有4個結(jié)點，權(quán)值分別為7，5，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=35構(gòu)造Huffman樹的方法Huffman算法構(gòu)造Huffman樹步驟根據(jù)給定的n個權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點的二叉樹，令起權(quán)值為wj在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和在森林

21、中刪除這兩棵樹，同時將新得到的二叉樹加入森林中重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例 w=5, 29, 7, 8, 14, 23, 3, 1151429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100Huffman算法實現(xiàn)Ch5_8.c一棵有n個葉子結(jié)點的Huffma

22、n樹有2n-1個結(jié)點采用順序存儲結(jié)構(gòu)一維結(jié)構(gòu)數(shù)組結(jié)點類型定義typedef struct int data; int pa,lc,rc;JD;lc data rc pa1 2 3 4 5 6 70 0 0 0 0 0 07 5 2 4 0 0 00 0 0 0 0 0 00 0 0 0 0 0 0(1)lc data rc pa1 2 3 4 5 6 70 0 0 0 3 0 07 5 2 4 6 0 00 0 0 0 4 0 00 0 5 5 0 0 0kx1=3,x2=4m1=2,m2=4(2)lc data rc pa1 2 3 4 5 6 70 0 0 0 3 2 07 5 2 4 6 11 00 0 0 0 4 5 00 6 5 5 6 0 0kx1=2,x2=5m1=5,m2=6(3)lc data rc pa1 2 3 4 5 6 70 0 0 0 3 2 17 5