数据结构二叉树综合实验报告.docx

数据结构二叉树综合实验报告武 汉 工 程 大 学 计算机科学与工程学院 数据结构实验报告2 专业班级 学生学号 学生姓名 实验项目 实验类别 智能01 实验地点 指导教师 实验时间 树性结构的综合使用 操作性 验证性 设计性 综合性 其它 1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。 2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 机电大楼4 楼 419 机房 第 12 周第14 周 星期2 实验目的及要求 成 绩 评 定 表 类 别 上机表现 报告质量 评 分 标 准 积极出勤、遵守纪律 认真完成设计任务 操作规范、功能正确 填写完整、体现收获 分值 30分 70分 得分 合 计 说明： 评阅教师： 日 期： 20 年 月 日 实 验 内 容 计算机科学与工程学院 一实验内容 1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。 2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 二程序的设计思想 1实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。 先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则输入上一层右字树。 二叉树的非递归遍历是用显示栈来存储二叉树的结点指针，先序遍历时，按二叉树前序遍历的顺序访问结点，并将结点的指针入栈，直到栈顶指针指向结点的左指针域为空时取出栈顶指针并删除栈顶指针，访问刚取出的指针指向的结点的右指针指向的结点并将其指针入栈，如此反复执行则为非递归操作。 二叉树的递归遍历：若二叉树为空，则空操作 先序遍历： 访问根结点； 先序遍历左子树； 先序遍历右子树。 中序遍历 ： 中序遍历左子树； 访问根结点； 中序遍历右子树 后序遍历： 后序遍历左子树； 后序遍历右子树； 访问根结点。 2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。 求二叉树的叶子结点个数：先分别求得左右子树中个叶子结点的个数，再计算出两者之和即为二叉树的叶子结点数。 二叉树的结点个数之和：先分别求得左子树右子树中结点之和，再计算两者之和即为所求。 二叉树的高度：首先判断二叉树是否为空，若为空则此二叉树高度为0,。否则，就先分别求出左右子树的深度进行比较，取较大的树加一即为所求。 二叉树的度为2的结点个数：计算有左右孩子的结点个数，即为度为2的结点个 实 验 内 容 数据结构实验报告 2 计算机科学与工程学院 数。 三编程过程中遇到的问题及解决办法 后续遍历的非递归函数涉及到回溯的方法，开始设计的方案想的太过于简单，所以形成了死循环，总是在最后的节点处不停地循环，后改成回溯后，该问题得到解决。 计算二叉树中度为2的结点个数中，返回循环的时候不论根结点有没有左右子树，但个人设计时，根总是会将自己默认为有左右子树，自行增加1.后在同学帮助下才看到自己的这个失误。 四程序的闪光点(自我评价) 1.程序模块化，各个函数分开描述，方便观察 2.关键处有注释 3.建立二叉树时，用先序提示输入，比较人性化。 五程序源代码(以文件为单位提供) #include<iostream.h> #include<malloc.h> #define Maxsize 100 typedef struct TREE struct TREE *lTree; struct TREE *rTree; char data; Tree; void InitTree(Tree*);/初始化树 void CreatTree(Tree*);/创建二叉树 void PreTraverse(Tree*);/先序遍历递归 void PreOrderTraverse(Tree*);/先序遍历非递归 void InTraverse(Tree *tree);/中序遍历递归 void InOrderTraverse(Tree *tree);/中序遍历非递归 void PostTraverse(Tree *tree);/后序遍历递归 void LastOrderTraverse(Tree *tree);/后序遍历非递归 int DepthTree(Tree *tree);/计算树的深度 数据结构实验报告 3 计算机科学与工程学院 int LeafsTree(Tree *tree);/计算叶子结点个数 int NodesTree(Tree *tree);/计算结点个数 int Twochild(Tree*tree);/计算度为二的结点个数 void main / int H,L; Tree tree; Tree m; InitTree(&tree); CreatTree(&tree); cout<<"先序遍历递归为:" PreTraverse(&tree);/先序遍历递归 cout<<"先序遍历非递归:" PreOrderTraverse(&tree);/先序遍历非递归 cout<<endl; cout<<"中序遍历递归为:" InTraverse(&tree);/中序遍历递归 cout<<"中序遍历非递归:" InOrderTraverse(&tree);/中序遍历非递归 cout<<endl; cout<<"后序遍历递归为:" PostTraverse(&tree);/后序遍历递归 cout<<"后序遍历非递归:" LastOrderTraverse(&tree);/后序遍历非递归 cout<<endl; cout<<"树的深度为:" H=DepthTree(&tree); cout<<H<<endl; cout<<"叶子结点个数:" 数据结构实验报告 4 计算机科学与工程学院 L=LeafsTree(&tree); cout<<L<<endl; void InitTree(Tree *tree)/初始化树 void CreatTree(Tree *tree)/创建树 int n=0,m=0,i=0; if(tree->data='0') cout<<"节点"<<tree->data<<"是否有左子树：" cin>>n; if(n=1) Tree *lTree=(Tree*)malloc(sizeof(Tree); tree->lTree=lTree; 数据结构实验报告 5 cout<<"结点个数：" cout<<NodesTree(&tree)<<endl; cout<<"度为二的结点个数" L=Twochild(&tree); cout<<L<<endl; tree->lTree=NULL; tree->rTree=NULL; tree->data='0' cout<<"请输入该节点的数据：" cin>>tree->data; 计算机科学与工程学院 else if(n=0) cout<<"节点"<<tree->data<<"是否有右子树：" cin>>m; lTree->lTree=NULL; lTree->rTree=NULL; lTree->data='0' CreatTree(tree->lTree); cout<<"节点"<<tree->data<<"是否有右子树：" cin>>i; if(i=0); else if(i=1) Tree *rTree=(Tree*)malloc(sizeof(Tree); tree->rTree=rTree; rTree->lTree=NULL; rTree->rTree=NULL; rTree->data='0' CreatTree(tree->rTree); if(m=0); else if(m=1) Tree *rTree=(Tree*)malloc(sizeof(Tree); tree->rTree=rTree; rTree->lTree=NULL; rTree->rTree=NULL; 数据结构实验报告 6 计算机科学与工程学院 void PreTraverse(Tree*tree)/先序遍历递归 void PreOrderTraverse(Tree *tree)/先序遍历非递归 Tree *S80=NULL; int top =0; while (tree!=NULL)|(top) 数据结构实验报告 7 rTree->data='0' CreatTree(tree->rTree); if(tree!=NULL) cout<<tree->data<<" " if(tree->lTree!=NULL) else if(tree->rTree!=NULL) else; PreTraverse(tree->rTree); PreTraverse(tree->lTree); PreTraverse(tree->rTree); 计算机科学与工程学院 if (tree!=NULL) cout<<tree->data<<" " top+; Stop = tree; tree = tree->lTree; void InTraverse(Tree *tree)/中序遍历递归 if(tree!=NULL) if(tree->lTree!=NULL) else if(tree->rTree!=NULL) cout<<tree->data<<" " 数据结构实验报告 8 else tree = Stop; top-; tree = tree->rTree; InTraverse(tree->lTree); cout<<tree->data<<" " InTraverse(tree->rTree); 计算机科学与工程学院 void InOrderTraverse(Tree *tree)/中序遍历非递归 Tree *D80=NULL; int top =0; while (tree!=NULL)|(top) if (tree!=NULL) top+; Dtop = tree; else cout<<tree->data<<" " InTraverse(tree->rTree); tree = tree->lTree; void PostTraverse(Tree *tree)/后序遍历递归 数据结构实验报告 9 else tree = Dtop; top-; cout<<tree->data<<" " tree = tree->rTree; 计算机科学与工程学院 void LastOrderTraverse(Tree *tree)/后序遍历非递归 Tree *stackMaxsize=NULL,*p; p=tree; int top=0,tag=1,i=0,k=0; while(p!=NULL | top) i=1; while(p!=NULL) 数据结构实验报告 10 if(tree!=NULL) if(tree->lTree!=NULL) else if(tree->rTree!=NULL) else cout<<tree->data<<" " PostTraverse(tree->rTree); cout<<tree->data<<" " PostTraverse(tree->lTree); PostTraverse(tree->rTree); cout<<tree->data<<" " stack+top=p; p=p->lTree; 计算机科学与工程学院 if(top!=0) p=stacktop->rTree; if(p=NULL) 数据结构实验报告 11 cout<<stacktop->data<<" " if(stacktop!=NULL) if(top!=0) else p=NULL; p=stacktop->rTree; while(i) if(stacktop!=NULL) else i=0; if(stacktop->rTree!=NULL) else i=0; if(stacktop->rTree->data=stacktop+1->data) else i=0; cout<<stacktop->data<<" " 计算机科学与工程学院 int DepthTree(Tree *tree) /深度函数 int u,v; if (tree=NULL) return 0; u=DepthTree(tree->lTree); v=DepthTree(tree->rTree); if (u>v) return (u+1); return (v+1); int LeafsTree(Tree *tree)/子叶个数函数 int num1,num2; if(tree=NULL) return 0; else if(tree->lTree=NULL&&tree->rTree=NULL) return 1; else num1=LeafsTree(tree->lTree); num2=LeafsTree(tree->rTree); return(num1+num2); 数据结构实验报告 12 计算机科学与工程学院 int NodesTree(Tree *tree)/结点个数函数 int num1,num2; if(tree=NULL) return 0; if(tree->lTree=NULL&&tree->rTree=NULL) return 1; else num1=NodesTree(tree->lTree); num2=NodesTree(tree->rTree); return(num1+num2+1); int Twochild(Tree*tree)/度为2的 int n=0; if(tree=NULL) return(0); if(tree->lTree!=NULL&&tree->rTree!=NULL) n=1; return(Twochild(tree->lTree)+Twochild(tree->rTree)+n); 数据结构实验报告 13 计算机科学与工程学院 实 验 总 结 通过这次实验使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。 数据结构实验报告 14