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

1、一、实验目的选择二叉链式存储结构作为二叉树的存储结构，设计一个程序实现二叉树的基本操作（包括建立、输出、前序遍历、中序遍历、后序遍历、求树高、统计叶子总数等）二、实验开发环境Windows 8.1 中文版Microsoft Visual Studio 6.0三、实验内容程序的菜单功能项如下：1-建立一棵二叉树2-前序遍历递归算法3-前序遍历非递归算法4- 中序遍历递归算法5- 中序遍历非递归算法6- 后序遍历递归算法7- 后序遍历非递归算法8-求树高9-求叶子总数10-输出二叉树11-退出四、实验分析1、建立一棵二叉树2、输入二叉树各节点数据cout 请按正确顺序输入二叉树的数据 :; cin

2、.getline(t,1000);/先把输入的数据输入到一个 t 数组3、递归前序遍历void BL1(ECS_data *t) if(NULL!=t) coutdatal); BL1(t-r); 4、非递归前序遍历void preOrder2(ECS_data *t) stack s; ECS_data *p=t; while(p!=NULL|!s.empty() while(p!=NULL) coutdatal; if(!s.empty() p=s.top(); s.pop(); p=p-r;5、递归中序遍历void BL2(ECS_data *t) if(NULL!=t)BL2(t-l)

3、;coutdatar);6、非递归中序遍历void inOrder2(ECS_data *t) /非递归中序遍历stack 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(); coutdatar;7、递归后序遍历void BL3(ECS_data *t)if(NULL!=t)BL3(t-l);BL3(t-r);coutdata,;8、非递归后序遍历void postOrder3(ECS_data *t)stack s;ECS_data *cur; /当前结点

4、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)coutdatar!=NULL)s.push(cur-r);if(cur-l!=NULL)s.push(cur-l);9、求树高int Height (ECS_data *t)if(t=NULL) return 0;elseint m = Height ( t-l );int n = Height(t-r);return (m n) ? (m+1

5、) : (n+1);10、求叶子总数int CountLeaf(ECS_data *t)static int LeafNum=0;/ 叶子初始数目为 0，使用静态变量if(t)/ 树非空if(t-l=NULL&t-r=NULL)/ 为叶子结点LeafNum+;/ 叶子数目加 1else/不为叶子结点Cou ntLeaf(t-l);递归统计左子树叶子数目Cou ntLeaf(t-r);递归统计右子树叶子数目 return LeafNum;五、运行结果附：完整程序源代码：二叉树链式存储的实现#in clude#in clude#in elude using n amespace std;struc

6、t ECS_data /先定义好一个数据的结构 char data;ECS_data *l;ECS_data *r; 一class ECSprivate:/in t level;/ 树高int n;/表示有多少个节点数int n1;表示的是数组的总长度值，(包括#)，因为后面要进行删除判断ECS_data *temp1000; public:ECS_data *root;ECS() / 初始化ECS_data *p;char t1000;int i; int front=0,rear=1;入的点的父母/front 表示有多少个节点， rear 表示当前插coutvv请按正确顺序输入二叉树的数据

7、cin.getline(t,1000); /coutt endl; int n1=strlen(t);n=0;/先把输入的数据输入到一个 t 数组/测量数据的长度for(i=0;idata=ti;p-l=NULL;p-r=NULL;front+;tempfront=p;if(1 = front)root=p;elseif(p!=NULL)&(0=front%2)temprear-l=p;/ 刚开始把这里写成了 =if(p!=NULL)&(1=front%2) temprear-r=p;if(1=front%2)rear+;/就当前的数据找这个数据的父母ECS()/释放内存int i; for(

8、i=1;i=n;i+) if(tempi!=NULL) delete tempi;void JS()/记录节点的个数int s;s=n;coutvv该二叉树的节点数为：vvsvvendl;void BL1(ECS_data *t)/ 递归前序遍历if(NULL!=t)coutdatal);BL1(t-r);void preOrder2(ECS_data *t) /非递归前序遍历stack s;ECS_data *p=t; while(p!=NULL|!s.empty() while(p!=NULL) coutdatal; if(!s.empty()p=s.top();s.pop(); p=p-

9、r;void BL2(ECS_data *t)/ 递归中序遍历if(NULL!=t)BL2(t-l);coutdatar);void inOrder2(ECS_data *t) /非递归中序遍历stack 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(); coutdatar;void BL3(ECS_data *t)/ 递归后序遍历if(NULL!=t)BL3(t-l);BL3(t-r);coutdata,;void postOrder3(ECS_dat

10、a *t) /非递归后序遍历stack 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)coutdatar!=NULL) s.push(cur-r);if(cur-l!=NULL)s.push(cur-l);int Height (ECS_data *t)/ 求树高if(t=NULL) return 0;elseint m = Height ( t

11、-l );int n = Height(t-r);return (m n) ? (m+1) : (n+1);int CountLeaf(ECS_data *t)/ 求叶子总数static int LeafNum=0;/ 叶子初始数目为 0，使用静态变量if(t)/ 树非空if(t-l=NULL&t-r=NULL)/ 为叶子结点 LeafNum+;/ 叶子数目加 1else/不为叶子结点Cou ntLeaf(t-l);递归统计左子树叶子数目Cou ntLeaf(t-r);递归统计右子树叶子数目return LeafNum;int main()ECS a;a.JS();cout 递归前序遍历 :;a.BL1(a.root);coutendl;cout 非递归前序遍历 :;a.preOrder2(a.root); coutendl;coutvv递归中序遍历：；a.BL2(a.root);coutendl；coutvv非递归中序遍历:;a.inOrder2(a.root)； c