数据结构之线性表和树剖析.ppt

2.5 树 2.5.1 树的定义：由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。 2.5.2 二叉树 （Binary Tree） 1 、二叉树的定义及其性质 (1) 二叉树的定义 （5）树与二叉树的区别 A．树的结点个数至少为1，而二叉树的结点个数可以为0。 B．树中结点的最大度数没有限制，二叉树结点最大度数为2。 C．树的结点无左、右之分，二叉树的结点子树有明确的左、右之分。 （5）树与二叉树的区别 A． 树的结点个数至少为1，而二叉树的结点个数可以为0。 B．树中结点的最大度数没有限制，二叉树结点最大度数为2。 C．树的结点子树无左、右之分，二叉树的结点子树有明确的左、 右之分。 While (pa!=nNULL)/*如果pa链表还未到表尾，复制剩余部分*/ {q=(JD *)malloc(sizeof(JD)); q-data = pa-data; pa=pa-link; p-link=q; p=q; } While (pb!=nNULL)/*如果pb链表还未到表尾，复制剩余部分*/ {q=(JD *)malloc(sizeof(JD)); q-data = pb-data; pb=pb-link; p-link=q; p=q; } pc p-link=NULL; p q a1 a2 b1 pc p-link=NULL; p=pc; p q a1 a2 b1 pc p-link=NULL; p=pc; pc=p-link; p q a1 a2 b1 pc p-link=NULL; p=pc; pc=p-link; free(p); p q a1 a2 b1 pc p-link=NULL; p=pc; return(pc); } pc=p-link; free(p); q a1 a2 b1 合并算法程序如下： JD * comlink(JD *pa,JD *pb) { JD *p，*q，*pc； pc=(JD*)malloc(sizeof(JD))； p=pc； While(pa!=NULL pb!=NULL) {q=(JD*)malloc(sizeof(JD))； if (pb-data pa-data) {q-data = pb-data； pb = pb-link；} Else {q-data = pa-data； pa=pa-link； p-link=q； if (pa-data= =pb-data) pb = pb-link；} p=q； } While (pa!=nNULL)/*如果pa链表还未到表尾，复制剩余部分*/ {q=(JD *)malloc(sizeof(JD)); q-data = pa-data; pa=pa-link; p-link=q; p=q; } While (pb!=nNULL)/*如果pb链表还未到表尾，复制剩余部分*/ {q=(JD *)malloc(sizeof(JD)); q-data = pb-data; pb=pb-link; p-link=q; p=q; } p-link=NULL; p=pc; return(pc); } pc=p-link; free(p); 下面介绍链表的创建。 Linklist creat() {linklist head,p1,p2; n=0；p1=p2=(struct lnode*)malloc(LEN)； scanf(“%d”,p1-data)；head-next=NULL; while(p1-data!0) {n=n+1； if(n==1) head-next=p1； else p2-next=p1； p2=p1；p1=(struct lnode*)malloc(LEN)； scanf(%d”,p1-data)；p2-next=NULL； }return(head)；} 创立具有头指针的链表 作业： P77 第29~25题 第27题、第29题 A C G D H I J M B E L K F 作业20解 A K、L、F、G、M、I、J C E、F E、F、G、H、I、J 4 A B C D E F K L G H I J M void change(NODE *T) {NODE *m; if(T!=NULL) { m=T-L T-L=T-R; T-R=m; change(T-L); change(T-R);} } typedef struct node{ int data； struct nod