數(shù)據(jù)結構教學課件：第六講3二叉樹

1、F二叉樹建立算法 按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為： A B C D E G F A B C D E F G JD *crt_bt_pre(JD *bt) char ch; printf(ch=); scanf(%c,&ch); if(ch= ) bt=NULL; else bt=(JD *)malloc(sizeof(JD); bt-data=ch; bt-lchild=crt_bt_pre(bt-lchild); bt-rchild=crt_bt_pre(bt-rchild); return(bt);用遞歸的方法計算二叉樹的節(jié)點數(shù)遍歷算法相關的應用求二叉樹中葉子節(jié)

2、點的數(shù)目求二叉樹的深度二叉樹左右子樹互換u線索二叉樹F定義： 前驅與后繼前驅與后繼：在二叉樹的先序、中序或后序遍歷序列中兩個相鄰的結點互稱為 線索線索：指向前驅或后繼結點的指針稱為 線索二叉樹線索二叉樹：加上線索的二叉鏈表表示的二叉樹叫 線索化線索化：對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫F實現(xiàn) 在有n個結點的二叉鏈表中必定有n+1個空鏈域 在線索二叉樹的結點中增加兩個標志域 lt :若 lt =0, lc 域指向左孩子；若 lt=1, lc域指向其前驅 rt :若 rt =0, rc 域指向右孩子；若 rt=1, rc域指向其后繼 結點定義：typedef struct node

3、int data; int lt, rt; struct node *lc, *rc;JD; lc lt data rt rcABCDE A B D C ET先序序列：ABCDE先序線索二叉樹00001111 11ABCDE A B D C ET中序序列：BCAED中序線索二叉樹0000111111ABCDE A B D C ET后序序列：CBEDA后序線索二叉樹0000111111ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED帶頭結點的中序線索二叉樹 0 1頭結點：lt=0, lc指向根結點rt=1, rc指向遍歷序列中最后一個結點遍歷序列中第

4、一個結點的lc域和最后一個結點的rc域都指向頭結點 A B D C ET中序序列：BCAED中序線索二叉樹0000111111ABCDEt 0 1prpiP-AJD *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=NUL

5、L) 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); A B D C Ebt0000000000中序線索二叉樹ABCDE 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;

6、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);0000000000ABCDE A B D C Ebtt 0 1prP=NULLiP-AP-BJD *zxxsh(JD *bt) JD *p,*p

7、r,*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-

8、rc=pr; return(t);0000000000ABCDE A B D 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;

9、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);00000000001ABCDE 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

10、(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);0000100000ABCDE A B D C Ebtt 0 1prP=NULLiP-AP-C輸出:BJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)mal

11、loc(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);0000100000Ch5

12、_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(pr-rc=NULL) pr-

13、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);00001000001ABCDE 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=bt; pr=t; p=bt; do while(p!=NULL) si

14、+=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);0000100010ABCDE A B D C Ebtt 0 1prPi輸出: B C A JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(sizeof(JD); t

15、-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);00001000101 遍歷中序線索二叉樹在中序線索二叉樹中

16、找結點后繼的方法：（1）若rt=1, 則rc域直接指向其后繼（2）若rt=0, 則結點的后繼應是其右子樹的左鏈尾（lt=1)的結點在中序線索二叉樹中找結點前驅的方法：（1）若lt=1, 則lc域直接指向其前驅（2）若lt=0, 則結點的前驅應是其左子樹的右鏈尾（rt=1)的結點ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED帶頭結點的中序線索二叉樹 0 1n二叉樹的應用u哈夫曼樹(Huffman)帶權路徑長度最短的樹F定義 路徑：從樹中一個結點到另一個結點之間的分支構成這兩個結點間的 路徑長度：路徑上的分支數(shù) 樹的路徑長度：從樹根到每一個結點的路徑長度之和 樹的帶權路徑長度：樹中所有帶權結點的路徑長度之和結點到根的路徑長度權值其中：記作：kknkkklwlwwpl1 Huffman樹設有n個權值w1,w2,wn，構造一棵有n個葉子結點的二叉樹，每個葉子的權值為wi,則wpl最小的二叉樹叫例 有4個結點，權值分別為7，5，2，4，構造有4個葉子結點的二叉樹abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd