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

《数据结构C语言版-树的双亲表存储表示.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、/*数据结构C语言版树的双亲表存储表示P135编译环境：Dev-C++4.9.9.2日期：2011年2月13日*/#includetypedefcharTElemType;//树的双亲表存储表示#defineMAX_TREE_SIZE100typedefstruct{TElemTypedata;//数据域intparent;//双亲位置域}PTNode;//结点结构typedefstruct{PTNodenodes[MAX_TREE_SIZE];//存储结点的数组intn;//结点

2、数}PTree;typedefstruct{intnum;TElemTypename;}QElemType;//定义队列元素类型typedefstructQNode{QElemTypedata;//数据域structQNode*next;//指针域}QNode,*QueuePtr;typedefstruct{QueuePtrfront,//队头指针，指针域指向队头元素rear;//队尾指针，指向队尾元素}LinkQueue;TElemTypeNil='';//以空格符为空intInitTree(PT

3、ree*T){//操作结果:构造空树T(*T).n=0;return1;}voidDestroyTree(){//由于PTree是定长类型,无法销毁}//构造一个空队列QintInitQueue(LinkQueue*Q){(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));//动态分配一个空间if(!(*Q).front)exit(0);(*Q).front->next=NULL;//队头指针指向空，无数据域，这样构成了一个空队列return1;

4、}//若Q为空队列,则返回1,否则返回0intQueueEmpty(LinkQueueQ){if(Q.front==Q.rear)return1;elsereturn0;}//插入元素e为Q的新的队尾元素intEnQueue(LinkQueue*Q,QElemTypee){QueuePtrp=(QueuePtr)malloc(sizeof(QNode));if(!p)//存储分配失败exit(0);//生成一个以为e为数据域的队列元素p->data=e;p->next=NULL;//将该新队列元素接

5、在队尾的后面(*Q).rear->next=p;(*Q).rear=p;return1;}//若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0intDeQueue(LinkQueue*Q,QElemType*e){QueuePtrp;if((*Q).front==(*Q).rear)return0;p=(*Q).front->next;//队头元素*e=p->data;(*Q).front->next=p->next;if((*Q).rear==p)(*Q).rear=(*Q).fr

6、ont;free(p);return1;}//构造树TintCreateTree(PTree*T){LinkQueueq;QElemTypep,qq;inti=1,j,l;charc[MAX_TREE_SIZE];//临时存放孩子结点数组InitQueue(&q);//初始化队列printf("请输入根结点(字符型,空格为空):");scanf("%c%*c",&(*T).nodes[0].data);//根结点序号为0,%*c吃掉回车符if((*T).nodes[0].data!=Nil)//非空

7、树{(*T).nodes[0].parent=-1;//根结点无双亲qq.name=(*T).nodes[0].data;qq.num=0;EnQueue(&q,qq);//入队此结点while(i

8、.data=c[j];(*T).nodes[i].parent=qq.num;p.name=c[j];p.num=i;EnQueue(&q,p);//入队此结点i++;}}if(i>MAX_TREE_SIZE){printf("结点数超过数组容量");exit(0);}(*T).n=i;}else(*T).n=0;return1;}#defineClearTreeInitTree//二者操作相同//若T为空树,则返回1,否则返回0intTreeEmpty(PTre