《数据结构C语言版树的双亲表存储表示 (2)》由会员分享，可在线阅读，更多相关《数据结构C语言版树的双亲表存储表示 (2)（12页珍藏版）》请在金锄头文库上搜索。
1、数据结构 C 语言版 树的双亲表存储表示.txt 如果不懂就说出来，如果懂了，就笑笑别说出来。贪婪是最真实的贫穷，满足是最真实的财富。幽默就是一个人想哭的时候还有笑的兴致。/*数据结构 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 str
2、uctPTNode nodesMAX_TREE_SIZE; /存储结点的数组int n; / 结点数 PTree;typedef structint num;TElemType name;QElemType; / 定义队列元素类型 typedef struct QNodeQElemType data; /数据域struct QNode *next; /指针域QNode,*QueuePtr;typedef structQueuePtr front,/队头指针，指针域指向队头元素rear; /队尾指针，指向队尾元素LinkQueue;TElemType Nil= ; / 以空格符为空 int In
3、itTree(PTree *T) / 操作结果: 构造空树 T (*T).n=0;return 1;void DestroyTree() / 由于 PTree 是定长类型,无法销毁 / 构造一个空队列 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 Qu
4、eueEmpty(LinkQueue Q)if(Q.front=Q.rear)return 1;elsereturn 0;/ 插入元素 e 为 Q 的新的队尾元素int 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
5、 返回其值,并返回 1,否则返回 0 int DeQueue(LinkQueue *Q,QElemType *e)QueuePtr p;if(*Q).front=(*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
6、; / 临时存放孩子结点数组 InitQueue(&q); / 初始化队列 printf(请输入根结点(字符型,空格为空): );scanf(%c%*c,&(*T).nodes0.data); / 根结点序号为 0,%*c 吃掉回车符 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)printf(结点数超过数组容量n);exit(0);(*T)
7、.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;k=0) / 有双亲 printf( %c,Value(T,T.nodesi.parent); / 双亲 printf(n);return 1;/ 插入 c 为 T 中 p 结点的第 i 棵子树i
8、nt 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 = 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 (*T).
9、nodesj+1.parent)/ 如果结点 j 的双亲排在结点 j+1 的双亲之后(树没有按层序排/ 列),交换两结点t=(*T).nodesj;(*T).nodesj=(*T).nodesj+1;(*T).nodesj+1=t;f=1; / 交换标志置 1 for(k=j;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;i+)Visit(
10、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);printf(层序遍历树
11、 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,vi);p
12、rintf(将树 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 的所
13、有孩子: d请按长幼顺序输入结点 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结点 双亲ab ac ad bA bf cB A删除树 T 中结点 e 的第 i 棵子树，请输入 e i: a 1结点个数=3 结点 双亲ac af c请按任意键继续. . . */
