數(shù)據(jù)結構-樹-嚴蔚敏版.ppt

《數(shù)據(jù)結構-樹-嚴蔚敏版.ppt》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構-樹-嚴蔚敏版.ppt（78頁珍藏版）》請在裝配圖網上搜索。

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

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

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

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

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

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

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

8、的存儲結構 順序存儲結構 實現(xiàn)：按滿二叉樹的結點層次編號，依次存放二叉樹中的數(shù)據(jù)元素 特點： 結點間關系蘊含在其存儲位置中 浪費空間，適于存滿二叉樹和完全二叉樹,鏈式存儲結構 二叉鏈表,typedef struct node datatype data; struct node *lchild, *rchild; JD;,在n個結點的二叉鏈表中，有n+1個空指針域,三叉鏈表,typedef struct node datatype data; struct node *lchild, *rchild, *parent; JD;,樹與二叉樹轉換,將樹轉換成二叉樹 加線：在兄弟之間加一連線 抹線：

9、對每個結點，除了其左孩子外，去除其與其余孩子之間的關系 旋轉：以樹的根結點為軸心，將整樹順時針轉45,樹轉換成的二叉樹其右子樹一定為空,將二叉樹轉換成樹 加線：若p結點是雙親結點的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用線連起來 抹線：抹掉原二叉樹中雙親與右孩子之間的連線 調整：將結點按層次排列，形成樹結構,森林轉換成二叉樹 將各棵樹分別轉換成二叉樹 將每棵樹的根結點用線相連 以第一棵樹根結點為二叉樹的根，再以根結點為軸心，順時針旋轉，構成二叉樹型結構,二叉樹轉換成森林 抹線：將二叉樹中根結點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之

10、變成孤立的二叉樹 還原：將孤立的二叉樹還原成樹,5.4 樹和二叉樹的遍歷 樹的遍歷 遍歷按一定規(guī)律走遍樹的各個頂點，且使每一頂點僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結點的一個線性排列 常用方法 先根（序）遍歷：先訪問樹的根結點，然后依次先根遍歷根的每棵子樹 后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結點 按層次遍歷：先訪問第一層上的結點，然后依次遍歷第二層，第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,二叉樹的遍歷 方法 先序遍歷：先訪問根結點,然后分別先序遍歷左子樹、右子樹 中序遍歷：先中序遍歷左子樹，然后訪問根結點，最后中序遍歷右子樹 后序遍歷：先后序遍歷左、右子樹，然后訪問根結點 按層次遍歷：從上到下、從左到右訪問各結點,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,后序遍歷非遞歸算法,遍歷算法應用 按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為： A B C D E G F ,求二叉樹深度算法,Ch5_5.c ch5_6.c,Ch5_1.c,統(tǒng)計二叉樹中葉子結點個數(shù)算法,5

13、.5 二叉樹的應用 哈夫曼樹(Huffman)帶權路徑長度最短的樹 定義 路徑：從樹中一個結點到另一個結點之間的分支構成這兩個結點間的 路徑長度：路徑上的分支數(shù) 樹的路徑長度：從樹根到每一個結點的路徑長度之和 樹的帶權路徑長度：樹中所有帶權結點的路徑長度之和,Huffman樹設有n個權值w1,w2,wn，構造一棵有n個葉子結點的二叉樹，每個葉子的權值為wi,則wpl最小的二叉樹叫,例 有4個結點，權值分別為7，5，2，4，構造有4個葉子結點的二叉樹,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,構造Hu

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

15、 data; int pa,lc,rc; JD;,Ch5_8.c,Huffman樹應用 最佳判定樹,Huffman編碼：數(shù)據(jù)通信用的二進制編碼 思想：根據(jù)字符出現(xiàn)頻率編碼，使電文總長最短 編碼：根據(jù)字符出現(xiàn)頻率構造Huffman樹，然后將樹中結點引向其左孩子的分支標“0”，引向其右孩子的分支標“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”，則向左走；

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

17、lc 域指向左孩子；若 lt=1, lc域指向其前驅 rt :若 rt =0, rc 域指向右孩子；若 rt=1, rc域指向其后繼 結點定義：,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,頭結點： lt=0, lc指向根結點 rt=1, rc指向遍歷序列中最后一個結點 遍歷序列中第一個結點的lc域和最后 一個結點的rc域都指向頭結點,算法 按中序線索化二叉樹,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); ,算法 按中序線索化二叉樹,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); ,算法 按中序線索化二叉樹,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); ,算法 按中序線索化二叉樹,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,算法 按中序線索化二叉樹,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); ,算法 按中序線索化二叉樹,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); ,算法 按中序線索化二叉樹,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,算法 按中序線索化二叉樹,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); ,算法 按中序線索化二叉樹,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,算法 按中序線索化二叉樹,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); ,算法 按中序線索化二叉樹,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); ,算法 按中序線索化二叉樹,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、 ,算法 按中序線索化二叉樹,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,算法 按中序線索化二叉樹,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); ,算法 按中序線索化二叉樹,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,算法 按中序線索化二叉樹,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,算法 按中序線索化二叉樹,Ch5_20.c,輸出: B C A E D,算法 按中序線索化二叉樹 遍歷中序線索二叉樹,Ch5_20.c,在中序線索二叉樹中找結點后繼的方法： （1）若rt=1, 則rc域直接指向其后繼 （2）若rt=0, 則結點的后繼應是其右子樹的左鏈尾（lt=1)的結點,在中序線索二叉樹中找結點前驅的方法： （1）若lt=1, 則lc域直接指向其前驅 （2）若lt=0, 則結點的前驅應是其左子樹的右鏈尾（rt=1)的結點,二叉排序樹 定義：二叉排序樹或是一棵空樹，或是具有下列性質的二叉樹：

39、 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值 若它的右子樹不空，則右子樹上所有結點的值均大于或等于它的根結點的值 它的左、右子樹也分別為二叉排序樹 二叉排序樹的插入 插入原則：若二叉排序樹為空，則插入結點應為新的根結點；否則，繼續(xù)在其左、右子樹上查找，直至某個葉子結點的左子樹或右子樹為空為止，則插入結點應為該葉子結點的左孩子或右孩子 二叉排序樹生成：從空樹出發(fā)，經過一系列的查找、插入操作之后，可生成一棵二叉排序樹,插入算法,例 10， 18， 3， 8， 12， 2， 7， 3,10,中序遍歷二叉排序樹可得到一個關鍵字的有序序列,Ch5_9.c,二叉排序樹的刪除 要刪除二叉排序樹中的p結點，分三種情況： p為葉子結點，只需修改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,