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

《算法与数据结构》试验报告[六]专业班级试验地点学生学号指导教师学生姓名试验时间试验项目算法与数据结构试验类别基础性（）设计性（）综合性（√）其它（）试验目的及要求（1）掌握用VC++上机调试线性表的基本方法；（2）掌握顺序表的存储结构以及基本运算的实现。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律主动完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分备注：评阅教师：日期：年月日试验内容一、实验目的和要求1、实验目的：（1）针对问题的实际要求，正确应用树形结构组织和存储数据；（2）掌握二叉树的存储方法。（3）掌握二叉树的各种遍历方法。计算机科学与工程学院《算法与数据结构》试验报告22、实验内容:二叉树后序遍历的非递归算法。3、实验说明：二叉树后序遍历的非递归算法：结点要入两次栈，出两次栈；为了区别同一个结点的两次出栈，设置标志flag，当结点进、出栈时，其标志flag也同时进、出栈。设根指针为root，则可能有以下两种情况：⑴若root!=NULL，则root及标志flag（置为1）入栈，遍历其左子树；⑵若root=NULL，此时若栈空，则整个遍历结束；若栈不空，则表明栈顶结点的左子树或右子树已遍历完毕。若栈顶结点的标志flag=1，则表明栈顶结点的左子树已遍历完毕，将flag修改为2，并遍历栈顶结点的右子树；若栈顶结点的标志flag=2，则表明栈顶结点的右子树也遍历完毕，输出栈顶结点。二叉树后序遍历的非递归算法伪代码如下：二、设计分析在输入二叉树时，按照先序的顺序来进行构建，若输入’#’表示该点为空不存在，每个孩子节点都必须有数据不管它是否为空，后续遍历函数则利用了非递归算法按照了实验指导，加入了上述算法。三、源程序代码#includestdio.h#includeiostream#includestdlib.hstructtree{chardata;structtree*lchild;structtree*rchild;};typedefstructtree*treptr;treptrbuild(treptrt)//先序建树{charc;c=getchar();if(c=='#')1第一次出栈，只遍历完左子树，该结点不能访问2第二次出栈，遍历完右子树，该结点可以访问flag＝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，准备遍历栈顶结点的右子树；计算机科学与工程学院《算法与数据结构》试验报告3{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);}}structstack{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)//取栈顶元素{计算机科学与工程学院《算法与数据结构》试验报告4treptr*l=s-top-1;return*(l);}voidpostorder(treptrt)//这是非递归后序实现{stackptrs=(stackptr)malloc(sizeof(structstack));treptrtemp=t;treptrp;treptrlastvist=NULL;init(s);p=t;while(p||s-top!=s-base){while(p){push(s,p);p=p-lchild;}temp=gettop(s);if(temp-rchild==NULL||temp-rchild==lastvist){putchar(temp-data);lastvist=pop(s);}elsep=temp-rchild;}}intmain(){treptrt=NULL;printf(请输入需要遍历的二叉树：\n);t=build(t);postdorder(t);printf(非递归后序遍历\n);postorder(t);printf(\n);return0;}四、测试用例1.该数为空，用只有一个节点且为空计算机科学与工程学院《算法与数据结构》试验报告5此时没有节点，无法遍历。2。普通的树3.树中只有一个根节点设为1，两个孩子节点分别设为2和3先序为123，后序遍历五、实验总结这一次实验是二叉树的后序遍历，创建树的时候为先序创建。运用了刚刚学习过的二叉树的相关知识。什么知识都是在实践中加深理解，更好地掌握。这次实验很困难，树的遍历算法很难写，老师让我们要多加讨论，通过和同学的讨论，一些问题迎刃而解，各个问题逐步击破，此外还参考了相关书籍和上网查资料。每一次的实验都能然我收获很多，我觉得树是一个很总要的数据结构，一定要好好掌握。