好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

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

16页
  • 卖家[上传人]:ni****g
  • 文档编号:400735067
  • 上传时间:2023-10-31
  • 文档格式:DOC
  • 文档大小:43KB
  • / 16 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 一、实验目的 选择二叉链式存储结构作为二叉树的存储结构,设计一个程序实现二叉树的基本操作(涉及建立、输出、前序遍历、中序遍历、后序遍历、求树高、记录叶子总数等)二、 实验开发环境 Windows 8.1 中文版 Microsoft Visual Studio 6.0三、实验内容程序的菜单功能项如下:1------建立一棵二叉树2------前序遍历递归算法3------前序遍历非递归算法4------中序遍历递归算法5------中序遍历非递归算法6------后序遍历递归算法7------后序遍历非递归算法8------求树高9------求叶子总数10-----输出二叉树11-----退出四、实验分析1、建立一棵二叉树2、输入二叉树各节点数据 cout<<"请按对的顺序输入二叉树的数据:"; cin.getline(t,1000); //先把输入的数据输入到一个t数组 3、递归前序遍历 void BL1(ECS_data *t) { if(NULL!=t) { cout<data<<","; BL1(t->l); BL1(t->r); } }4、非递归前序遍历 void preOrder2(ECS_data *t) { stack s; ECS_data *p=t; while(p!=NULL||!s.empty()) { while(p!=NULL) { cout<data<<" "; s.push(p); p=p->l; } if(!s.empty()) { p=s.top(); s.pop(); p=p->r; } } }5、递归中序遍历 void BL2(ECS_data *t) { if(NULL!=t) { BL2(t->l); cout<data<<","; BL2(t->r); } } 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(); cout<data<<" "; s.pop(); p=p->r; } } }7、递归后序遍历 void BL3(ECS_data *t) { if(NULL!=t) { BL3(t->l); BL3(t->r); cout<data<<","; } }8、非递归后序遍历 void postOrder3(ECS_data *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))) { cout<data<<" "; //假如当前结点没有孩子结点或者孩子节点都已被访问过 s.pop(); pre=cur; } else { if(cur->r!=NULL) s.push(cur->r); if(cur->l!=NULL) s.push(cur->l); } } }9、求树高 int Height (ECS_data *t) { if(t==NULL) return 0; else { int m = Height ( t->l ); int n = Height(t->r); return (m > n) ? (m+1) : (n+1); } } 10、 求叶子总数int CountLeaf(ECS_data *t) { static int LeafNum=0;//叶子初始数目为0,使用静态变量 if(t)//树非空 { if(t->l==NULL&&t->r==NULL)//为叶子结点 LeafNum++;//叶子数目加1 else//不为叶子结点 { CountLeaf(t->l);//递归记录左子树叶子数目 CountLeaf(t->r);//递归记录右子树叶子数目 } } return LeafNum; }五、运营结果附:完整程序源代码://二叉树链式存储的实现 #include #include #include using namespace std; struct ECS_data //先定义好一个数据的结构 { char data; ECS_data *l; ECS_data *r; }; class ECS { private: //int level; //树高 int n; //表达有多少个节点数 int n1; //表达的是数组的总长度值,(涉及#),由于后面要进行删除判断 ECS_data *temp[1000]; public: ECS_data *root; ECS() //初始化 { ECS_data *p; char t[1000];int i; int front=0,rear=1; //front表达有多少个节点,rear表达当前插入的点的父母 cout<<"请按对的顺序输入二叉树的数据:"; cin.getline(t,1000); //先把输入的数据输入到一个t数组 //cout<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() //释放内存 { int i; for(i=1;i<=n;i++) if(temp[i]!=NULL) delete temp[i]; } void JS() //记录节点的个数 { int s; s=n; cout<<"该二叉树的节点数为:"<data<<","; BL1(t->l); BL1(t->r); } } void preOrder2(ECS_data *t) //非递归前序遍历 { stack s; ECS_data *p=t; while(p!=NULL||!s.empty()) { while(p!=N。

      点击阅读更多内容
      关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.