《數(shù)據(jù)結(jié)構(gòu)-樹(shù)-嚴(yán)蔚敏版.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)-樹(shù)-嚴(yán)蔚敏版.ppt（78頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第五章 樹(shù),樹(shù)是一類(lèi)重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu) 5.1 樹(shù)的定義 定義 定義：樹(shù)(tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集T，其中： 有且僅有一個(gè)特定的結(jié)點(diǎn)，稱(chēng)為樹(shù)的根(root) 當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集T1,T2,Tm，其中每一個(gè)集合本身又是一棵樹(shù)，稱(chēng)為根的子樹(shù)(subtree) 特點(diǎn)： 樹(shù)中至少有一個(gè)結(jié)點(diǎn)根 樹(shù)中各子樹(shù)是互不相交的集合,根,子樹(shù),基本術(shù)語(yǔ) 結(jié)點(diǎn)(node)表示樹(shù)中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的分支 結(jié)點(diǎn)的度(degree)結(jié)點(diǎn)擁有的子樹(shù)數(shù) 葉子(leaf)度為0的結(jié)點(diǎn) 孩子(child)結(jié)點(diǎn)子樹(shù)的根稱(chēng)為該結(jié)點(diǎn)的孩子 雙親

2、(parents)孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的 兄弟(sibling)同一雙親的孩子 樹(shù)的度一棵樹(shù)中最大的結(jié)點(diǎn)度數(shù) 結(jié)點(diǎn)的層次(level)從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層 深度(depth)樹(shù)中結(jié)點(diǎn)的最大層次數(shù) 森林(forest)m(m0)棵互不相交的樹(shù)的集合,結(jié)點(diǎn)A的度：3 結(jié)點(diǎn)B的度：2 結(jié)點(diǎn)M的度：0,葉子：K，L，F(xiàn)，G，M，I，J,結(jié)點(diǎn)A的孩子：B，C，D 結(jié)點(diǎn)B的孩子：E，F(xiàn),結(jié)點(diǎn)I的雙親：D 結(jié)點(diǎn)L的雙親：E,結(jié)點(diǎn)B，C，D為兄弟 結(jié)點(diǎn)K，L為兄弟,樹(shù)的度：3,結(jié)點(diǎn)A的層次：1 結(jié)點(diǎn)M的層次：4,樹(shù)的深度：4,結(jié)點(diǎn)F，G為堂兄弟 結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先,5.2 二

3、叉樹(shù) 定義 定義：二叉樹(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?shù)(n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱(chēng)為左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)構(gòu)成 特點(diǎn) 每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)(即不存在度大于2的結(jié)點(diǎn)) 二叉樹(shù)的子樹(shù)有左、右之分，且其次序不能任意顛倒 基本形態(tài),二叉樹(shù)性質(zhì) 性質(zhì)1：,證明：用歸納法證明之 i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)， 是對(duì)的 假設(shè)對(duì)所有j(1ji)命題成立，即第j層上至多有 個(gè)結(jié)點(diǎn) 那么，第i-1層至多有 個(gè)結(jié)點(diǎn) 又二叉樹(shù)每個(gè)結(jié)點(diǎn)的度至多為2 第i層上最大結(jié)點(diǎn)數(shù)是第i-1層的2倍，即 故命題得證,性質(zhì)2：深度為k的二叉樹(shù)至多有 個(gè)結(jié)點(diǎn)(k1),證明：由性質(zhì)1，可得深度為k 的二叉樹(shù)最大結(jié)

4、點(diǎn)數(shù)是,性質(zhì)3：對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1,證明：n1為二叉樹(shù)T中度為1的結(jié)點(diǎn)數(shù) 因?yàn)椋憾鏄?shù)中所有結(jié)點(diǎn)的度均小于或等于2 所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2 又二叉樹(shù)中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個(gè) 分支進(jìn)入 設(shè)B為分支總數(shù)，則n=B+1 又：分支由度為1和度為2的結(jié)點(diǎn)射出，B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1,幾種特殊形式的二叉樹(shù) 滿(mǎn)二叉樹(shù) 定義：,特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù) 完全二叉樹(shù) 定義：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從

5、1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱(chēng)為 特點(diǎn) 葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn) 對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為l 或l+1 性質(zhì) 性質(zhì)4：,性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1in)，有： (1) 如果i=1，則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i1，則其雙親是i/2 (2) 如果2in，則結(jié)點(diǎn)i無(wú)左孩子；如果2in，則其左孩子是2i (3) 如果2i+1n，則結(jié)點(diǎn)i無(wú)右孩子；如果2i+1n，則其右孩子是2i+1,5.3 樹(shù)的存儲(chǔ)結(jié)構(gòu) 樹(shù)的存儲(chǔ)結(jié)構(gòu) 雙親表示法 實(shí)現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹(shù)的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域： 數(shù)據(jù)域

6、：存放結(jié)點(diǎn)本身信息 雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置 特點(diǎn)：找雙親容易，找孩子難,typedef struct node datatype data; int parent; JD; JD tM;,0,1,2,2,3,5,5,5,1,0號(hào)單元不用或 存結(jié)點(diǎn)個(gè)數(shù),如何找孩子結(jié)點(diǎn),孩子表示法 多重鏈表：每個(gè)結(jié)點(diǎn)有多個(gè)指針域，分別指向其子樹(shù)的根 結(jié)點(diǎn)同構(gòu)：結(jié)點(diǎn)的指針個(gè)數(shù)相等，為樹(shù)的度D 結(jié)點(diǎn)不同構(gòu)：結(jié)點(diǎn)指針個(gè)數(shù)不等，為該結(jié)點(diǎn)的度d,孩子鏈表：每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈表存儲(chǔ)，再用含n個(gè)元素的結(jié)構(gòu)數(shù)組指向每個(gè)孩子鏈表,孩子結(jié)點(diǎn)：typedef struct node int child; /該結(jié)

7、點(diǎn)在表頭數(shù)組中下標(biāo) struct node *next; /指向下一孩子結(jié)點(diǎn) JD; 表頭結(jié)點(diǎn)：typedef struct tnode datatype data; /數(shù)據(jù)域 struct node *fc; /指向第一個(gè)孩子結(jié)點(diǎn) TD; TD tM; /t0不用,如何找雙親結(jié)點(diǎn),帶雙親的孩子鏈表,孩子兄弟表示法（二叉樹(shù)表示法） 實(shí)現(xiàn)：用二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn) 特點(diǎn) 操作容易 破壞了樹(shù)的層次,typedef struct node datatype data; struct node *fch, *nsib; JD;,二叉樹(shù)

8、的存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu) 實(shí)現(xiàn)：按滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹(shù)中的數(shù)據(jù)元素 特點(diǎn)： 結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中 浪費(fèi)空間，適于存滿(mǎn)二叉樹(shù)和完全二叉樹(shù),鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 二叉鏈表,typedef struct node datatype data; struct node *lchild, *rchild; JD;,在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域,三叉鏈表,typedef struct node datatype data; struct node *lchild, *rchild, *parent; JD;,樹(shù)與二叉樹(shù)轉(zhuǎn)換,將樹(shù)轉(zhuǎn)換成二叉樹(shù) 加線：在兄弟之間加一連線 抹線：

9、對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系 旋轉(zhuǎn)：以樹(shù)的根結(jié)點(diǎn)為軸心，將整樹(shù)順時(shí)針轉(zhuǎn)45,樹(shù)轉(zhuǎn)換成的二叉樹(shù)其右子樹(shù)一定為空,將二叉樹(shù)轉(zhuǎn)換成樹(shù) 加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用線連起來(lái) 抹線：抹掉原二叉樹(shù)中雙親與右孩子之間的連線 調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹(shù)結(jié)構(gòu),森林轉(zhuǎn)換成二叉樹(shù) 將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù) 將每棵樹(shù)的根結(jié)點(diǎn)用線相連 以第一棵樹(shù)根結(jié)點(diǎn)為二叉樹(shù)的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹(shù)型結(jié)構(gòu),二叉樹(shù)轉(zhuǎn)換成森林 抹線：將二叉樹(shù)中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之

10、變成孤立的二叉樹(shù) 還原：將孤立的二叉樹(shù)還原成樹(shù),5.4 樹(shù)和二叉樹(shù)的遍歷 樹(shù)的遍歷 遍歷按一定規(guī)律走遍樹(shù)的各個(gè)頂點(diǎn)，且使每一頂點(diǎn)僅被訪問(wèn)一次，即找一個(gè)完整而有規(guī)律的走法，以得到樹(shù)中所有結(jié)點(diǎn)的一個(gè)線性排列 常用方法 先根（序）遍歷：先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹(shù) 后根（序）遍歷：先依次后根遍歷每棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn) 按層次遍歷：先訪問(wèn)第一層上的結(jié)點(diǎn)，然后依次遍歷第二層，第n層的結(jié)點(diǎn),先序遍歷：,后序遍歷：,層次遍歷：,A,B,E,F,I,G,C,D,H,J,K,L,N,O,M,E,I,F,G,B,C,J,K,N,O,L,M,H,D,A,A,B,C,D,E,F,G,H,I,J,K

11、,L,M,N,O,二叉樹(shù)的遍歷 方法 先序遍歷：先訪問(wèn)根結(jié)點(diǎn),然后分別先序遍歷左子樹(shù)、右子樹(shù) 中序遍歷：先中序遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù) 后序遍歷：先后序遍歷左、右子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn) 按層次遍歷：從上到下、從左到右訪問(wèn)各結(jié)點(diǎn),D L R,先序遍歷序列：A B D C,先序遍歷:,L D R,中序遍歷序列：B D A C,中序遍歷:,L R D,后序遍歷序列： D B C A,后序遍歷:,先序遍歷：,中序遍歷：,后序遍歷：,層次遍歷：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,

12、a,*,b,-,c,d,/,e,f,算法 遞歸算法,Ch5_1.c,void preorder(JD *bt) if(bt!=NULL) printf(%dt,bt-data); preorder(bt-lchild); preorder(bt-rchild); ,返回,返回,返回,返回,A,C,B,D,返回,先序序列：A B D C,非遞歸算法,Ch5_4.c Ch5_40.C,后序遍歷非遞歸算法,遍歷算法應(yīng)用 按先序遍歷序列建立二叉樹(shù)的二叉鏈表，已知先序序列為： A B C D E G F ,求二叉樹(shù)深度算法,Ch5_5.c ch5_6.c,Ch5_1.c,統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)算法,5

13、.5 二叉樹(shù)的應(yīng)用 哈夫曼樹(shù)(Huffman)帶權(quán)路徑長(zhǎng)度最短的樹(shù) 定義 路徑：從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)間的 路徑長(zhǎng)度：路徑上的分支數(shù) 樹(shù)的路徑長(zhǎng)度：從樹(shù)根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和 樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有帶權(quán)結(jié)點(diǎn)的路徑長(zhǎng)度之和,Huffman樹(shù)設(shè)有n個(gè)權(quán)值w1,w2,wn，構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，每個(gè)葉子的權(quán)值為wi,則wpl最小的二叉樹(shù)叫,例 有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹(shù),WPL=7*2+5*2+2*2+4*2=36,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,構(gòu)造Hu

14、ffman樹(shù)的方法Huffman算法 構(gòu)造Huffman樹(shù)步驟 根據(jù)給定的n個(gè)權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹(shù)，令起權(quán)值為wj 在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作左右子樹(shù)，構(gòu)造一棵新的二叉樹(shù)，置新二叉樹(shù)根結(jié)點(diǎn)權(quán)值為其左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和 在森林中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入森林中 重復(fù)上述兩步，直到只含一棵樹(shù)為止，這棵樹(shù)即哈夫曼樹(shù),例 w=5, 29, 7, 8, 14, 23, 3, 11,Huffman算法實(shí)現(xiàn),Ch5_8.c,一棵有n個(gè)葉子結(jié)點(diǎn)的Huffman樹(shù)有2n-1個(gè)結(jié)點(diǎn) 采用順序存儲(chǔ)結(jié)構(gòu)一維結(jié)構(gòu)數(shù)組 結(jié)點(diǎn)類(lèi)型定義,typedef struct int

15、 data; int pa,lc,rc; JD;,Ch5_8.c,Huffman樹(shù)應(yīng)用 最佳判定樹(shù),Huffman編碼：數(shù)據(jù)通信用的二進(jìn)制編碼 思想：根據(jù)字符出現(xiàn)頻率編碼，使電文總長(zhǎng)最短 編碼：根據(jù)字符出現(xiàn)頻率構(gòu)造Huffman樹(shù)，然后將樹(shù)中結(jié)點(diǎn)引向其左孩子的分支標(biāo)“0”，引向其右孩子的分支標(biāo)“1”；每個(gè)字符的編碼即為從根到每個(gè)葉子的路徑上得到的0、1序列,例 要傳輸?shù)淖址?D=C,A,S,T, ; 字符出現(xiàn)頻率 w=2,4,2,3,3,T : 00 ; : 01 A : 10 C : 110 S : 111,譯碼：從Huffman樹(shù)根開(kāi)始，從待譯碼電文中逐位取碼。若編碼是“0”，則向左走；

16、若編碼是“1”，則向右走，一旦到達(dá)葉子結(jié)點(diǎn)，則譯出一個(gè)字符；再重新從根出發(fā)，直到電文結(jié)束,例 電文是CAS;CAT;SAT;AT 其編碼 “11010111011101000011111000011000” 電文為“1101000” 譯文只能是“CAT”,線索二叉樹(shù) 定義： 前驅(qū)與后繼：在二叉樹(shù)的先序、中序或后序遍歷序列中兩個(gè)相鄰的結(jié)點(diǎn)互稱(chēng)為 線索：指向前驅(qū)或后繼結(jié)點(diǎn)的指針?lè)Q為 線索二叉樹(shù)：加上線索的二叉鏈表表示的二叉樹(shù)叫 線索化：對(duì)二叉樹(shù)按某種遍歷次序使其變?yōu)榫€索二叉樹(shù)的過(guò)程叫 實(shí)現(xiàn) 在有n個(gè)結(jié)點(diǎn)的二叉鏈表中必定有n+1個(gè)空鏈域 在線索二叉樹(shù)的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域 lt :若 lt =0,

17、lc 域指向左孩子；若 lt=1, lc域指向其前驅(qū) rt :若 rt =0, rc 域指向右孩子；若 rt=1, rc域指向其后繼 結(jié)點(diǎn)定義：,typedef struct node int data; int lt, rt; struct node *lc, *rc; JD;,0,0,0,0,1,1,1,1,1,1,0,0,0,0,1,1,1,1,1,1,0,0,0,0,1,1,1,1,1,1,頭結(jié)點(diǎn)： lt=0, lc指向根結(jié)點(diǎn) rt=1, rc指向遍歷序列中最后一個(gè)結(jié)點(diǎn) 遍歷序列中第一個(gè)結(jié)點(diǎn)的lc域和最后 一個(gè)結(jié)點(diǎn)的rc域都指向頭結(jié)點(diǎn),算法 按中序線索化二叉樹(shù),Ch5_20.c,JD

18、*zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL

19、); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹(shù),Ch5_20.c,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=

20、pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹(shù),Ch5_20.c,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=

21、p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹(shù),Ch5_20.c,i,輸出:B,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t;

22、 if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,1,算法 按中序線索化二叉樹(shù),Ch5_20.c,輸出:B,i,P-C,JD *zxxsh(JD *b

23、t) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t;

24、pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹(shù),Ch5_20.c,i,P-C,輸出:B,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=p

25、r; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹(shù),Ch5_20.c,i,輸出: B C,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL)

26、si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,1,算法 按中序線索化二叉樹(shù),Ch5_20.c,i,輸出: B C,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t

27、-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹(shù),Ch5_20.c,i,輸出: B C A,JD

28、 *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NUL

29、L); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,1,算法 按中序線索化二叉樹(shù),Ch5_20.c,i,輸出: B C A,P-D,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=

30、NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹(shù),Ch5_20.c,i,輸出: B C A,P-D,P-E,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt;

31、pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹(shù),Ch5_20.c,i,輸出: B C A,P-D,P-E,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0

32、; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t);

33、 ,算法 按中序線索化二叉樹(shù),Ch5_20.c,i,輸出: B C A E,P-D,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-

34、rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,1,算法 按中序線索化二叉樹(shù),Ch5_20.c,i,輸出: B C A E,P-D,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-

35、lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹(shù),Ch5_20.c,i,輸出: B C A E D,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1;

36、t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,1,算法 按中序線索化二叉樹(shù),Ch5_20.c,i,輸出: B C A E D,JD

37、*zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t-lt=0; t-rt=1; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p!=NULL) si+=p; p=p-lc; if(i0) p=s-i; printf(%c ,p-data); if(p-lc=NULL) p-lt=1; p-lc=pr; if(pr-rc=NULL) pr-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL

38、); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,1,算法 按中序線索化二叉樹(shù),Ch5_20.c,輸出: B C A E D,算法 按中序線索化二叉樹(shù) 遍歷中序線索二叉樹(shù),Ch5_20.c,在中序線索二叉樹(shù)中找結(jié)點(diǎn)后繼的方法： （1）若rt=1, 則rc域直接指向其后繼 （2）若rt=0, 則結(jié)點(diǎn)的后繼應(yīng)是其右子樹(shù)的左鏈尾（lt=1)的結(jié)點(diǎn),在中序線索二叉樹(shù)中找結(jié)點(diǎn)前驅(qū)的方法： （1）若lt=1, 則lc域直接指向其前驅(qū) （2）若lt=0, 則結(jié)點(diǎn)的前驅(qū)應(yīng)是其左子樹(shù)的右鏈尾（rt=1)的結(jié)點(diǎn),二叉排序樹(shù) 定義：二叉排序樹(shù)或是一棵空樹(shù)，或是具有下列性質(zhì)的二叉樹(shù)：

39、 若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值 若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值 它的左、右子樹(shù)也分別為二叉排序樹(shù) 二叉排序樹(shù)的插入 插入原則：若二叉排序樹(shù)為空，則插入結(jié)點(diǎn)應(yīng)為新的根結(jié)點(diǎn)；否則，繼續(xù)在其左、右子樹(shù)上查找，直至某個(gè)葉子結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)為空為止，則插入結(jié)點(diǎn)應(yīng)為該葉子結(jié)點(diǎn)的左孩子或右孩子 二叉排序樹(shù)生成：從空樹(shù)出發(fā)，經(jīng)過(guò)一系列的查找、插入操作之后，可生成一棵二叉排序樹(shù),插入算法,例 10， 18， 3， 8， 12， 2， 7， 3,10,中序遍歷二叉排序樹(shù)可得到一個(gè)關(guān)鍵字的有序序列,Ch5_9.c,二叉排序樹(shù)的刪除 要?jiǎng)h除二叉排序樹(shù)中的p結(jié)點(diǎn)，分三種情況： p為葉子結(jié)點(diǎn)，只需修改p雙親f的指針f-lchild=NULL f-rchild=NULL p只有左子樹(shù)或右子樹(shù) p只有左子樹(shù)，用p的左孩子代替p (1)(2) p只有右子樹(shù)，用p的右孩子代替p (3)(4) p左、右子樹(shù)均非空 沿p左子樹(shù)的根C的右子樹(shù)分支找到S，S的右子樹(shù)為空，將S的左子樹(shù)成為S的雙親Q的右子樹(shù)，用S取代p (5) 若C無(wú)右子樹(shù)，用C取代p (6),刪除算法,Ch5_10.c,