数据结构树教程PPT学习教案

1、会计学1 数据结构树教程数据结构树教程 A 只有根结点的树 A BCD EFGHIJ KLM 有子树的树 根 子树 第1页/共77页 n深度(depth)树中结点的最大层次 数 n森林(forest)m(m0)棵互不相交的 树的集合 第2页/共77页 A BCD EFGHIJ KLM 结点A的度：3 结点B的度：2 结点M的度：0 叶子：K，L，F，G，M，I，J 结点A的孩子：B，C，D 结点B的孩子：E，F 结点I的双亲：D 结点L的双亲：E 结点B，C，D为兄弟 结点K，L为兄弟 树的度：3 结点A的层次：1 结点M的层次：4 树的深度：4 结点F，G为堂兄弟 结点A是结点F，G的祖先

2、第3页/共77页 A 只有根结点 的二叉树 空二叉树 A B 右子树为空 A B 左子树为空 A BC 左、右子树 均非空 第4页/共77页 ) 1(2 1 ii i 个结点层上至多有在二叉树的第 证明：用归纳法证明之 i=1时，只有一个根结点， 是对的 假设对所有j(1j B D C D L R 先序遍历序列：A B D C 先序遍历: 第27页/共77页 A D B C L D R B L D R L D R A D C L D R 中序遍历序列：B D A C 中序遍历: 第28页/共77页 A D B C L R D L R D L R D A D C L R D 后序遍历序列： D

3、B C A 后序遍历: B 第29页/共77页 - + / a* b- e f cd 先序遍历： 中序遍历： 后序遍历： 层次遍历： - + a * b - c d / e f -+a*b-cd/ef - +a*b - c d/ef -+a*b-c d/e f 第30页/共77页 void preorder(JD *bt) if(bt!=NULL) printf(%dt,bt-data); preorder(bt-lchild); preorder(bt-rchild); 主程序主程序 Pre( T ) 返回 返回 pre(T R); 返回 返回 pre(T R); A CB D T B pr

4、intf(B); pre(T L); B T A printf(A); pre(T L); A T D printf(D); pre(T L); D T C printf(C); pre(T L); C 返回 T 左是空返回 pre(T R); T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre(T R); 先序序列：A B D C 第31页/共77页 l非递归算法 A B CD E F G p i P-A (1) A B CD E F G p i P-A P-B (2) A B CD E F G p i P-A P-B P-C (3) p=NULL A B CD E F

5、G i P-A P-B 访问：C(4) 第32页/共77页 p A B CD E F G i P-A 访问：C B (5) A B CD E F G i P-A P-D 访问：C B p (6) A B CD E F G i P-A P-D P-E 访问：C B p (7) A B CD E F G i P-A P-D 访问：C B E p (8) 第33页/共77页 A B CD E F G i P-A P-D P-G 访问：C B E P=NULL (9) A B CD E F G i P-A 访问：C B E G D p (11) A B CD E F G i P-A P-F 访问：C

6、B E G D p (12) A B CD E F G i P-A P-D 访问：C B E G p (10) 第34页/共77页 A B CD E F G i P-A 访问：C B E G D F p=NULL (13) A B CD E F G i 访问：C B E G D F A p (14) A B CD E F G i 访问：C B E G D F A p=NULL (15) Ch5_4.c Ch5_40.C 后序遍历非递归算法 第35页/共77页 v遍历算法应用 l按先序遍历序列建立二叉树的二叉链表，已知先序序列为： A B C D E G F l求二叉树深度算法 Ch5_5.c

7、ch5_6.c A B CD E F G A B C D E F G Ch5_1.c l统计二叉树中叶子结点个数算法 第36页/共77页 结点到根的路径长度 权值其中： 记作： k k n k kk l w lwwpl 1 lHuffman树设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫 第37页/共77页 例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树 abcd 7524 WPL=7*2+5*2+2*2+4*2=3 6 d c ab 2 4 75 WPL=7*3+5*3+2*1+4*2=4 6 a b cd 7

8、 5 24 WPL=7*1+5*2+2*3+4*3=3 5 n k KKL WWPL 1 第38页/共77页 第39页/共77页 例 a 7 b 5 c 2 d 4 a 7 b 5 c 2 d 4 6 a 7 b 5 c 2 d 4 6 11 a 7 b 5 c 2 d 4 6 11 18 第40页/共77页 例 w=5, 29, 7, 8, 14, 23, 3, 11 514297823311 1429782311 35 8 87 15 142923 35 811 11 35 8 19 142923 87 15 11 35 8 19 2923 14 87 15 29 29 14 87 15

9、29 11 35 8 19 23 42 11 35 8 19 23 42 29 14 87 15 29 58 11 35 8 19 23 42 29 14 87 15 29 58 100 第41页/共77页 lHuffman算法实现 Ch5_8.c u一棵有n个叶子结点的Huffman树有2n-1个结点 u采用顺序存储结构一维结构数组 u结点类型定义 typedef struct int data; int pa,lc,rc; JD; 第42页/共77页 lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 0 0 0 7 5 2 4 0 0 0 0 0 0 0 0 0 0

10、0 0 0 0 0 0 0 (1) lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 3 0 0 7 5 2 4 6 0 0 0 0 0 0 4 0 0 0 0 5 5 0 0 0 k x1=3,x2=4 m1=2,m2=4 (2) lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 3 2 0 7 5 2 4 6 11 0 0 0 0 0 4 5 0 0 6 5 5 6 0 0 k x1=2,x2=5 m1=5,m2=6 (3) lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 3 2 1 7 5 2 4 6 11 18 0 0

11、 0 0 4 5 6 7 6 5 5 6 7 0 k x1=1,x2=6 m1=7,m2=11 (4) Ch5_8.c 第43页/共77页 vHuffman树应用 l最佳判定树 等级 分数段 比例 A B C DE 059 60697079808990100 0.05 0.150.40 0.30 0.10 a60 a90 a80 a70 E Y N D Y N C Y N B Y N A 70a80 a60 C Y N B Y N D Y N E Y N A 80a90 60a70 E A D E C a80 a70 a60 aA JD *zxxsh(JD *bt) JD *p,*pr,*sM

12、,*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-rc=pr

13、; return(t); A B D C E bt 0 0 00 0 0 0 0 00 第52页/共77页 v算法 l按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt t 0 1 pr p i P-A P-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(

14、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); 0 0 00 0 0 0 0 00 第53页/共77页 v算法 l按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt t 0 1 pr P=NULL i P-A P-B JD *zxxsh(JD *bt) JD *p,*pr,*sM,*

15、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-rc=pr;

16、return(t); 0 0 00 0 0 0 0 00 第54页/共77页 v算法 l按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt t 0 1 pr P i P-A 输出: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; pri

17、ntf(%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); 0 0 00 0 0 0 0 00 1 第55页/共77页 v算法 l按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt t 0 1 pr P 输出:B i P-A P-C JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0;

18、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); 0

19、 0 00 1 0 0 0 00 第56页/共77页 v算法 l按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt t 0 1 pr P=NULL i P-A 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

20、(%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); 0 0 00 1 0 0 0 00 第57页/共77页 v算法 l按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt t 0 1 pr P i P-A 输出: B C JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD

21、*)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); 0 0 00

22、1 0 0 0 001 第58页/共77页 v算法 l按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt t 0 1 pr P=NULL i P-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

23、-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); 0 0 00 1 0 0 0 10 第59页/共77页 v算法 l按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt t 0 1 pr P i 输出: B C A JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc

24、(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); 0 0 00 1 0 0 0

25、10 1 第60页/共77页 v算法 l按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt t 0 1 P i 输出: B C A pr 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

26、(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); 0 0 00 1 0 1 0 10 第61页/共77页 v算法 l按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt t 0 1 P i 输出: B C A pr P-D P-E JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)malloc(s

27、izeof(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); 0 0 00 1 0 1 0 10

28、 第62页/共77页 v算法 l按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt t 0 1 P=NULL i 输出: B C A pr 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; printf(%c ,p-data

29、); 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); 0 0 00 1 0 1 0 10 第63页/共77页 v算法 l按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt t 0 1 P i 输出: B C A E pr P-D JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)mallo

30、c(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); 0 0 00 1 0 1 0

31、 10 1 第64页/共77页 v算法 l按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt t 0 1 P=NULL i 输出: B C A E pr 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-d

32、ata); 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); 0 0 00 1 0 1 0 11 第65页/共77页 v算法 l按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt t 0 1 P i 输出: B C A E D pr JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0; t=(JD *)mall

33、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; return(t); 0 0 00 1 0 1

34、0 11 1 第66页/共77页 v算法 l按中序线索化二叉树 Ch5_20.c A B C D E A B D C E bt t 0 1 P=NULL i 输出: B C A E D pr 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-rt=1; pr-rc=p; pr=p; p=p-rc; while(i0|p!=NULL)