20151009-数据结构实验报告3

实验报告课程名称数据结构实验项目实验三--创建一个二叉树并输出三种遍历结果系别____计算机学院_______专业____计算机大类___班级/学号_____(1406/2014011288)____学生姓名_______孙文学___________实验日期_（2015年11月25日）成绩_______________________指导教师黄改娟实验题目：实验三------创建一个二叉树并输出三种遍历结果一、实验目的1)掌握二叉树存储结构；2)掌握并实现二叉树遍历的递归算法和非递归算法；3)理解树及森林对二叉树的转换；4)理解二叉树的应用—哈夫曼编码及WPL计算。二、实验内容1)以广义表或遍历序列形式创建一个二叉树，存储结构自选；2)输出先序、中序、后序遍历序列；3)二选一应用题：1）树和森林向二叉树转换；2）哈夫曼编码的应用问题。（应用型题目可替换上述前两项实验内容）三、设计与编码1)实验题目及主要存储结构定义（提示：请根据所选定题目，描述主要存储结构，语言不限）题目：创建一个二叉树并输出三种遍历结果存储结构：typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;2)结合题目，说明利用栈或队列解决问题的基本算法描述（提示：可用自然语言、流程图、伪代码等均可，要求对每一个操作，都给出具体的算法描述）非递归先序遍历：stackBiTNode*s;BiTNode*p=T;while(p!=NULL||!s.empty()){while(p!=NULL){coutp-data;s.push(p);p=p-lchild;}if(!s.empty()){p=s.top();s.pop();p=p-rchild;}}非递归中序遍历：stackBiTNode*s;BiTNode*p=T;while(p!=NULL||!s.empty()){while(p!=NULL){s.push(p);p=p-lchild;}if(!s.empty()){p=s.top();coutp-data;s.pop();p=p-rchild;}}非递归后序遍历：stackBiTNode*s;BiTNode*cur;//当前结点BiTNode*pre=NULL;//前一次访问的结点s.push(T);while(!s.empty()){cur=s.top();if((cur-lchild==NULL&&cur-rchild==NULL)||(pre!=NULL&&(pre==cur-lchild||pre==cur-rchild))){coutcur-data;//如果当前结点没有孩子结点或者孩子节点都已被访问过s.pop();pre=cur;}else{if(cur-rchild!=NULL)s.push(cur-rchild);if(cur-lchild!=NULL)s.push(cur-lchild);}}3)程序源码（提示：列出所编写程序的代码。如果利用图形界面IDE等编程，这里只要求写出关键操作的程序代码。此外，程序一定要有注释说明）#includeiostream#includestack#includestdlib.husingnamespacestd;#defineOK1#defineERROR0#defineOVERFLOW-2typedefintStatus;typedefcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreeCreateBiTree(){//创建树BiTreeT;charch;cinch;if(ch=='#')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T-data=ch;T-lchild=CreateBiTree();T-rchild=CreateBiTree();}returnT;}voidPreDTraverse(BiTreeT){//递归先序遍历if(T){printf(%c,T-data);PreDTraverse(T-lchild);PreDTraverse(T-rchild);}}voidInDTraverse(BiTreeT){//递归中序遍历if(T){InDTraverse(T-lchild);printf(%c,T-data);InDTraverse(T-rchild);}}voidPostDTraverse(BiTreeT){//递归后序遍历if(T){PostDTraverse(T-lchild);PostDTraverse(T-rchild);printf(%c,T-data);}}voidPreTraverse(BiTNode*T)//非递归先序遍历{stackBiTNode*s;BiTNode*p=T;while(p!=NULL||!s.empty()){while(p!=NULL){coutp-data;s.push(p);p=p-lchild;}if(!s.empty()){p=s.top();s.pop();p=p-rchild;}}}voidInTraverse(BiTNode*T)//非递归中序遍历{stackBiTNode*s;BiTNode*p=T;while(p!=NULL||!s.empty()){while(p!=NULL){s.push(p);p=p-lchild;}if(!s.empty()){p=s.top();coutp-data;s.pop();p=p-rchild;}}}voidPostTraverse(BiTNode*T)//非递归后序遍历{stackBiTNode*s;BiTNode*cur;//当前结点BiTNode*pre=NULL;//前一次访问的结点s.push(T);while(!s.empty()){cur=s.top();if((cur-lchild==NULL&&cur-rchild==NULL)||(pre!=NULL&&(pre==cur-lchild||pre==cur-rchild))){coutcur-data;//如果当前结点没有孩子结点或者孩子节点都已被访问过s.pop();pre=cur;}else{if(cur-rchild!=NULL)s.push(cur-rchild);if(cur-lchild!=NULL)s.push(cur-lchild);}}}voidtips(){printf(输入1执行递归先序遍历：\n);printf(输入2执行递归中序遍历：\n);printf(输入3执行递归后序遍历：\n);printf(输入4执行非递归先序遍历：\n);printf(输入5执行非递归中序遍历：\n);printf(输入6执行非递归后序遍历：\n);printf(输入0结束程序：\n);}voidmain(){//主函数intop;BiTreeT;printf(输入数据以创建二叉树，“#”代表空树:\n);T=CreateBiTree();tips();cinop;while(op){switch(op){case1:PreDTraverse(T);break;case2:InDTraverse(T);break;case3:PostDTraverse(T);break;case4:PreTraverse(T);break;case5:InTraverse(T);break;case6:PostTraverse(T);break;}printf(\n);system(pause);system(cls);tips();cinop;}}4)运行结果（提示：运行结果要求能反应每一种操作前后的结果变化情况）四、总结与心得实验完成后的总结与思考，或者谈收获，关键是把算法设计和编程实现中的问题如何解决的说明出来。（注意此部分要结合自己的题目来阐述说明）学会了二叉树的创建与三种遍历，其中三种遍历的递归实现比较简单，但非递归算法实现比较复杂，我用到了栈。