第六章二叉树和树

1、数据结构中的一种，属于非线性结构。数据结构中的一种，属于非线性结构。a只有根结点的二叉树空二叉树a左右子树为空a左右左、右子树均非空a左子树为空右abcdefghijabcdefg分支：结点拥有的子树称为其分支。分支：结点拥有的子树称为其分支。双亲双亲(parents)孩子结点的上层结点叫该结孩子结点的上层结点叫该结点的双亲点的双亲兄弟兄弟(sibling)同一双亲的孩子同一双亲的孩子祖先和子孙结点：祖先和子孙结点：二叉树的度二叉树的度一棵二叉树中最大的结点度数一棵二叉树中最大的结点度数结点的层次结点的层次(level)从根结点算起，根为第从根结点算起，根为第一层，它的孩子为第二层一层，它的孩

2、子为第二层深度深度(depth)树中结点的最大层次数树中结点的最大层次数证明：用归纳法证明之证明：用归纳法证明之 i=1时，只有一个根结点，时，只有一个根结点， 是对的是对的 假设对所有假设对所有j(1 j1，则其双亲是则其双亲是 i/2 (2) 如果如果2in，则结点则结点i无左孩子；如果无左孩子；如果2i n， 则其左孩子是则其左孩子是2i (3) 如果如果2i+1n，则结点则结点i无右孩子；如无右孩子；如果果2i+1 n，则其右孩子是则其右孩子是2i+11log2nn深度为个结点的完全二叉树的具有性质性质4abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6

3、7 8 9 10 11struct bitreenode datatype data; struct bitreenode *lchild, *rchild;lchild data rchild abcdefg在在n个结点的二叉链表中，有个结点的二叉链表中，有n+1个空指针域个空指针域 ab c d e f gtypedef struct node datatype data; struct node *lchild, *rchild, *parent;jd;lchild data parent rchild a b c d e f gabcdefgdlrldr、lrd、dlrrdl、rld、

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

5、 r);返回返回pre(t r);acbdtbprintf(b);pre(t l);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 cabcdefgpip-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)

6、abcdefgip-ap-dp-e访问：c bp(7)abcdefgip-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)abcdefg a b c d e f g abcde

7、fghijklm结点结点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的祖先的祖先a只有根结点的树只有根结点的树abcdefghijklm有子树的树有子树的树根根子树子树typedef struct node

8、datatype data; int parent;jd; jd tm;abcdefhgiacdefghib012235551096012345789dataparent0号单元不用或号单元不用或存结点个数存结点个数如何找孩子结点如何找孩子结点data child1 child2 . childddata degree child1 child2 . childdn孩子结点：孩子结点：typedef struct node int child; /该结点在表头数组中下标该结点在表头数组中下标nstruct node *next; /指向下一孩子结点指向下一孩子结点 jd;n表头结点：表头结点：

9、typedef struct tnode datatype data; /数据域数据域nstruct node *fc; /指向第一个孩子结点指向第一个孩子结点ntd;n ntd tm; /t0不用不用abcdefhgi6012345789acdefghibdatafc 2 3 4 5 9 7 8 6如何找双亲结点612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgi a b c d e f g h iabcdefhgiacbed树树abcde二叉树二叉树 a b c d e abcdefghiabcdefghiabcd

10、efghiabcdefghiabcdefghi树转换成的二叉树其右子树一定为空abcdefghiabcdefghiabcdefghiabcdefghiabcdefghiabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijklmno先序遍历：先序遍历：后序遍历：后序遍历：层次遍历：层次遍历：abefi gcdhj klnomeifgbcjknolmhdaabcdefghi j klmno结点到根的路径长度权值其中：记作：kknkkklwlwwpl1例例 有有4个结点，权值分别为个结点，权值

11、分别为7，5，2，4，构造有，构造有4个叶子结点的二叉树个叶子结点的二叉树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=35nkkklwwpl1例例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 231487152929148715

12、29113581923421135819234229148715295811358192342291487152958100typedef struct int data; int pa,lc,rc;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

13、4 5 6 70 0 0 0 3 2 07 5 2 4 6 11 00 0 0 0 4 5 00 6 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)等级等级分数段分数段比例比例abcde059606970798089 901000.050.150.400.300.10a60a90a80a70eyndyncynbyna70 a80a60cynbyndyneyna80 a9060

14、 a70eadeca80a70a60aajd *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

15、=p-rc; while(i0|p!=null); pr-rc=t; pr-rt=1; t-rc=pr; return(t); a b d c ebt0000000000ch5_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;

16、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);0000000000ch5_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=

17、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);0000000000ch5_20.cabcde a b d c eb

18、tt 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; p=p-

19、rc; while(i0|p!=null); pr-rc=t; pr-rt=1; t-rc=pr; return(t);00000000001ch5_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=p-lc; if(i0) p=s

20、-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_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 *)malloc(sizeof(jd); t-lt=0; t-r

21、t=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_20.cabcde a b d c ebtt 0 1

22、prpip-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-rt=1; pr-rc=p; pr=p; p=p-rc

23、; while(i0|p!=null); pr-rc=t; pr-rt=1; t-rc=pr; return(t);00001000001ch5_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=bt; pr=t; p=bt; do while(p!=null) si+=p; p=p-lc; if(i0)

24、 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);0000100010ch5_20.cabcde 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-lt=0; t-rt

25、=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);00001000101ch5_20.cabcde a b d c ebtt 0 1

26、pi输出: 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-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-

27、rc; while(i0|p!=null); pr-rc=t; pr-rt=1; t-rc=pr; return(t);0000101010ch5_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=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

28、) 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);0000101010ch5_20.cabcde a b d 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);

29、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);0000101010ch5_20.cabcde a b d

30、 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 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=

31、p; pr=p; p=p-rc; while(i0|p!=null); pr-rc=t; pr-rt=1; t-rc=pr; return(t);0000101010 1ch5_20.cabcde a b d c ebtt 0 1p=nulli输出: 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 while(p!=null) s

32、i+=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);0000101011ch5_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