数据结构C语言版 树的双亲表存储表示

1、/*数据结构C语言版 树的双亲表存储表示P135 编译环境：Dev-C+ 日期：2011年2月13日 */#include <stdio.h>typedef char TElemType;/ 树的双亲表存储表示 #define MAX_TREE_SIZE 100typedef structTElemType data;/数据域int parent;/ 双亲位置域 PTNode;/结点结构typedef structPTNode nodesMAX_TREE_SIZE;/存储结点的数组int n; / 结点数 PTree;typedef structint num;TEl

2、emType name;QElemType; / 定义队列元素类型 typedef struct QNodeQElemType data;/数据域struct QNode *next;/指针域QNode,*QueuePtr;typedef structQueuePtr front,/队头指针，指针域指向队头元素rear; /队尾指针，指向队尾元素LinkQueue;TElemType Nil=' ' / 以空格符为空 int InitTree(PTree *T) / 操作结果: 构造空树T (*T).n=0;return 1;void DestroyTree() / 由于PTr

3、ee是定长类型,无法销毁 / 构造一个空队列Qint InitQueue(LinkQueue *Q) (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode);/动态分配一个空间if(!(*Q).front)exit(0);(*Q).front->next=NULL;/队头指针指向空，无数据域，这样构成了一个空队列return 1;/ 若Q为空队列,则返回1,否则返回0 int QueueEmpty(LinkQueue Q)if(Q.front=Q.rear)return 1;elsereturn 0;/ 插入元素e为Q的新的队尾元素int

4、EnQueue(LinkQueue *Q,QElemType e) QueuePtr p=(QueuePtr)malloc(sizeof(QNode);if(!p) / 存储分配失败 exit(0);/生成一个以为e为数据域的队列元素p->data=e;p->next=NULL;/将该新队列元素接在队尾的后面(*Q).rear->next=p;(*Q).rear=p;return 1;/ 若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0 int DeQueue(LinkQueue *Q,QElemType *e)QueuePtr p;if(*Q).front=

5、(*Q).rear)return 0;p=(*Q).front->next;/队头元素*e=p->data;(*Q).front->next=p->next;if(*Q).rear=p)(*Q).rear=(*Q).front;free(p);return 1;/ 构造树T int CreateTree(PTree *T) LinkQueue q;QElemType p,qq;int i=1,j,l;char cMAX_TREE_SIZE; / 临时存放孩子结点数组 InitQueue(&q); / 初始化队列 printf("请输入根结点(字符型,空

6、格为空): ");scanf("%c%*c",&(*T).nodes0.data); / 根结点序号为0,%*c吃掉回车符 if(*T).nodes0.data != Nil) / 非空树 (*T).nodes0.parent = -1; / 根结点无双亲 = (*T).nodes0.data;qq.num = 0;EnQueue(&q,qq); / 入队此结点 while(i < MAX_TREE_SIZE && !QueueEmpty(q) / 数组未满且队不空 DeQueue(&q,&qq

7、); / 出队一个结点 printf("请按长幼顺序输入结点%c的所有孩子: ",);gets(c);l=strlen(c);for(j=0;j<l;j+)(*T).nodesi.data=cj;(*T).nodesi.parent=qq.num;=cj;p.num=i;EnQueue(&q,p); / 入队此结点 i+;if(i>MAX_TREE_SIZE)printf("结点数超过数组容量n");exit(0);(*T).n=i;else(*T).n=0;return 1;#define ClearTre

8、e InitTree / 二者操作相同 / 若T为空树,则返回1,否则返回0int TreeEmpty(PTree T) if(T.n)return 0;elsereturn 1;/ 返回T的深度int TreeDepth(PTree T) int k,m,def,max=0;/存储深度for(k=0;k<T.n;+k)def=1; / 初始化本际点的深度 m = T.nodesk.parent;while(m != -1)m = T.nodesm.parent;def+;if(max < def)max = def;return max; / 最大深度 / 返回T的根TElemT

9、ype Root(PTree T) int i;for(i=0;i<T.n;i+)if(T.nodesi.parent < 0)return T.nodesi.data;return Nil;/ 返回第i个结点的值 TElemType Value(PTree T,int i)if(i<T.n)return T.nodesi.data;elsereturn Nil;/ 改cur_e为valueint Assign(PTree *T,TElemType cur_e,TElemType value)int j;for(j=0;j<(*T).n;j+)if(*T).nodesj

10、.data = cur_e)(*T).nodesj.data = value;return 1;return 0;/ 若cur_e是T的非根结点,则返回它的双亲,否则函数值为空TElemType Parent(PTree T,TElemType cur_e) int j;for(j=1; j < T.n;j+) / 根结点序号为0 if(T.nodesj.data = cur_e)return T.nodesT.nodesj.parent.data;return Nil;/ 若cur_e是T的非叶子结点,则返回它的最左孩子,否则返回空TElemType LeftChild(PTree T

11、,TElemType cur_e) int i,j;for(i=0;i<T.n;i+)if(T.nodesi.data = cur_e) / 找到cur_e,其序号为i break;for(j=i+1; j < T.n;j+)/ 根据树的构造函数,孩子的序号其双亲的序号 / 根据树的构造函数,最左孩子(长子)的序号其它孩子的序号 if(T.nodesj.parent = i)return T.nodesj.data;return Nil;/ 若cur_e有右(下一个)兄弟,则返回它的右兄弟,否则返回空 TElemType RightSibling(PTree T,TElemType

12、 cur_e)int i;for(i=0;i<T.n;i+)if(T.nodesi.data=cur_e) / 找到cur_e,其序号为i break;if(T.nodesi+1.parent = T.nodesi.parent)/ 根据树的构造函数,若cur_e有右兄弟的话则右兄弟紧接其后 return T.nodesi+1.data;return Nil;/ 输出树Tint Print(PTree T) int i;printf("结点个数=%dn",T.n);printf(" 结点 双亲n");for(i=0;i<T.n;i+)prin

13、tf(" %c",Value(T,i); / 结点 if(T.nodesi.parent>=0) / 有双亲 printf(" %c",Value(T,T.nodesi.parent); / 双亲 printf("n");return 1;/ 插入c为T中p结点的第i棵子树int InsertChild(PTree *T,TElemType p,int i,PTree c) int j,k,l,f=1,n=0; / 设交换标志f的初值为1,p的孩子数n的初值为0 PTNode t;if(!TreeEmpty(*T) / T不空

14、for(j=0;j<(*T).n;j+)/ 在T中找p的序号 if(*T).nodesj.data=p)/ p的序号为j break;l = j+1;/ 如果c是p的第1棵子树,则插在j+1处 if(i > 1) / c不是p的第1棵子树 for(k=j+1; k < (*T).n; k+) / 从j+1开始找p的前i-1个孩子 if(*T).nodesk.parent = j) / 当前结点是p的孩子 n+; / 孩子数加1 if(n = i-1) / 找到p的第i-1个孩子,其序号为k1 break;l = k+1; / c插在k+1处 / p的序号为j,c插在l处 if

15、(l < (*T).n) / 插入点l不在最后/ 依次将序号l以后的结点向后移c.n个位置 for(k=(*T).n-1; k >= l; k-)(*T).nodesk+c.n = (*T).nodesk;/向后移c.n个位置if(*T).nodesk.parent >= l)(*T).nodesk+c.n.parent+=c.n;for(k=0;k<c.n;k+)(*T).nodesl+k.data=c.nodesk.data; / 依次将树c的所有结点插于此处 (*T).nodesl+k.parent=c.nodesk.parent+l;(*T).nodesl.pa

16、rent=j; / 树c的根结点的双亲为p (*T).n+=c.n; / 树T的结点数加c.n个 while(f) / 从插入点之后,将结点仍按层序排列 f=0; / 交换标志置0 for(j=l; j < (*T).n-1; j+)if(*T).nodesj.parent > (*T).nodesj+1.parent)/ 如果结点j的双亲排在结点j+1的双亲之后(树没有按层序排/ 列),交换两结点t=(*T).nodesj;(*T).nodesj=(*T).nodesj+1;(*T).nodesj+1=t;f=1; / 交换标志置1 for(k=j;k<(*T).n;k+)

17、 / 改变双亲序号 if(*T).nodesk.parent=j)(*T).nodesk.parent+; / 双亲序号改为j+1 else if(*T).nodesk.parent=j+1)(*T).nodesk.parent-; / 双亲序号改为j return 1;else / 树T不存在 return 0;int deletedMAX_TREE_SIZE+1; / 删除标志数组(全局量) / 删除T中结点p的第i棵子树 void DeleteChild(PTree *T,TElemType p,int i) int j,k,n=0;LinkQueue q;QElemType pq,qq

18、;for(j=0;j<=(*T).n;j+)deletedj=0; / 置初值为0(不删除标记) ='a' / 此成员不用 InitQueue(&q); / 初始化队列 for(j=0;j<(*T).n;j+)if(*T).nodesj.data=p)break; / j为结点p的序号 for(k=j+1;k<(*T).n;k+)if(*T).nodesk.parent=j)n+;if(n=i)break; / k为p的第i棵子树结点的序号 if(k<(*T).n) / p的第i棵子树结点存在 n=0;pq.num=k;delete

19、dk=1; / 置删除标记 n+;EnQueue(&q,pq);while(!QueueEmpty(q)DeQueue(&q,&qq);for(j=qq.num+1;j<(*T).n;j+)if(*T).nodesj.parent=qq.num)pq.num=j;deletedj=1; / 置删除标记 n+;EnQueue(&q,pq);for(j=0;j<(*T).n;j+)if(deletedj=1)for(k=j+1;k<=(*T).n;k+)deletedk-1=deletedk;(*T).nodesk-1=(*T).nodesk;if

20、(*T).nodesk.parent>j)(*T).nodesk-1.parent-;j-;(*T).n-=n; / n为待删除结点数 / 层序遍历树T,对每个结点调用函数Visit一次且仅一次void TraverseTree(PTree T,void(*Visit)(TElemType) int i;for(i=0;i<T.n;i+)Visit(T.nodesi.data);printf("n");void vi(TElemType c) printf("%c ",c);int main()int i;PTree T,p;TElemTyp

21、e e,e1;InitTree(&T);printf("构造空树后,树空否? %d(1:是 0:否) 树根为%c 树的深度为%dn",TreeEmpty(T),Root(T),TreeDepth(T);CreateTree(&T);printf("构造树T后,树空否? %d(1:是 0:否) 树根为%c 树的深度为%dn",TreeEmpty(T),Root(T),TreeDepth(T);printf("层序遍历树T:n");TraverseTree(T,vi);printf("请输入待修改的结点的值 新值

22、: ");scanf("%c%*c%c%*c",&e,&e1);Assign(&T,e,e1);printf("层序遍历修改后的树T:n");TraverseTree(T,vi);printf("%c的双亲是%c,长子是%c,下一个兄弟是%cn", e1, Parent(T,e1),LeftChild(T,e1),RightSibling(T,e1);printf("建立树p:n");InitTree(&p);CreateTree(&p);printf("层序遍历树p:n");TraverseTree(p