二叉树后序遍历-数据结构实验.doc

《二叉树后序遍历-数据结构实验.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《算法与数据结构》试验报告[六]专业班级试验地点学生学号指导教师学生姓名试验时间试验项目算法与数据结构试验类别基础性（）设计性（）综合性（√）其它（）试验目的及要求（1）掌握用VC++上机调试线性表的基本方法；（2）掌握顺序表的存储结构以及基本运算的实现。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律主动完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分备注：评阅教师：日期：年月日试验内容一、实验目的和要求1、实验目的：（1）针对问题的实际要求，正确应用树形结构组织和存储数据；（2）掌握二叉树的

2、存储方法。（3）掌握二叉树的各种遍历方法。2、实验内容:二叉树后序遍历的非递归算法。3、实验说明：二叉树后序遍历的非递归算法：结点要入两次栈，出两次栈；为了区别同一个结点的两次出栈，设置标志flag，当结点进、出栈时，其标志flag也同时进、出栈。1第一次出栈，只遍历完左子树，该结点不能访问2第二次出栈，遍历完右子树，该结点可以访问flag＝设根指针为root，则可能有以下两种情况：⑴若root!=NULL，则root及标志flag（置为1）入栈，遍历其左子树；⑵若root=NULL，此时若栈空，则整个遍历结束；若栈不空，则表明栈顶结点

3、的左子树或右子树已遍历完毕。若栈顶结点的标志flag=1，则表明栈顶结点的左子树已遍历完毕，将flag修改为2，并遍历栈顶结点的右子树；若栈顶结点的标志flag=2，则表明栈顶结点的右子树也遍历完毕，输出栈顶结点。二叉树后序遍历的非递归算法伪代码如下：1.栈s初始化；2.循环直到root为空且栈s为空2.1当root非空时循环2.1.1将root连同标志flag=1入栈；2.1.2继续遍历root的左子树；2.2当栈s非空且栈顶元素的标志为2时，出栈并输出栈顶结点;2.3若栈非空，将栈顶元素的标志改为2，准备遍历栈顶结点的右子树；二、设

4、计分析在输入二叉树时，按照先序的顺序来进行构建，若输入’#’表示该点为空不存在，每个孩子节点都必须有数据不管它是否为空，后续遍历函数则利用了非递归算法按照了实验指导，加入了上述算法。三、源程序代码#include#include#includestructtree{chardata;structtree*lchild;structtree*rchild;};typedefstructtree*treptr;treptrbuild(treptrt)//先序建树{charc;c=ge

5、tchar();if(c=='#'){t=NULL;}else{t=(treptr)malloc(sizeof(structtree));t->data=c;t->lchild=build(t->lchild);t->rchild=build(t->rchild);}returnt;}voidpostdorder(treptrroot){if(root!=NULL){postdorder(root->lchild);postdorder(root->rchild);printf("%c",root->data);}}structstac

6、k{treptr*top,*base;};typedefstructstack*stackptr;voidinit(stackptrs)//初始化栈{s->base=(treptr*)malloc(sizeof(treptr)*100);s->top=s->base;}voidpush(stackptrs,treptrt)//入栈{*(s->top++)=t;}treptrpop(stackptrs)//弹出栈顶元素{treptrt;t=*(--(s->top));returnt;}treptrgettop(stackptrs)//取栈

7、顶元素{treptr*l=s->top-1;return*(l);}voidpostorder(treptrt)//这是非递归后序实现{stackptrs=(stackptr)malloc(sizeof(structstack));treptrtemp=t;treptrp;treptrlastvist=NULL;init(s);p=t;while(p

8、

9、s->top!=s->base){while(p){push(s,p);p=p->lchild;}temp=gettop(s);if(temp->rchild==NULL

10、

11、temp->

12、rchild==lastvist){putchar(temp->data);lastvist=pop(s);}elsep=temp->rchild;}}intmain(){treptrt=NULL;prin