C++二叉树基本操作实验报告.doc

《C++二叉树基本操作实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、实验目的选择二叉链式存储结构作为二叉树的存储结构，设计一个程序实现二叉树的基本操作（包括建立、输出、前序遍历、中序遍历、后序遍历、求树高、统计叶子总数等）二、实验开发环境Windows8.1中文版MicrosoftVisualStudio6.0三、实验内容程序的菜单功能项如下：1------建立一棵二叉树2------前序遍历递归算法3------前序遍历非递归算法4------中序遍历递归算法5------中序遍历非递归算法6------后序遍历递归算法7------后序遍历非递归算法8------求树高9------求叶子总

2、数10-----输出二叉树11-----退出四、实验分析1、建立一棵二叉树2、输入二叉树各节点数据cout<<"请按正确顺序输入二叉树的数据:";cin.getline(t,1000);//先把输入的数据输入到一个t数组3、递归前序遍历voidBL1(ECS_datat){if(NULL!=t){cout<data<<",";BL1(t->l);BL1(t->r);}}4、非递归前序遍历voidpreOrder2(ECS_datat){stacks;ECS_datap=t;while(p!=NULL!s.

3、empty()){while(p!=NULL){cout<data<<"";s.push(p);p=p->l;}if(!s.empty()){p=s.top();s.pop();p=p->r;}}}5、递归中序遍历voidBL2(ECS_datat){if(NULL!=t){BL2(t->l);cout<data<<",";BL2(t->r);}}6、非递归中序遍历voidinOrder2(ECS_datat)//非递归中序遍历{stacks;ECS_datap=t;while(p!=NULL!s

4、.empty()){while(p!=NULL){s.push(p);p=p->l;}if(!s.empty()){p=s.top();cout<data<<"";s.pop();p=p->r;}}}7、递归后序遍历voidBL3(ECS_datat){if(NULL!=t){BL3(t->l);BL3(t->r);cout<data<<",";}}8、非递归后序遍历voidpostOrder3(ECS_datat){stacks;ECS_datacur;//当前结点ECS_datapre=NUL

5、L;//前一次访问的结点s.push(t);while(!s.empty()){cur=s.top();if((cur->l==NULL&&cur->r==NULL)(pre!=NULL&&(pre==cur->lpre==cur->r))){cout<data<<"";//如果当前结点没有孩子结点或者孩子节点都已被访问过s.pop();pre=cur;}else{if(cur->r!=NULL)s.push(cur->r);if(cur->l!=NULL)s.push(cur->l);}}}9、求树高intHeight

6、(ECS_datat){if(t==NULL)return0;else{intm=Height(t->l);intn=Height(t->r);return(m>n)?(m+1):(n+1);}}10、求叶子总数intCountLeaf(ECS_datat){staticintLeafNum=0;//叶子初始数目为0，使用静态变量if(t)//树非空{if(t->l==NULL&&t->r==NULL)//为叶子结点LeafNum++;//叶子数目加1else//不为叶子结点{CountLeaf(t->l);//递归统计左子树叶子数

7、目CountLeaf(t->r);//递归统计右子树叶子数目}}returnLeafNum;}五、运行结果附：完整程序源代码：//二叉树链式存储的实现#include#include#includeusingnamespacestd;structECS_data//先定义好一个数据的结构{chardata;ECS_datal;ECS_datar;};classECS{private://intlevel;//树高intn;//表示有多少个节点数intn1;//表示的是数组的总长度值

8、，（包括#）,因为后面要进行删除判断ECS_datatemp[1000];public:ECS_dataroot;ECS()//初始化{ECS_datap;chart[1000];inti;intfront=0,rear=1;//fr