资源描述:
《c语言数据结构树双亲表示法实例分析》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、C语言数据结构树双亲表示法实例分析 树状图是一种数据结构,它是由n(n=1)个有限节点组成一个具有层次关系的集合。以下是职场百科网小编搜索整理的关于C语言数据结构树双亲表示法实例分析,需要的朋友可以参考一下!想了解更多相关信息请持续关注我们应届毕业生考试网! 1、树的双亲表示法: 树的双亲表示法 2、/*bo6-4.c树的双亲表存储(存储结构由c6-4.h定义)的基本操作(14个)*/ StatusInitTree(PTree*T) {/*操作结果:构造空树T*/ (*T).n=0; returnOK; } void19D
2、estroyTree() {/*由于PTree是定长类型,无法销毁*/ } typedefstruct { intnum; TElemTypename; }QElemType;/*定义队列元素类型*/ #include"c3-2.h/*定义LinkQueue类型*/ #include"bo3-2.c/*LinkQueue类型的基本操作*/ StatusCreateTree(PTree*T) {/*操作结果:构造树T*/ LinkQueueq; QElemTypep,qq; inti=1,j,l;
3、 charc[MAX_TREE_SIZE];/*临时存放孩子结点数组*/ InitQueue(&q);/*初始化队列*/ printf("请输入根结点(字符型,空格为空):"); scanf("%c%*c",&(*T).nodes[0].data);/*19根结点序号为0,%*c吃掉回车符*/ if((*T).nodes[0].data!=Nil)/*非空树*/ { (*T).nodes[0].parent=-1;/*根结点无双亲*/ qq.name=(*T).nodes
4、[0].data; qq.num=0; EnQueue(&q,qq);/*入队此结点*/ while(iMAX_TREE_SIZE&&!QueueEmpty(q))/*数组未满且队不空*/ { DeQueue(&q,&qq);/*出队一个结点*/ printf("请按长幼顺序输入结点%c的所有孩子:19",qq.name); gets(c); l=strlen(c); for(j=0;jl;j++) { (*T).nodes[i].data=c[j]; (*T
5、).nodes[i].parent=qq.num; p.name=c[j]; p.num=i; EnQueue(&q,p);/*入队此结点*/ i++; } } if(iMAX_TREE_SIZE) { printf("结点数超过数组容量"); exit(OVERFLOW); } (*T).n=i; } else (*T).n=0; returnOK; } #defineClearTreeInitTree/*二者操作相同*/ StatusTreeEmpty(PTreeT) {
6、/*初始条件:树T存在。操作结果:若T为空树,则返回TRUE,否则返回FALSE*/ if(T.n) return19FALSE; else returnTRUE; } intTreeDepth(PTreeT) {/*初始条件:树T存在。操作结果:返回T的深度*/ intk,m,def,max=0; for(k=0;kT.n;++k) { def=1;/*初始化本际点的深度*/ m=T.nodes[k].parent; while(m!=-1) { m=T.nodes[m].parent; def++; }
7、 if(maxdef) max=def; } returnmax;/*最大深度*/ } TElemTypeRoot(PTreeT) {/*初始条件:树T存在。操作结果:返回T的根19*/ inti; for(i=0;iT.n;i++) if(T.nodes[i].parent0) returnT.nodes[i].data; returnNil; } TElemTypeValue(PTreeT,inti) {/*初始条件:树T存在,i是树T中结点的序号。操作结果:返回第i个结点的值*/ if(iT.n) ret
8、urnT.nodes[i].data; else returnNil; } StatusAssign(PTree*T,TElemTypecur_e,TEle