数据结构实验3.doc

《数据结构实验3.doc》由会员分享，可在线阅读，更多相关《数据结构实验3.doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构实验3.精品文档.实验三、二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容题目一：二叉树的基本操作实现 （必做题）问题描述建立一棵二叉树，试编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；(选做)4. 将二叉树每个结点的左右子树交换位置。（选做） 基本要求从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉

2、树（以先序来建立），测试数据如输入：ABCDEGF（其中表示空格字符）则输出结果为 先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA层序：ABCDEFG选作内容采用非递归算法实现二叉树遍历。三、 算法思想按前序构造一棵二叉树，先给二叉树分配空间，再用前序递归算法为该树输入结点。本次实验主要用到了多个递归遍历，把二叉树的不同顺序展现给大家。主要递归方式，用图代表如下：1、前序递归遍历：1. 2.5. 3. 4. 6. 7.当该二叉树为非空时，按上图的顺序输出各个结点。具体步骤为：1、 写一个函数，先输出根结点数据。2、 再判断左子树是否为空，如果左子树不为空，调用自身函数，把左子树的

3、根结点附给原根结点。3、 再判断右子树是否为空，如果右子树不为空，调用自身函数，把右子树的根结点附给原根结点。4、 遍历直到再没有结点作为原根结点，结束递归。2、 中序递归遍历： 4.2.6.1.3. 5.7.当该二叉树为非空时，按上图的顺序输出各个结点。具体步骤为：1、 先判断左子树是否为空，如果左子树不为空，调用自身函数，把左子树的根结点附给原根结点。2、 写一个函数，输出根结点数据。3、再判断右子树是否为空，如果右子树不为空，调用自身函数，把右子树的根结点附给原根结点。4、遍历直到再没有结点作为原根结点，结束递归。3、后续递归遍历：7. 3.6. 1. 2. 4.5.当该二叉树为非空时，

4、按上图的顺序输出各个结点。具体步骤为：1、先判断左子树是否为空，如果左子树不为空，调用自身函数，把左子树的根结点附给原根结点。2、再判断右子树是否为空，如果右子树不为空，调用自身函数，把右子树的根结点附给原根结点。3、 写一个函数，输出根结点数据。4、 遍历直到再没有结点作为原根结点，结束递归。4、 层序遍历：1. 先把根结点的数据赋值给数组的第一个元素2. 当左右结点不为空时，把左右结点分别赋值给数组的下个，再下个元素3. 当左子树不为空时，j加1，当右子树不为空时，j加1，每循环一次i加14. 每循环一次，把下标为i的数组赋值给根结点5. 直到i和j的值相等为止四、本函数包含九个模块1、

5、创建一棵树主要代码：cinch;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)coutch;PreOrder(T-Lsubtree);PreOrder(T-Rsubtree);3、 递归中序遍历主要代码：if(T)InOrder(T-Lsubtree);coutch;InOrder(T-Rsubtree);4、

6、递归后序遍历主要代码：if(T)PostOrder(T-Lsubtree);PostOrder(T-Rsubtree);coutch;5、 层序遍历主要代码：while (i != j)p = qi;cout 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

7、 & 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+(depthleftdepthright?depthleft:depthright);elseBdepth = 0;9、 主函数主要代码：cout+ 输入格式为:endlendl;cout+ 例： aendl;cout / endl;cout

8、 b c endl;cout+ 输入格式为：ab#c# endlendlendl;s:cout+ 请输入您的树（系统默认按前序输入）： endlendl;五、实验过程图1.该图为进入菜单界面图2.该图为输入一棵树时显示数据图3.该图为输入y或Y时的界面图4.该图为输入第二棵树时的界面图5.该图为输入除了y和Y的数据时界面六、调试及感受本次实验花了我好多时间，不是调试，现在调试略有提高。但是，就是在层序遍历那里给卡住了，总是想不通写的队列为什么总是有问题，后来琢磨太久，果断决定用数组解决，以后再好好学习学习队列，实在是自己用的不熟练。还有，谢谢老师的辅导，老师每天的课都被安排在早上第一节，每天都

9、顾不上吃早餐就跑来给我们上课，谢谢老师，一直默默地为我们付出！谢谢！七、源代码#include#include#includeusing namespace std;int count = 0;/初始化计数器int node = 0;/初始化结点数typedef struct BiNode/定义树的结构体char ch;BiNode *Lsubtree,*Rsubtree;BiNode,*BiTree;BiTree CreateTree()/创建一棵树BiTree T;char ch;cinch;if(ch = #)T = NULL;elseif(!(T = (BiTree)malloc(si

10、zeof(BiNode)exit(OVERFLOW);T-ch = ch;T-Lsubtree = CreateTree();T-Rsubtree = CreateTree();return T;void PreOrder(BiTree T)/递归前序遍历if(T)coutch;PreOrder(T-Lsubtree);PreOrder(T-Rsubtree);void InOrder(BiTree T)/递归中序遍历if(T)InOrder(T-Lsubtree);coutch;InOrder(T-Rsubtree);void PostOrder(BiTree T)/递归后序遍历if(T)P

11、ostOrder(T-Lsubtree);PostOrder(T-Rsubtree);coutch;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 ch;if (p-Lsubtree!= NULL)qj = p-Lsubtree;j+;if (p-Rsubtree!= NULL)qj = p-Rsubtree;j+;i+;void nodecount(BiTr

12、ee 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 = depth

13、count(T-Rsubtree);Bdepth = 1+(depthleftdepthright?depthleft:depthright);elseBdepth = 0;return Bdepth;int main()/主函数char a;BiTree T;cout+endl;cout+endlendl;cout+你喜欢爬树么？喜欢二叉树么？赶紧跟我一起来玩吧，哈哈哈。 endlendl;cout+ 来创建你的树吧：(请输入您所想要的树节点，一个节点一个字母,输入#代表空！)endlendl;cout+ 输入格式为:endlendl;cout+ 例： aendl;cout / endl;c

14、out b c endl;cout+ 输入格式为：ab#c# endlendlendl;s:cout+ 请输入您的树（系统默认按前序输入）： endlendl;node = 0;count = 0;T = CreateTree();coutendl;if(T!=NULL)cout+ 您的树已创建成功! endlendl;if(!T)cout+ 该二叉树为空!endlendl;cout+ 1.递归先序遍历: endltt;PreOrder(T);coutendl;cout+ 2.递归中序遍历: endltt;InOrder(T);coutendl;cout+ 3.递归后序遍历: endltt;P

15、ostOrder(T);coutendl;cout+ 4.层序遍历: endltt;FloorOrder(T);coutendl;cout+ 5.结点数： endltt;nodecount(T);coutnode个结点endl;cout+ 6.叶子数： endltt;leafcount(T);coutcount片树叶endl;cout+ 7.树的深度： endltt;coutdepthcount(T)层;coutendl;coutendl;cout+endl;cout+endlendl;cout输入Y或y可再输入一棵树，输入其它键结束！oendla;if(a=Y|a=y)goto s;system(pause);return 0;