4、有 個結(jié)點(k1),證明：由性質(zhì)1，可得深度為k 的二叉樹最大結(jié)點數(shù)是,性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1,證明：n1為二叉樹T中度為1的結(jié)點數(shù) 因為：二叉樹中所有結(jié)點的度均小于或等于2 所以：其結(jié)點總數(shù)n=n0+n1+n2 又二叉樹中，除根結(jié)點外，其余結(jié)點都只有一個 分支進(jìn)入 設(shè)B為分支總數(shù)，則n=B+1 又：分支由度為1和度為2的結(jié)點射出，B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1,幾種特殊形式的二叉樹 滿二叉樹 定義：,特點：每一層上的結(jié)點數(shù)都是最大
5、結(jié)點數(shù) 完全二叉樹 定義：深度為k，有n個結(jié)點的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱為 特點 葉子結(jié)點只可能在層次最大的兩層上出現(xiàn) 對任一結(jié)點，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為l 或l+1 性質(zhì) 性質(zhì)4：,,,性質(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
6、,5.3 樹的存儲結(jié)構(gòu) 樹的存儲結(jié)構(gòu) 雙親表示法 實現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點，每個結(jié)點含兩個域： 數(shù)據(jù)域：存放結(jié)點本身信息 雙親域：指示本結(jié)點的雙親結(jié)點在數(shù)組中位置 特點：找雙親容易，找孩子難,typedef struct node datatype data; int parent; JD; JD tM;,0,1,2,2,3,5,5,5,1,0號單元不用或 存結(jié)點個數(shù),如何找孩子結(jié)點,孩子表示法 多重鏈表：每個結(jié)點有多個指針域，分別指向其子樹的根 結(jié)點同構(gòu)：結(jié)點的指針個數(shù)相等，為樹的度D 結(jié)點不同構(gòu)：結(jié)點指針個數(shù)不等，為該結(jié)點的度d,孩子鏈表：每個結(jié)點的孩子結(jié)點用單鏈表存儲，再用含n
7、個元素的結(jié)構(gòu)數(shù)組指向每個孩子鏈表,孩子結(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不用,,,,,,如何找雙親結(jié)點,帶雙親的孩子鏈表,孩子兄弟表示法（二叉樹表示法） 實現(xiàn)：用二叉鏈表作樹的存儲結(jié)構(gòu)，鏈表中每個結(jié)點的兩個
8、指針域分別指向其第一個孩子結(jié)點和下一個兄弟結(jié)點 特點 操作容易 破壞了樹的層次,typedef struct node datatype data; struct node *fch, *nsib; JD;,,,,,,,,,,,,,,,,,,,二叉樹的存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu) 實現(xiàn)：按滿二叉樹的結(jié)點層次編號，依次存放二叉樹中的數(shù)據(jù)元素 特點： 結(jié)點間關(guān)系蘊(yùn)含在其存儲位置中 浪費空間，適于存滿二叉樹和完全二叉樹,鏈?zhǔn)酱鎯Y(jié)構(gòu) 二叉鏈表,typedef struct node datatype data; struct node *lchild, *rchild; JD;,在n個結(jié)點的二叉鏈
9、表中，有n+1個空指針域,,,,,,,,,,,,,,,三叉鏈表,typedef struct node datatype data; struct node *lchild, *rchild, *parent; JD;,,,,,,,,,,,,,,,,,,,,,,樹與二叉樹轉(zhuǎn)換,將樹轉(zhuǎn)換成二叉樹 加線：在兄弟之間加一連線 抹線：對每個結(jié)點，除了其左孩子外，去除其與其余孩子之間的關(guān)系 旋轉(zhuǎn)：以樹的根結(jié)點為軸心，將整樹順時針轉(zhuǎn)45,,,,,,樹轉(zhuǎn)換成的二叉樹其右子樹一定為空,將二叉樹轉(zhuǎn)換成樹 加線：若p結(jié)點是雙親結(jié)點的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用
10、線連起來 抹線：抹掉原二叉樹中雙親與右孩子之間的連線 調(diào)整：將結(jié)點按層次排列，形成樹結(jié)構(gòu),,,,,,森林轉(zhuǎn)換成二叉樹 將各棵樹分別轉(zhuǎn)換成二叉樹 將每棵樹的根結(jié)點用線相連 以第一棵樹根結(jié)點為二叉樹的根，再以根結(jié)點為軸心，順時針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu),二叉樹轉(zhuǎn)換成森林 抹線：將二叉樹中根結(jié)點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹 還原：將孤立的二叉樹還原成樹,5.4 樹和二叉樹的遍歷 樹的遍歷 遍歷按一定規(guī)律走遍樹的各個頂點，且使每一頂點僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結(jié)點的一個線性排列 常用方法 先根（序）遍歷：先訪問樹的根結(jié)點，
11、然后依次先根遍歷根的每棵子樹 后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點 按層次遍歷：先訪問第一層上的結(jié)點，然后依次遍歷第二層，第n層的結(jié)點,先序遍歷：,后序遍歷：,層次遍歷：,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,L,M,N,O,二叉樹的遍歷 方法 先序遍歷：先訪問根結(jié)點,然后分別先序遍歷左子樹、右子樹 中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點，最后中序遍歷右子樹 后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點 按層次遍歷：從上到下、從左到右訪問各結(jié)點,
12、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,-,+,a,*,b,-,c,d,/,e,f,算法 遞歸算法,,Ch5_1.c,void preorder(JD *bt) if(bt!=NULL) printf(%dt,bt-data); preorder(bt-lchi
13、ld); preorder(bt-rchild); ,,返回,返回,返回,返回,A,C,B,D,返回,先序序列：A B D C,非遞歸算法,,Ch5_4.c Ch5_40.C,后序遍歷非遞歸算法,遍歷算法應(yīng)用 按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為： A B C D E G F ,求二叉樹深度算法,,Ch5_5.c ch5_6.c,Ch5_1.c,統(tǒng)計二叉樹中葉子結(jié)點個數(shù)算法,5.5 二叉樹的應(yīng)用 哈夫曼樹(Huffman)帶權(quán)路徑長度最短的樹 定義 路徑：從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點間的 路徑長度：路徑上的分支數(shù) 樹的路徑長度：從樹根到每一個結(jié)點
14、的路徑長度之和 樹的帶權(quán)路徑長度：樹中所有帶權(quán)結(jié)點的路徑長度之和,Huffman樹設(shè)有n個權(quán)值w1,w2,wn，構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉子的權(quán)值為wi,則wpl最小的二叉樹叫,例 有4個結(jié)點，權(quán)值分別為7，5，2，4，構(gòu)造有4個葉子結(jié)點的二叉樹,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)造Huffman樹的方法Huffman算法 構(gòu)造Huffman樹步驟 根據(jù)給定的n個權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點的二叉樹，令起權(quán)值為wj 在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)
15、造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和 在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中 重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹,例 w=5, 29, 7, 8, 14, 23, 3, 11,Huffman算法實現(xiàn),,Ch5_8.c,一棵有n個葉子結(jié)點的Huffman樹有2n-1個結(jié)點 采用順序存儲結(jié)構(gòu)一維結(jié)構(gòu)數(shù)組 結(jié)點類型定義,typedef struct int data; int pa,lc,rc; JD;,,Ch5_8.c,Huffman樹應(yīng)用 最佳判定樹,Huffman編碼：數(shù)據(jù)通信用的二進(jìn)制編碼 思想：根據(jù)字符出現(xiàn)頻率編碼，使電文總長最短
16、編碼：根據(jù)字符出現(xiàn)頻率構(gòu)造Huffman樹，然后將樹中結(jié)點引向其左孩子的分支標(biāo)“0”，引向其右孩子的分支標(biāo)“1”；每個字符的編碼即為從根到每個葉子的路徑上得到的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樹根開始，從待譯碼電文中逐位取碼。若編碼是“0”，則向左走；若編碼是“1”，則向右走，一旦到達(dá)葉子結(jié)點，則譯出一個字符；再重新從根出發(fā)，直到電文結(jié)束,例 電文是CAS;CAT;SAT;AT 其編碼 “110101110111010000111
17、11000011000” 電文為“1101000” 譯文只能是“CAT”,線索二叉樹 定義： 前驅(qū)與后繼：在二叉樹的先序、中序或后序遍歷序列中兩個相鄰的結(jié)點互稱為 線索：指向前驅(qū)或后繼結(jié)點的指針稱為 線索二叉樹：加上線索的二叉鏈表表示的二叉樹叫 線索化：對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫 實現(xiàn) 在有n個結(jié)點的二叉鏈表中必定有n+1個空鏈域 在線索二叉樹的結(jié)點中增加兩個標(biāo)志域 lt :若 lt =0, lc 域指向左孩子；若 lt=1, lc域指向其前驅(qū) rt :若 rt =0, rc 域指向右孩子；若 rt=1, rc域指向其后繼 結(jié)點定義：,typedef struct n
18、ode 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é)點： lt=0, lc指向根結(jié)點 rt=1, rc指向遍歷序列中最后一個結(jié)點 遍歷序列中第一個結(jié)點的lc域和最后 一個結(jié)點的rc域都指向頭結(jié)點,算法 按中序線索化二叉樹,,Ch5_20.c,,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)mall
19、oc(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;
20、 return(t); ,算法 按中序線索化二叉樹,,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=pr; if(pr-r
21、c==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); ,算法 按中序線索化二叉樹,,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+
22、+=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); ,算法 按中序線索化二叉樹,Ch5_20.c,,i,,輸出:B,,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(
23、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)
24、; ,1,算法 按中序線索化二叉樹,,Ch5_20.c,,輸出:B,,i,P-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(
25、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); ,算法 按中序線索化二叉樹,,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 whi
26、le(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); ,算法 按中序線索化二叉樹,,Ch5_20.c,,i,輸出: B C,,,JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=
27、(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;
28、 t-rc=pr; return(t); ,1,算法 按中序線索化二叉樹,,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) si++=p; p=p-lc; if(i0) p=s--i; printf(%c ,p-data); if(p-lc==NULL) p
29、-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); ,算法 按中序線索化二叉樹,,Ch5_20.c,,i,輸出: B C A,,,,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); ,1,算法 按中序線索化二叉樹,,Ch5_20.c,,i,輸出: B C A,,,,P-D,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(
32、i0||p!=NULL); pr-rc=t; pr-rt=1; t-rc=pr; return(t); ,算法 按中序線索化二叉樹,,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; pr=t; p=bt; do while(p!=NULL) si++=p; p=p-lc; if(i0) p=s--i;
33、 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); ,算法 按中序線索化二叉樹,,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;
34、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); ,算法 按中序線索化二叉
35、樹,,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=
36、=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,算法 按中序線索化二叉樹,,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;
37、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); ,算法 按中序線索化二叉樹,,Ch5_20.c,,i,輸出: B C A E D,,,,,,JD *zxxsh(JD *bt) JD *p,*pr,*sM,
38、*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
39、-rc=t; pr-rt=1; t-rc=pr; return(t); ,1,算法 按中序線索化二叉樹,,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; 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-
40、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,算法 按中序線索化二叉樹,,Ch5_20.c,,輸出: B C A E D,算法 按中序線索化二叉樹 遍歷中序線索二叉樹,,Ch5_20.c,在中序線索二叉樹中找結(jié)點后繼的方法： （1）若rt=1, 則rc域直接指向其后繼 （2）若rt=0, 則結(jié)點的后繼應(yīng)是其右子樹的左鏈尾（lt
41、=1)的結(jié)點,在中序線索二叉樹中找結(jié)點前驅(qū)的方法： （1）若lt=1, 則lc域直接指向其前驅(qū) （2）若lt=0, 則結(jié)點的前驅(qū)應(yīng)是其左子樹的右鏈尾（rt=1)的結(jié)點,二叉排序樹 定義：二叉排序樹或是一棵空樹，或是具有下列性質(zhì)的二叉樹： 若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值 若它的右子樹不空，則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值 它的左、右子樹也分別為二叉排序樹 二叉排序樹的插入 插入原則：若二叉排序樹為空，則插入結(jié)點應(yīng)為新的根結(jié)點；否則，繼續(xù)在其左、右子樹上查找，直至某個葉子結(jié)點的左子樹或右子樹為空為止，則插入結(jié)點應(yīng)為該葉子結(jié)點的左孩子或右孩子 二叉排序樹
42、生成：從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，可生成一棵二叉排序樹,插入算法,例 10， 18， 3， 8， 12， 2， 7， 3,10,中序遍歷二叉排序樹可得到一個關(guān)鍵字的有序序列,,Ch5_9.c,二叉排序樹的刪除 要刪除二叉排序樹中的p結(jié)點，分三種情況： p為葉子結(jié)點，只需修改p雙親f的指針f-lchild=NULL f-rchild=NULL p只有左子樹或右子樹 p只有左子樹，用p的左孩子代替p (1)(2) p只有右子樹，用p的右孩子代替p (3)(4) p左、右子樹均非空 沿p左子樹的根C的右子樹分支找到S，S的右子樹為空，將S的左子樹成為S的雙親Q的右子樹，用S取代p (5) 若C無右子樹，用C取代p (6),,,,,,,,刪除算法,,Ch5_10.c,
數(shù)據(jù)結(jié)構(gòu)-樹-嚴(yán)蔚敏版.ppt
