c二叉树基本操作实验报告

《c二叉树基本操作实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、二叉树各节点数据cout«”请按正确顺序输入二叉树的数据:”；cin.getline（t，1000）;//先把输入的数据输入到一个t数组3、递归前序遍历voidBLl(ECS_data*t){if(NULL!=t){cout«t-〉data<<’’，";BLl(t-〉l);BLl(t-〉r);}}4、非递归前序遍历voidpreOrder2(ECS_data*t){stack

3、

4、!s.empty()){while(p!=NULL

5、){cout«p->data«"s.push(p);p=p-〉l;}if(!s.empty()){p=s.top();s.popO;p=p-〉r;}}}5、递归中序遍历voidBL2(ECS_data*t){if(NULL!=t)cout«t->data«，7'；BL2(t->r);}6、非递归中序遍历voidinOrder2(ECS_data*t)//非递归中序遍历{stack

6、

7、!s.emptyO)while(p!=NULL

8、){s.push(p);p=p-〉l;}if(!s.empty()){p=s.top();cout«p->data«"":s.pop();p=p-〉r;}7、递归后序遍历voidBL3(ECS_data*t){if(NULL!=t){BL3(t->l);BL3(t->r);cout«t->data«;8、非递归后序遍历voidpostOrder3(ECS_data*t){stacks;ECS_data*cur;//当前结点ECS_data*pre=NULL;//前一次访问的结点s.p

9、ush(t);while(!s.empty())cur=s.top();if((cur->l==NULL&&cur->r==NULL)

10、

11、(pre!=NULL&&(pre==cur->l

12、

13、pre==cur->r))){cout«cur->data«H//如果当前结点没有孩子结点或者孩子节点都已被访问过s.pop();pre=cur;}else{if(cur->r!=NULL)s.push(cur->r);if(cur-〉l!=NULL)s.push(cur->l);}9、求树高intHeight(ECS

14、_data*t){if(t==NULL)return0;else{intm=Height(t->l);intn=Height(t->r);return(m>n)?(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）;//

15、递归统计左子树叶子数目CountLeaf（t->r）;//递归统计右子树叶子数目returnLeafNum;}五、运行结果67330651-95800,叉:1,84,2二为,42,9人数,2:1,4*按正确3i63175609259n4489斤节历遍历遍历遍:5ke顺的为y樹序前^!£:-5-1!£:后:4数仙正叉薦中归肩为口r二归遥归遥归遥髙子esS謹非递非递非側叶pr附：完整程序源代码://二叉树链式存储的实现#include#include#include〈st

16、ack〉usingnamespacestd;structECS_data//先定义好一个数掘的结构{chardata;ECS_data*1;ECS_data*r;classECS{private://intlevel;//树高intn;//表示有多少个节点数intnl;//表示的是数组的总长度值，（钮拈#），因为后面要进行删除判断ECS_data*temp[1000];public:ECS_data*root;ECS()//初