树和二叉树(一) 数据结构实验

《树和二叉树(一) 数据结构实验》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告五月142015姓名：陈斌学号：E11314079专业：13计算机科学与技术数据结构第三次实验学号E11314079专业计算机科学与技术姓名陈斌实验日期2015.05.14教师签字成绩实验报告【实验名称】树和二叉树（一）【实验目的】1.掌握二叉树的二叉链表存储表示；2.掌握二叉树的遍历算法；3.运用遍历算法求解有关问题。【实验内容】1.必做内容任务1：以算法6.4创建二叉树的存储结构，树的具体形态自定。任务2：对任务1中的二叉树分别实现先序、中序、后序遍历（递归实现）和中序遍历的非递归实现以及层序遍历；任

2、务3：统计1中树的结点总数、叶子结点总数以及树的高度；源代码：head.h:#include#include#include//malloc()#include//INT,MAX#include//EOF,NULL#include//atoi()#include//eof()#include//floor(),ceil(),abs()#include

3、//exit()#include//cout,cin//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1//OVERFLOW在math.h中已定义为3typedefintStatus;typedefintBoolean;//布尔类型head2.h:#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{SElemType*

4、base;SElemType*top;intstacksize;}SqStack;typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront,rear;/*队头、队尾指针*/}LinkQueue;StatusInitStack(SqStack&S){/*构造一个空栈S*/S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType

5、));if(!S.base)exit(OVERFLOW);/*存储分配失败*/S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusStackEmpty(SqStack&S){/*若栈S为空栈，则返回TRUE，否则返回FALSE*/if(S.top==S.base)returnTRUE;elsereturnFALSE;}StatusGetTop(SqStack&S,QElemType&e){/*若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERR

6、OR*/if(S.top>S.base){e=*(S.top-1);returnOK;}elsereturnERROR;}StatusPush(SqStack&S,QElemType&e){/*插入元素e为新的栈顶元素*/if(S.top-S.base>=S.stacksize)/*栈满，追加存储空间*/{S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLO

7、W);/*存储分配失败*/S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}StatusPop(SqStack&S,QElemType&e){/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}StatusInitQueue(LinkQueue&Q){/*构造一个空队列Q*/Q.fron

8、t=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;returnOK;}StatusQueueEmpty(LinkQueue&Q){/*若Q为空队列,则返回TRUE,否则返回FALSE*/if(Q.front==Q.rear)returnTRUE;el