数据结构实验3.doc
【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构实验3.精品文档.实验三、二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容题目一：二叉树的基本操作实现 （必做题）问题描述建立一棵二叉树，试编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；(选做)4. 将二叉树每个结点的左右子树交换位置。（选做） 基本要求从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），测试数据如输入：ABCDEGF（其中表示空格字符）则输出结果为 先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA层序：ABCDEFG选作内容采用非递归算法实现二叉树遍历。三、 算法思想按前序构造一棵二叉树，先给二叉树分配空间，再用前序递归算法为该树输入结点。本次实验主要用到了多个递归遍历，把二叉树的不同顺序展现给大家。主要递归方式，用图代表如下：1、前序递归遍历：1. 2.5. 3. 4. 6. 7.当该二叉树为非空时，按上图的顺序输出各个结点。具体步骤为：1、 写一个函数，先输出根结点数据。2、 再判断左子树是否为空，如果左子树不为空，调用自身函数，把左子树的根结点附给原根结点。3、 再判断右子树是否为空，如果右子树不为空，调用自身函数，把右子树的根结点附给原根结点。4、 遍历直到再没有结点作为原根结点，结束递归。2、 中序递归遍历： 4.2.6.1.3. 5.7.当该二叉树为非空时，按上图的顺序输出各个结点。具体步骤为：1、 先判断左子树是否为空，如果左子树不为空，调用自身函数，把左子树的根结点附给原根结点。2、 写一个函数，输出根结点数据。3、再判断右子树是否为空，如果右子树不为空，调用自身函数，把右子树的根结点附给原根结点。4、遍历直到再没有结点作为原根结点，结束递归。3、后续递归遍历：7. 3.6. 1. 2. 4.5.当该二叉树为非空时，按上图的顺序输出各个结点。具体步骤为：1、先判断左子树是否为空，如果左子树不为空，调用自身函数，把左子树的根结点附给原根结点。2、再判断右子树是否为空，如果右子树不为空，调用自身函数，把右子树的根结点附给原根结点。3、 写一个函数，输出根结点数据。4、 遍历直到再没有结点作为原根结点，结束递归。4、 层序遍历：1. 先把根结点的数据赋值给数组的第一个元素2. 当左右结点不为空时，把左右结点分别赋值给数组的下个，再下个元素3. 当左子树不为空时，j加1，当右子树不为空时，j加1，每循环一次i加14. 每循环一次，把下标为i的数组赋值给根结点5. 直到i和j的值相等为止四、本函数包含九个模块1、 创建一棵树主要代码：cin>>ch;if(ch = '#')T = NULL;elseif(!(T = (BiTree)malloc(sizeof(BiNode)exit(OVERFLOW);T->ch = ch;T->Lsubtree = CreateTree();T->Rsubtree = CreateTree();return T;2、 递归前序遍历主要代码：if(T)cout<<T->ch;PreOrder(T->Lsubtree);PreOrder(T->Rsubtree);3、 递归中序遍历主要代码：if(T)InOrder(T->Lsubtree);cout<<T->ch;InOrder(T->Rsubtree);4、 递归后序遍历主要代码：if(T)PostOrder(T->Lsubtree);PostOrder(T->Rsubtree);cout<<T->ch;5、 层序遍历主要代码：while (i != j)p = qi;cout << p->ch;if (p->Lsubtree!= NULL)qj = p->Lsubtree;j+;if (p->Rsubtree!= NULL)qj = p->Rsubtree;j+;i+;6、 计算总结点数主要代码：if(T)node+;nodecount(T->Lsubtree);nodecount(T->Rsubtree);7、 计算叶子数主要代码：if(T)if(T->Lsubtree = NULL && T->Rsubtree = NULL)count+;leafcount(T->Lsubtree);leafcount(T->Rsubtree);8、 计算深度主要代码：if(T)int depthleft = depthcount(T->Lsubtree);int depthright = depthcount(T->Rsubtree);Bdepth = 1+(depthleft>depthright?depthleft:depthright);elseBdepth = 0;9、 主函数主要代码：cout<<"+ 输入格式为:"<<endl<<endl;cout<<"+ 例： a"<<endl;cout<<" / "<<endl;cout<<" b c "<<endl;cout<<"+ 输入格式为：ab#c# "<<endl<<endl<<endl;s:cout<<"+ 请输入您的树（系统默认按前序输入）： "<<endl<<endl;五、实验过程图1.该图为进入菜单界面图2.该图为输入一棵树时显示数据图3.该图为输入y或Y时的界面图4.该图为输入第二棵树时的界面图5.该图为输入除了y和Y的数据时界面六、调试及感受本次实验花了我好多时间，不是调试，现在调试略有提高。但是，就是在层序遍历那里给卡住了，总是想不通写的队列为什么总是有问题，后来琢磨太久，果断决定用数组解决，以后再好好学习学习队列，实在是自己用的不熟练。还有，谢谢老师的辅导，老师每天的课都被安排在早上第一节，每天都顾不上吃早餐就跑来给我们上课，谢谢老师，一直默默地为我们付出！谢谢！七、源代码#include<iostream>#include<stdio.h>#include<malloc.h>using namespace std;int count = 0;/初始化计数器int node = 0;/初始化结点数typedef struct BiNode/定义树的结构体char ch;BiNode *Lsubtree,*Rsubtree;BiNode,*BiTree;BiTree CreateTree()/创建一棵树BiTree T;char ch;cin>>ch;if(ch = '#')T = NULL;elseif(!(T = (BiTree)malloc(sizeof(BiNode)exit(OVERFLOW);T->ch = ch;T->Lsubtree = CreateTree();T->Rsubtree = CreateTree();return T;void PreOrder(BiTree T)/递归前序遍历if(T)cout<<T->ch;PreOrder(T->Lsubtree);PreOrder(T->Rsubtree);void InOrder(BiTree T)/递归中序遍历if(T)InOrder(T->Lsubtree);cout<<T->ch;InOrder(T->Rsubtree);void PostOrder(BiTree T)/递归后序遍历if(T)PostOrder(T->Lsubtree);PostOrder(T->Rsubtree);cout<<T->ch;void FloorOrder(BiTree T)/层序遍历BiTree q200, p;int i, j;if (T)p = T;q1 = T;i = 1; j = 2;elsecout << "该二叉树创建失败！" << endl;return;while (i != j)p = qi;cout << p->ch;if (p->Lsubtree!= NULL)qj = p->Lsubtree;j+;if (p->Rsubtree!= NULL)qj = p->Rsubtree;j+;i+;void nodecount(BiTree T)/计算总结点数if(T)node+;nodecount(T->Lsubtree);nodecount(T->Rsubtree);void leafcount(BiTree T)/计算叶子数if(T)if(T->Lsubtree = NULL && T->Rsubtree = NULL)count+;leafcount(T->Lsubtree);leafcount(T->Rsubtree);int depthcount(BiTree T)/计算深度int Bdepth;if(T)int depthleft = depthcount(T->Lsubtree);int depthright = depthcount(T->Rsubtree);Bdepth = 1+(depthleft>depthright?depthleft:depthright);elseBdepth = 0;return Bdepth;int main()/主函数char a;BiTree T;cout<<"+"<<endl;cout<<"+"<<endl<<endl;cout<<"+你喜欢爬树么？喜欢二叉树么？赶紧跟我一起来玩吧，哈哈哈。 "<<endl<<endl;cout<<"+ 来创建你的树吧：(请输入您所想要的树节点，一个节点一个字母,输入#代表空！)"<<endl<<endl;cout<<"+ 输入格式为:"<<endl<<endl;cout<<"+ 例： a"<<endl;cout<<" / "<<endl;cout<<" b c "<<endl;cout<<"+ 输入格式为：ab#c# "<<endl<<endl<<endl;s:cout<<"+ 请输入您的树（系统默认按前序输入）： "<<endl<<endl;node = 0;count = 0;T = CreateTree();cout<<endl;if(T!=NULL)cout<<"+ 您的树已创建成功! "<<endl<<endl;if(!T)cout<<"+ 该二叉树为空!"<<endl<<endl;cout<<"+ 1.递归先序遍历: "<<endl<<"tt"PreOrder(T);cout<<endl;cout<<"+ 2.递归中序遍历: "<<endl<<"tt"InOrder(T);cout<<endl;cout<<"+ 3.递归后序遍历: "<<endl<<"tt"PostOrder(T);cout<<endl;cout<<"+ 4.层序遍历: "<<endl<<"tt"FloorOrder(T);cout<<endl;cout<<"+ 5.结点数： "<<endl<<"tt"nodecount(T);cout<<node<<"个结点"<<endl;cout<<"+ 6.叶子数： "<<endl<<"tt"leafcount(T);cout<<count<<"片树叶"<<endl;cout<<"+ 7.树的深度： "<<endl<<"tt"cout<<depthcount(T)<<"层"cout<<endl;cout<<endl;cout<<"+"<<endl;cout<<"+"<<endl<<endl;cout<<"输入Y或y可再输入一棵树，输入其它键结束！o"<<endl<<endl;cin>>a;if(a='Y'|a='y')goto s;system("pause");return 0;
