數(shù)據(jù)結(jié)構(gòu)DOC講義第5章

1、第五章 樹(shù)樹(shù)是一類重要的非線性數(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)，稱為樹(shù)的根(root)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集T1,T2,Tm，其中每一個(gè)集合本身又是一棵樹(shù)，稱為根的子樹(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ù)的根稱為該結(jié)點(diǎn)的孩子雙親(parents)孩子結(jié)點(diǎn)的

2、上層結(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ù)森林(forestm(m口 0棵互不相交的樹(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)【的雙親：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二叉樹(shù)定義定義：二叉樹(shù)是n(n口 0個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?shù)(n=

3、0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱 為左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)構(gòu)成特點(diǎn)每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)(即不存在度大于2的結(jié)點(diǎn))二叉樹(shù)的子樹(shù)有左、右之分，且其次序不能任意顛倒基本形態(tài)二叉樹(shù)性質(zhì)性質(zhì)1：性質(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幾

4、種特殊形式的二叉樹(shù)滿二叉樹(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的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為特點(diǎn)葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為1，則其左分支下子孫的最大層次必為l或1+1性質(zhì)性質(zhì)4：性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1口記n) 有：如果i=1，則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i1，則其雙親是口 i/2口如果2in，則結(jié)點(diǎn)i無(wú)左孩子；如果2迢n則其左孩子是2i如果2i+1n，則結(jié)點(diǎn)i無(wú)右孩子；如果2i+1 n則其

5、右孩子是2i+15.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ù)域：存放結(jié)點(diǎn)本身信息雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置特點(diǎn)：找雙親容易，找孩子難typedef struct node( datatype data;int parent;JD;JD tM;0122355510號(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)：

6、typedef struct node int child;該結(jié)點(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, *

7、nsib;JD;二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)：按滿二叉樹(shù)的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹(shù)中的數(shù)據(jù)元素特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中浪費(fèi)空間，適于存滿二叉樹(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ù)加線：在兄弟之間加一連線抹線：對(duì)每個(gè)結(jié)

8、點(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的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與？的雙親用線連起來(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)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹(shù)還原：將孤立的二

9、叉樹(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)先序遍歷：后序遍歷：層次遍歷：ABEFIGCDHNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO二叉樹(shù)的遍歷方法先序遍歷：先訪問(wèn)根結(jié)點(diǎn)，然后分別先序遍歷左子樹(shù)、右子樹(shù)中序遍歷：先中序遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù)

10、后序遍歷：先后序遍歷左、右子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)按層次遍歷：從上到下、從左到右訪問(wèn)各結(jié)點(diǎn)DLR先序遍歷序列：A B D C先序遍歷：LDR中序遍歷序列：B D A C中序遍歷：LRD后序遍歷序列：D B C A后序遍歷：先序遍歷：中序遍歷：后序遍歷：層次遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef*b-cd/ef算法遞歸算法Ch5_1.cvoid preorder(JD *bt) if(bt!=NULL)( printf(%dt”,bt-data);preorder(bt-lchild);preorder(bt-rchild);返回返回返回返回ACBD返回先序序列：A

11、 B D C非遞歸算法Ch5_4.cCh5_40.C后序遍歷非遞歸算法遍歷算法應(yīng)用按先序遍歷序列建立二叉樹(shù)的二叉鏈表，已知先序序列為：ABC D E G F 求二叉樹(shù)深度算法Ch5_5.cch5_6.cCh5_1.c統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)算法5.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,則wp

12、l最小的二叉樹(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=36WPL=7*3+5*3+2*1+4*2=46WPL=7*1+5*2+2*3+4*3=35 構(gòu)造Huffman樹(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,

13、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)類型定義 typedef struct int data;int pa,lc,rc;JD;Ch5_8.cHuffman樹(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ù)淖址疍=C,A,S,

14、T, ; 字符出現(xiàn)頻率w=2,4,2,3,3 TOC o 1-5 h z T :00;:01A :10C :110S :111譯碼：從Huffman樹(shù)根開(kāi)始，從待譯碼電文中逐位取碼。若編碼是“0”，則向左走；若編 碼是“1”，則向右走，一旦到達(dá)葉子結(jié)點(diǎn)，則譯出一個(gè)字符；再重新從根出發(fā)，直到電文結(jié)束例 電文是CAS;CAT;SAT;AT其編碼“1101011101110100001111100001100”電文為“1101000”譯文只能是“ CAT”線索二叉樹(shù)定義：前驅(qū)與后繼：在二叉樹(shù)的先序、中序或后序遍歷序列中兩個(gè)相鄰的結(jié)點(diǎn)互稱為線索：指向前驅(qū)或后繼結(jié)點(diǎn)的指針?lè)Q為線索二叉樹(shù)：加上線索的二叉鏈

15、表表示的二叉樹(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, 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;00001111A1100001111A110000111111A頭結(jié)點(diǎn)：lt=O, 1c指向根結(jié)點(diǎn)rt=l, rc指向遍歷序列中最后一個(gè)結(jié)點(diǎn)遍歷序列中第一個(gè)結(jié)點(diǎn)的

16、lc域和最后 一個(gè)結(jié)點(diǎn)的rc域都指向頭結(jié)點(diǎn) 算法按中序線索化二叉樹(shù)Ch5_20.cJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD);t-lt=O; t-rt=l; 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=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l

17、; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr; return(t);算法按中序線索化二叉樹(shù)Ch5_20.cJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; 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-d

18、ata); if(p-lc=NULL) p-lt=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr; return(t);算法按中序線索化二叉樹(shù)Ch5_20.cJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; t-TC=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt;do

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

20、t-rt=l; 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=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr; return(t);1算法按中序線索化二叉樹(shù)Ch5_20.c輸出:BP-CJD *zxxsh(

21、JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; 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=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t

22、; pr-rt=l; t-rc=pr; return(t);算法按中序線索化二叉樹(shù)Ch5_20.cP-C輸出:BJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; 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=l; p-lc=pr; if(pr-r

23、c=NULL) pr-rt= 1; pr-rc=p;pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr;return(t);算法按中序線索化二叉樹(shù)Ch5_20.c輸出:B CJD *zxxsh(JD *bt)( JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; 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)

24、(P=s-i;printf(%c ,p-data); if(p-lc=NULL) p-lt=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; 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=O; t-rt=l; t-rc=t; if(bt=NULL) t-l

25、c=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=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc; while(iOllp!=NULL); pr-rc=t; pr-rt=l; t-rc=pr; return(t); 算法 按中序線索化二叉樹(shù) Ch5_20.c i 輸出:B C A JD *zxxsh(JD *bt) JD *p,*pr,*sM

26、,*t;int i=0; t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; 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=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr;

27、return(t);1算法按中序線索化二叉樹(shù)Ch5_20.c輸出:B C AP-DJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; 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=l; p-lc=pr; if(pr-rc=NULL) pr-rt=

28、l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr; return(t);算法按中序線索化二叉樹(shù)Ch5_20.c輸出:B C AP-DP-EJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; 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

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

30、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=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr; return(t);算法按中序線索化二叉樹(shù)Ch5_20.c輸出:B CAEP-DJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0

31、;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; 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=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=1; t-rc=pr;return(t);1

32、算法按中序線索化二叉樹(shù)Ch5_20.ci輸出:B CAEP-DJD *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-

33、rc;while(i0|p!=NULL);pr-rc=t; pr-rt=1; t-rc=pr;return(t);算法按中序線索化二叉樹(shù)Ch5_20.ci輸出: B C A E DJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD);t-lt=O; t-rt=l; 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=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-r