数据结构C语言版-树的双亲表存储表示(共12页).doc

《数据结构C语言版-树的双亲表存储表示(共12页).doc》由会员分享，可在线阅读，更多相关《数据结构C语言版-树的双亲表存储表示(共12页).doc（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上/*数据结构C语言版 树的双亲表存储表示P135 编译环境：Dev-C+ 4.9.9.2日期：2011年2月13日 */#include typedef char TElemType;/ 树的双亲表存储表示 #define MAX_TREE_SIZE 100typedef structTElemType data;/数据域int parent;/ 双亲位置域 PTNode;/结点结构typedef structPTNode nodesMAX_TREE_SIZE;/存储结点的数组int n; / 结点数 PTree;typedef structint num;TElem

2、Type 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() / 由于PTree是定长类型,无法销

3、毁 / 构造一个空队列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 EnQueue(LinkQue

4、ue *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=(*Q).rear)return 0;p=(*Q).f

5、ront-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(请输入根结点(字符型,空格为空): );scanf(%c%*c,&(*T).nodes0.data); / 根结点序号为0,%*c

6、吃掉回车符 if(*T).nodes0.data != Nil) / 非空树 (*T).nodes0.parent = -1; / 根结点无双亲 qq.name = (*T).nodes0.data;qq.num = 0;EnQueue(&q,qq); / 入队此结点 while(i MAX_TREE_SIZE & !QueueEmpty(q) / 数组未满且队不空 DeQueue(&q,&qq); / 出队一个结点 printf(请按长幼顺序输入结点%c的所有孩子: ,qq.name);gets(c);l=strlen(c);for(j=0;jMAX_TREE_SIZE)printf(结点数

7、超过数组容量n);exit(0);(*T).n=i;else(*T).n=0;return 1;#define ClearTree 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;kT.n;+k)def=1; / 初始化本际点的深度 m = T.nodesk.parent;while(m != -1)m = T.nodesm.parent;def

8、+;if(max def)max = def;return max; / 最大深度 / 返回T的根TElemType Root(PTree T) int i;for(i=0;iT.n;i+)if(T.nodesi.parent 0)return T.nodesi.data;return Nil;/ 返回第i个结点的值 TElemType Value(PTree T,int i)if(iT.n)return T.nodesi.data;elsereturn Nil;/ 改cur_e为valueint Assign(PTree *T,TElemType cur_e,TElemType value)

9、int j;for(j=0;j(*T).n;j+)if(*T).nodesj.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的非叶子结点,则返回它的最左孩子

10、,否则返回空TElemType LeftChild(PTree T,TElemType cur_e) int i,j;for(i=0;iT.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 RightS

11、ibling(PTree T,TElemType cur_e)int i;for(i=0;iT.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=0) / 有双亲 printf( %

12、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不空 for(j=0;j 1) / c不是p的第1棵子树 for(k=j+1; k (*T).n; k+) / 从j+1开始找p的前i-1个孩子 if(*T).nodesk.parent = j) / 当前结

13、点是p的孩子 n+; / 孩子数加1 if(n = i-1) / 找到p的第i-1个孩子,其序号为k1 break;l = k+1; / c插在k+1处 / p的序号为j,c插在l处 if(l = 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;kc.n;k+)(*T).nodesl+k.data=c.nodesk.data; / 依次将树c的所有结点插于此处 (*T).nodesl+k.parent=c.nodesk.paren

14、t+l;(*T).nodesl.parent=j; / 树c的根结点的双亲为p (*T).n+=c.n; / 树T的结点数加c.n个 while(f) / 从插入点之后,将结点仍按层序排列 f=0; / 交换标志置0 for(j=l; j (*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+) / 改变双亲序号 if(*T).nodesk.parent

15、=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;for(j=0;j=(*T).n;j+)deletedj=

16、0; / 置初值为0(不删除标记) pq.name=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;deletedk=1; / 置删除标记 n+;EnQueue(&q,pq);while(!QueueEmpty(q)DeQueue

17、(&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;kj)(*T).nodesk-1.parent-;j-;(*T).n-=n; / n为待删除结点数 / 层序遍历树T,对每个结点调用函数Visit一次且仅一次void TraverseTree(PTree T,void(*Visit)(TElemType) int i;for(i=0;iT.n

18、;i+)Visit(T.nodesi.data);printf(n);void vi(TElemType c) printf(%c ,c);int main()int i;PTree T,p;TElemType 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);pri

19、ntf(层序遍历树T:n);TraverseTree(T,vi);printf(请输入待修改的结点的值 新值: );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,v

20、i);printf(将树p插到树T中，请输入T中p的双亲结点 子树序号: );scanf(%c%d%*c,&e,&i);InsertChild(&T,e,i,p);Print(T);printf(删除树T中结点e的第i棵子树，请输入e i: );scanf(%c%d,&e,&i);DeleteChild(&T,e,i);Print(T);system(pause);return 0;/*输出效果：构造空树后,树空否? 1(1:是 0:否) 树根为 树的深度为0请输入根结点(字符型,空格为空): a请按长幼顺序输入结点a的所有孩子: bc请按长幼顺序输入结点b的所有孩子: d请按长幼顺序输入结点

21、c的所有孩子: e请按长幼顺序输入结点d的所有孩子:请按长幼顺序输入结点e的所有孩子:构造树T后,树空否? 0(1:是 0:否) 树根为a 树的深度为3层序遍历树T:a b c d e请输入待修改的结点的值 新值: e f层序遍历修改后的树T:a b c d ff的双亲是c,长子是 ,下一个兄弟是建立树p:请输入根结点(字符型,空格为空): A请按长幼顺序输入结点A的所有孩子: B请按长幼顺序输入结点B的所有孩子:层序遍历树p:A B将树p插到树T中，请输入T中p的双亲结点 子树序号: b 2结点个数=7 结点 双亲 a b a c a d b A b f c B A删除树T中结点e的第i棵子树，请输入e i: a 1结点个数=3 结点 双亲 a c a f c请按任意键继续. . . */专心-专注-专业