20151009-数据结构实验报告3

《20151009-数据结构实验报告3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告课程名称数据结构实验项目实验三--创建一个二叉树并输出三种遍历结果系别____计算机学院_______专业____计算机大类___班级/学号_____(1406/2014011288)____学生姓名_______孙文学___________实验日期_（2015年11月25日）成绩_______________________指导教师黄改娟实验题目：实验三------创建一个二叉树并输出三种遍历结果一、实验目的1)掌握二叉树存储结构；2)掌握并实现二叉树遍历的递归算法和非递归算法；3)理解树及森林对二叉树的转换；4)理解二叉树的应用—哈夫曼编码及WPL计算。二、实验内容1)以广义表或遍

2、历序列形式创建一个二叉树，存储结构自选；2)输出先序、中序、后序遍历序列；3)二选一应用题：1）树和森林向二叉树转换；2）哈夫曼编码的应用问题。（应用型题目可替换上述前两项实验内容）三、设计与编码1)实验题目及主要存储结构定义（提示：请根据所选定题目，描述主要存储结构，语言不限）题目：创建一个二叉树并输出三种遍历结果存储结构：typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;2)结合题目，说明利用栈或队列解决问题的基本算法描述（提示：可用自然语言、流程图、伪代码等均可，要求对每一个操

3、作，都给出具体的算法描述）非递归先序遍历：stacks;BiTNode*p=T;while(p!=NULL

4、

5、!s.empty()){while(p!=NULL){cout<data;s.push(p);p=p->lchild;}if(!s.empty()){p=s.top();s.pop();p=p->rchild;}}非递归中序遍历：stacks;BiTNode*p=T;while(p!=NULL

6、

7、!s.empty()){while(p!=NULL){s.push(p);p=p->lchild;}if(!s.empty()){p=s.top

8、();cout<data;s.pop();p=p->rchild;}}非递归后序遍历：stacks;BiTNode*cur;//当前结点BiTNode*pre=NULL;//前一次访问的结点s.push(T);while(!s.empty()){cur=s.top();if((cur->lchild==NULL&&cur->rchild==NULL)

9、

10、(pre!=NULL&&(pre==cur->lchild

11、

12、pre==cur->rchild))){cout<data;//如果当前结点没有孩子结点或者孩子节点都已被访问过s.pop();pre=cur

13、;}else{if(cur->rchild!=NULL)s.push(cur->rchild);if(cur->lchild!=NULL)s.push(cur->lchild);}}1)程序源码（提示：列出所编写程序的代码。如果利用图形界面IDE等编程，这里只要求写出关键操作的程序代码。此外，程序一定要有注释说明）#include#include#includeusingnamespacestd;#defineOK1#defineERROR0#defineOVERFLOW-2typedefintStatus;typedefcharTElem

14、Type;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreeCreateBiTree(){//创建树BiTreeT;charch;cin>>ch;if(ch=='#')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;T->lchild=CreateBiTree();T->rchild=CreateBiTree();}returnT;}voidPreDTraver

15、se(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->rchil