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

一、实验目的选择二叉链式存储结构作为二叉树的存储结构，设计一个程序实现二叉树的基本操作（包括建立、输出、前序遍历、中序遍历、后序遍历、求树高、统计叶子总数等）二、实验开发环境Windows8.1中文版MicrosoftVisualStudio6.0三、实验内容程序的菜单功能项如下：1------建立一棵二叉树2------前序遍历递归算法3------前序遍历非递归算法4------中序遍历递归算法5------中序遍历非递归算法6------后序遍历递归算法7------后序遍历非递归算法8------求树高9------求叶子总数10-----输出二叉树11-----退出四、实验分析1、建立一棵二叉树2、输入二叉树各节点数据cout请按正确顺序输入二叉树的数据:;cin.getline(t,1000);//先把输入的数据输入到一个t数组3、递归前序遍历voidBL1(ECS_data*t){if(NULL!=t){coutt-data,;BL1(t-l);BL1(t-r);}}4、非递归前序遍历voidpreOrder2(ECS_data*t){stackECS_data*s;ECS_data*p=t;while(p!=NULL||!s.empty()){while(p!=NULL){coutp-data;s.push(p);p=p-l;}if(!s.empty()){p=s.top();s.pop();p=p-r;}}}5、递归中序遍历voidBL2(ECS_data*t){if(NULL!=t){BL2(t-l);coutt-data,;BL2(t-r);}}6、非递归中序遍历voidinOrder2(ECS_data*t)//非递归中序遍历{stackECS_data*s;ECS_data*p=t;while(p!=NULL||!s.empty()){while(p!=NULL){s.push(p);p=p-l;}if(!s.empty()){p=s.top();coutp-data;s.pop();p=p-r;}}}7、递归后序遍历voidBL3(ECS_data*t){if(NULL!=t){BL3(t-l);BL3(t-r);coutt-data,;}}8、非递归后序遍历voidpostOrder3(ECS_data*t){stackECS_data*s;ECS_data*cur;//当前结点ECS_data*pre=NULL;//前一次访问的结点s.push(t);while(!s.empty()){cur=s.top();if((cur-l==NULL&&cur-r==NULL)||(pre!=NULL&&(pre==cur-l||pre==cur-r))){coutcur-data;//如果当前结点没有孩子结点或者孩子节点都已被访问过s.pop();pre=cur;}else{if(cur-r!=NULL)s.push(cur-r);if(cur-l!=NULL)s.push(cur-l);}}}9、求树高intHeight(ECS_data*t){if(t==NULL)return0;else{intm=Height(t-l);intn=Height(t-r);return(mn)?(m+1):(n+1);}}10、求叶子总数intCountLeaf(ECS_data*t){staticintLeafNum=0;//叶子初始数目为0，使用静态变量if(t)//树非空{if(t-l==NULL&&t-r==NULL)//为叶子结点LeafNum++;//叶子数目加1else//不为叶子结点{CountLeaf(t-l);//递归统计左子树叶子数目CountLeaf(t-r);//递归统计右子树叶子数目}}returnLeafNum;}五、运行结果附：完整程序源代码：//二叉树链式存储的实现#includeiostream#includecstring#includestackusingnamespacestd;structECS_data//先定义好一个数据的结构{chardata;ECS_data*l;ECS_data*r;};classECS{private://intlevel;//树高intn;//表示有多少个节点数intn1;//表示的是数组的总长度值，（包括#）,因为后面要进行删除判断ECS_data*temp[1000];public:ECS_data*root;ECS()//初始化{ECS_data*p;chart[1000];inti;intfront=0,rear=1;//front表示有多少个节点，rear表示当前插入的点的父母cout请按正确顺序输入二叉树的数据:;cin.getline(t,1000);//先把输入的数据输入到一个t数组//couttendl;intn1=strlen(t);//测量数据的长度n=0;for(i=0;in1;i++){if(t[i]!='#'){p=NULL;if(t[i]!=',')//满足条件并开辟内存{n++;p=newECS_data;p-data=t[i];p-l=NULL;p-r=NULL;}front++;temp[front]=p;if(1==front){root=p;}else{if((p!=NULL)&&(0==front%2)){temp[rear]-l=p;//刚开始把这里写成了==}if((p!=NULL)&&(1==front%2)){temp[rear]-r=p;}if(1==front%2)rear++;//就当前的数据找这个数据的父母}}}}~ECS()//释放内存{inti;for(i=1;i=n;i++)if(temp[i]!=NULL)deletetemp[i];}voidJS()//记录节点的个数{ints;s=n;cout该二叉树的节点数为:sendl;}voidBL1(ECS_data*t)//递归前序遍历{if(NULL!=t){coutt-data,;BL1(t-l);BL1(t-r);}}voidpreOrder2(ECS_data*t)//非递归前序遍历{stackECS_data*s;ECS_data*p=t;while(p!=NULL||!s.empty()){while(p!=NULL){coutp-data;s.push(p);p=p-l;}if(!s.empty()){p=s.top();s.pop();p=p-r;}}}voidBL2(ECS_data*t)//递归中序遍历{if(NULL!=t){BL2(t-l);coutt-data,;BL2(t-r);}}voidinOrder2(ECS_data*t)//非递归中序遍历{stackECS_data*s;ECS_data*p=t;while(p!=NULL||!s.empty()){while(p!=NULL){s.push(p);p=p-l;}if(!s.empty()){p=s.top();coutp-data;s.pop();p=p-r;}}}voidBL3(ECS_data*t)//递归后序遍历{if(NULL!=t){BL3(t-l);BL3(t-r);coutt-data,;}}voidpostOrder3(ECS_data*t)//非递归后序遍历{stackECS_data*s;ECS_data*cur;//当前结点ECS_data*pre=NULL;//前一次访问的结点s.push(t);while(!s.empty()){cur=s.top();if((cur-l==NULL&&cur-r==NULL)||(pre!=NULL&&(pre==cur-l||pre==cur-r))){coutcur-data;//如果当前结点没有孩子结点或者孩子节点都已被访问过s.pop();pre=cur;}else{if(cur-r!=NULL)s.push(cur-r);if(cur-l!=NULL)s.push(cur-l);}}}intHeight(ECS_data*t)//求树高{if(t==NULL)return0;else{intm=Height(t-l);intn=Height(t-r);return(mn)?(m+1):(n+1);}}intCountLeaf(ECS_data*t)//求叶子总数{staticintLeafNum=0;//叶子初始数目为0，使用静态变量if(t)//树非空{if(t-l==NULL&&t-r==NULL)//为叶子结点LeafNum++;//叶子数目加1else//不为叶子结点{CountLeaf(t-l);//递归统计左子树叶子数目CountLeaf(t-r);//递归统计右子树叶子数目}}returnLeafNum;}};intmain(){ECSa;a.JS();cout递归前序遍历:;a.BL1(a.root);coutendl;cout非递归前序遍历:;a.preOrder2(a.root);coutendl;cout递归中序遍历:;a.BL2(a.root);coutendl;cout非递归中序遍历:;a.inOrder2(a.root);coutendl;cout递归后序遍历:;a.BL3(a.root);coutendl;cout非递归后序遍历:;a.postOrder3(a.root);coutendl;cout树高为:a.Height(a.root)endl;cout叶子总数为:a.CountLeaf(a.root)endl;return0;}