數(shù)據(jù)結(jié)構(gòu)樹PPT教程

1、第五章 樹 樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)5.1 樹的定義定義v定義：樹(tree)是n(n0)個結(jié)點的有限集t，其中：l有且僅有一個特定的結(jié)點，稱為樹的根(root)l當n1時，其余結(jié)點可分為m(m0)個互不相交的有限集t1,t2,tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)v特點：l樹中至少有一個結(jié)點根l樹中各子樹是互不相交的集合a只有根結(jié)點的樹abcdefghijklm有子樹的樹根子樹基本術(shù)語v結(jié)點(node)表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支v結(jié)點的度(degree)結(jié)點擁有的子樹數(shù)v葉子(leaf)度為0的結(jié)點v孩子(ch

2、ild)結(jié)點子樹的根稱為該結(jié)點的孩子v雙親(parents)孩子結(jié)點的上層結(jié)點叫該結(jié)點的v兄弟(sibling)同一雙親的孩子v樹的度一棵樹中最大的結(jié)點度數(shù)v結(jié)點的層次(level)從根結(jié)點算起，根為第一層，它的孩子為第二層v深度(depth)樹中結(jié)點的最大層次數(shù)v森林(forest)m(m0)棵互不相交的樹的集合abcdefghijklm結(jié)點a的度：3結(jié)點b的度：2結(jié)點m的度：0葉子：k，l，f，g，m，i，j結(jié)點a的孩子：b，c，d結(jié)點b的孩子：e，f結(jié)點i的雙親：d結(jié)點l的雙親：e結(jié)點b，c，d為兄弟結(jié)點k，l為兄弟樹的度：3結(jié)點a的層次：1結(jié)點m的層次：4樹的深度：4結(jié)點f，g為堂兄弟

3、結(jié)點a是結(jié)點f，g的祖先5.2 二叉樹定義v定義：二叉樹是n(n0)個結(jié)點的有限集，它或為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成v特點l每個結(jié)點至多有二棵子樹(即不存在度大于2的結(jié)點)l二叉樹的子樹有左、右之分，且其次序不能任意顛倒v基本形態(tài)a只有根結(jié)點的二叉樹空二叉樹ab右子樹為空ab左子樹為空abc左、右子樹均非空二叉樹性質(zhì)v性質(zhì)1：) 1(21iii個結(jié)點層上至多有在二叉樹的第證明：用歸納法證明之 i=1時，只有一個根結(jié)點， 是對的 假設(shè)對所有j(1j1，則其雙親是i/2 (2) 如果2in，則結(jié)點i無左孩子；如果2in，則其左孩子是2i (3)

4、 如果2i+1n，則結(jié)點i無右孩子；如果2i+1n，則其右孩子是2i+15.3 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)v雙親表示法l實現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點，每個結(jié)點含兩個域：u數(shù)據(jù)域：存放結(jié)點本身信息u雙親域：指示本結(jié)點的雙親結(jié)點在數(shù)組中位置l特點：找雙親容易，找孩子難typedef struct node datatype data; int parent;jd;jd tm;abcdefhgiacdefghib012235551096012345789dataparent0號單元不用或存結(jié)點個數(shù)如何找孩子結(jié)點v孩子表示法l多重鏈表：每個結(jié)點有多個指針域，分別指向其子樹的根u結(jié)點同構(gòu)：結(jié)點的指針個數(shù)

5、相等，為樹的度du結(jié)點不同構(gòu)：結(jié)點指針個數(shù)不等，為該結(jié)點的度ddata child1 child2 . childddata degree child1 child2 . childdl孩子鏈表：每個結(jié)點的孩子結(jié)點用單鏈表存儲，再用含n個元素的結(jié)構(gòu)數(shù)組指向每個孩子鏈表孩子結(jié)點：typedef struct node int child; /該結(jié)點在表頭數(shù)組中下標 struct node *next; /指向下一孩子結(jié)點 jd;表頭結(jié)點：typedef struct tnode datatype data; /數(shù)據(jù)域 struct node *fc; /指向第一個孩子結(jié)點 td; td tm;

6、/t0不用abcdefhgi6012345789acdefghibdatafc 2 3 4 5 9 7 8 6如何找雙親結(jié)點l帶雙親的孩子鏈表612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgiv孩子兄弟表示法（二叉樹表示法）l實現(xiàn)：用二叉鏈表作樹的存儲結(jié)構(gòu)，鏈表中每個結(jié)點的兩個指針域分別指向其第一個孩子結(jié)點和下一個兄弟結(jié)點l特點u操作容易u破壞了樹的層次typedef struct node datatype data; struct node *fch, *nsib;jd;abcdefhgi a b c d e f

7、 g h i二叉樹的存儲結(jié)構(gòu)v順序存儲結(jié)構(gòu)l實現(xiàn)：按滿二叉樹的結(jié)點層次編號，依次存放二叉樹中的數(shù)據(jù)元素l特點：u結(jié)點間關(guān)系蘊含在其存儲位置中u浪費空間，適于存滿二叉樹和完全二叉樹abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11v鏈式存儲結(jié)構(gòu)l二叉鏈表typedef struct node datatype data; struct node *lchild, *rchild;jd;lchild data rchild abcdefg在n個結(jié)點的二叉鏈表中，有n+1個空指針域 ab c d e f gl三叉鏈表typedef struct

8、node datatype data; struct node *lchild, *rchild, *parent;jd;lchild data parent rchildabcdefg a b c d e f g樹與二叉樹轉(zhuǎn)換acbed樹abcde二叉樹 a b c d e a b c d e a b c d e 對應存儲存儲解釋解釋v將樹轉(zhuǎn)換成二叉樹l加線：在兄弟之間加一連線l抹線：對每個結(jié)點，除了其左孩子外，去除其與其余孩子之間的關(guān)系l旋轉(zhuǎn)：以樹的根結(jié)點為軸心，將整樹順時針轉(zhuǎn)45abcdefghiabcdefghiabcdefghiabcdefghiabcdefghi樹轉(zhuǎn)換成的二叉樹其右

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

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

11、gcdhj kl nome i f g b c j k n o l m h d aab c de f gh i j kl mno二叉樹的遍歷v方法l先序遍歷：先訪問根結(jié)點,然后分別先序遍歷左子樹、右子樹l中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點，最后中序遍歷右子樹l后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點l按層次遍歷：從上到下、從左到右訪問各結(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中序遍歷:adb

12、c l r dl r dl r dadcl r d后序遍歷序列： d 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 fvoid preorder(jd *bt) if(bt!=null) printf(%dt,bt-data); preorder(bt-lchild); preorder(bt-rchild); 主程序主程序pre( t )返回返回pre(t r);返回返回pre(t r);acbdtbprintf(b);pre(t l

13、);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 cl非遞歸算法abcdefgpip-a(1)abcdefgpip-ap-b(2)abcdefgpip-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-

14、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)abcdefgi訪問：c b e g d f ap(14)abcdefgi訪問：c b e g d f ap=null(15)ch5_4.cch5_40.c后序遍歷非遞歸算法v遍歷算法應用l按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為： a b c

15、 d e g f l求二叉樹深度算法ch5_5.cch5_6.cabcdefg a b c d e f g ch5_1.cl統(tǒng)計二叉樹中葉子結(jié)點個數(shù)算法5.5 二叉樹的應用哈夫曼樹(huffman)帶權(quán)路徑長度最短的樹v定義l路徑：從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點間的l路徑長度：路徑上的分支數(shù)l樹的路徑長度：從樹根到每一個結(jié)點的路徑長度之和l樹的帶權(quán)路徑長度：樹中所有帶權(quán)結(jié)點的路徑長度之和結(jié)點到根的路徑長度權(quán)值其中：記作：kknkkklwlwwpl1lhuffman樹設(shè)有n個權(quán)值w1,w2,wn，構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉子的權(quán)值為wi,則wpl最小的二叉樹叫例

16、有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=35nkkklwwpl1v構(gòu)造huffman樹的方法huffman算法l構(gòu)造huffman樹步驟u根據(jù)給定的n個權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點的二叉樹，令起權(quán)值為wju在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和u在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中u重復上述兩步，

17、直到只含一棵樹為止，這棵樹即哈夫曼樹例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100lhuffman算法實現(xiàn)ch5_8.cu一棵有n個葉子結(jié)點的huffman樹有2n-1個結(jié)點u采用順序存儲結(jié)構(gòu)一維結(jié)構(gòu)

18、數(shù)組u結(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

19、 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 2 4 6 11 180 0 0 0 4 5 67 6 5 5 6 7 0kx1=1,x2=6m1=7,m2=11(4)ch5_8.cvhuffman樹應用l最佳判定樹等級分數(shù)段比例abcde05960697079 8089 901000.050.150.400.300.10a60a90a80a70eyndyncynbyna70a80a60cynbyndyneyna80a9060a70eadeca80a70a60aajd *zxxsh(jd *b

20、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;

21、pr-rt=1; t-rc=pr; return(t); a b d c ebt0000000000v算法l按中序線索化二叉樹ch5_20.cabcde a b d c ebtt 0 1prpip-ap-bjd *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(%

22、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);0000000000v算法l按中序線索化二叉樹ch5_20.cabcde a b d c ebtt 0 1prp=nullip-ap-bjd *zxxsh(jd *bt) jd *p,*pr,*sm,*t; int i=0; t=(jd *)malloc(sizeof(jd); t-lt=0; t-rt=1

23、; 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);0000000000v算法l按中序線索化二叉樹ch5_20.cabcde a b d

24、c ebtt 0 1prpip-a輸出:bjd *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;

25、p=p-rc; while(i0|p!=null); pr-rc=t; pr-rt=1; t-rc=pr; return(t);00000000001v算法l按中序線索化二叉樹ch5_20.cabcde a b d c ebtt 0 1prp輸出:bip-ap-cjd *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

26、=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);0000100000v算法l按中序線索化二叉樹ch5_20.cabcde a b d c ebtt 0 1prp=nullip-ap-c輸出:bjd *zxxsh(jd *bt) jd *p,*pr,*sm,*t; int i=0; t=(jd *)

27、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);0000100000

28、v算法l按中序線索化二叉樹ch5_20.cabcde a b d c ebtt 0 1prpip-a輸出: 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) 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

29、(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);00001000001v算法l按中序線索化二叉樹ch5_20.cabcde a b d c ebtt 0 1prp=nullip-a輸出: 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

30、=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);0000100010v算法l按中序線索化二叉樹ch5_20.cabcde a b d c ebtt 0 1prpi輸出: b c a jd *zxxsh(jd *b

31、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;

32、pr-rt=1; t-rc=pr; return(t);00001000101v算法l按中序線索化二叉樹ch5_20.cabcde a b d c ebtt 0 1pi輸出: b c a prp-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

33、-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);0000101010v算法l按中序線索化二叉樹ch5_20.cabcde a b d c ebtt 0 1pi輸出: b c a prp-dp-ejd *zxxsh(jd *bt) jd *p,*pr,*sm,*t; int i=0; t=(jd *)malloc(sizeof(jd); t-lt=0; t-rt=

34、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);0000101010v算法l按中序線索化二叉樹ch5_20.cabcde a b d

35、 c ebtt 0 1p=nulli輸出: b c a prp-dp-ejd *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;

36、pr-rc=p; pr=p; p=p-rc; while(i0|p!=null); pr-rc=t; pr-rt=1; t-rc=pr; return(t);0000101010v算法l按中序線索化二叉樹ch5_20.cabcde a b d c ebtt 0 1pi輸出: b c a e prp-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 whil

37、e(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);0000101010 1v算法l按中序線索化二叉樹ch5_20.cabcde a b d c ebtt 0 1p=nulli輸出: b c a e prp-djd *zxxsh(jd *bt) jd *p,*pr

38、,*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; pr-rt=1; t-r

39、c=pr; return(t);0000101011v算法l按中序線索化二叉樹ch5_20.cabcde a b d c ebtt 0 1pi輸出: b c a e d prjd *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

40、-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);00001010111v算法l按中序線索化二叉樹ch5_20.cabcde a b d c ebtt 0 1p=nulli輸出: b c a e d prjd *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;