计算机科学与工程学院
《算法与数据结构》实验报告(六)
专业班级 学生学号 学生姓名 实验项目 实验类别 2013网络工程01 树的应用 基础性（） 设计性（√） 综合性（） 其它（ ） （1）针对问题的实际要求，正确应用树形结构组织和存储数据； （2）掌握二叉树的存储方法。 （3）掌握二叉树的各种遍历方法。 实验地点 指导教师 实验时间 423机房 赵卿松 实验目的及要求 成 绩 评 定 表 类 别 上机表现 评 分 标 准 积极出勤、遵守纪律 按要求完成设计任务 程序代码规范、功能正确 报告详实完整、体现收获 分值 30分 得分 70分 合 计 程序与报告 说明： 计算机科学与工程学院
评阅教师： 赵卿松 日 期： 2015 年 5 月 23 日 实 验 内 容 《算法与数据结构》实验报告 2
计算机科学与工程学院
实验内容: 二叉树后序遍历的非递归算法。 实验说明： 二叉树后序遍历的非递归算法：结点要入两次栈，出两次栈；为了区别同一个结点的两次出栈，设置标志flag，当结点进、出栈时，其标志flag也同时进、出栈。 1 第一次出栈，只遍历完左子树，该结点不能访问 flag＝ 2 第二次出栈，遍历完右子树，该结点可以访问 设根指针为root，则可能有以下两种情况： ⑴ 若root!=NULL，则root及标志flag（置为1）入栈，遍历其左子树； ⑵ 若root=NULL，此时若栈空，则整个遍历结束；若栈不空，则表明栈顶结点的左子树或右子树已遍历完毕。若栈顶结点的标志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，准备遍历栈顶结点的右子树； 实 验 内 容 《算法与数据结构》实验报告
3
计算机科学与工程学院
#include #include #define MaxSize 100 typedef struct node { char data; struct node *lchild; struct node *rchild; }BTNode; //二叉树数据结构定义 void CreateBTNode(BTNode *&b,char *str) //创建二叉树 { BTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0; char ch; b=NULL; ch=str[j]; while(ch!='\\0') { switch(ch) { case '(':top++;St[top]=p;k=1;break; case ')':top--;break; 《算法与数据结构》实验报告4
计算机科学与工程学院
case ',':k=2;break; default:p=(BTNode *)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(b==NULL) b=p; else { switch(k) { case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++; ch=str[j]; } } void PostOrder(BTNode *b) //二叉树的后序遍历的递归算法 { if(b!=NULL) { 《算法与数据结构》实验报告
5
计算机科学与工程学院
PostOrder(b->lchild); PostOrder(b->rchild); printf(\"%c\ } } void PostOrder1(BTNode *b) { BTNode *St[MaxSize]; BTNode *p; int flag,top=-1; if(b!=NULL) { do { while(b!=NULL) { top++; St[top]=b; b=b->lchild; } p=NULL; 《算法与数据结构》实验报告
6
计算机科学与工程学院
flag=1; while(top!=-1&&flag) { b=St[top]; if(b->rchild==p) { printf(\"%c\ top--; p=b; } else { b=b->rchild; flag=0; } } }while(top!=-1); printf(\"\\n\"); } } void main() 《算法与数据结构》实验报告
7
计算机科学与工程学院
{ char a[MaxSize]; printf(\"请输入二叉树：\\n\"); scanf(\"%s\ BTNode *b; CreateBTNode(b,a); printf(\"该二叉树经过后序遍历得到的输出序列为：\\n\"); PostOrder1(b); } 实 验 内 容 《算法与数据结构》实验报告
8
