欢迎来到天天文库
浏览记录
ID:29637087
大小:288.99 KB
页数:15页
时间:2018-12-21
《《数据结构实验》word版》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、实验三、二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容题目一:二叉树的基本操作实现(必做题)[问题描述]建立一棵二叉树,试编程实现二叉树的如下基本操作:1.按先序序列构造一棵二叉链表表示的二叉树T;2.对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出结点的遍历序列;3.求二叉树的深度/结点数目/叶结点数目;(选做)4.将二叉树每个结点的左右子树交换位置。(选做)[基本要求]从键盘接受输入(先序),以二叉链表作为存储结构,建立二叉树(以先序来建立),[测试数据]如输入:ABCффDEфGффFффф(其中ф表示
2、空格字符) 则输出结果为先序:ABCDEGF 中序:CBEGDFA 后序:CGEFDBA层序:ABCDEFG[选作内容]采用非递归算法实现二叉树遍历。三、算法思想按前序构造一棵二叉树,先给二叉树分配空间,再用前序递归算法为该树输入结点。本次实验主要用到了多个递归遍历,把二叉树的不同顺序展现给大家。15主要递归方式,用图代表如下: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.15当该二叉树为非空时,按上图的顺序输出各个结点。具体步骤为:1、先判断左子树是否为空,如果左子树不
4、为空,调用自身函数,把左子树的根结点附给原根结点。2、再判断右子树是否为空,如果右子树不为空,调用自身函数,把右子树的根结点附给原根结点。3、写一个函数,输出根结点数据。4、遍历直到再没有结点作为原根结点,结束递归。4、层序遍历:1.先把根结点的数据赋值给数组的第一个元素2.当左右结点不为空时,把左右结点分别赋值给数组的下个,再下个元素3.当左子树不为空时,j加1,当右子树不为空时,j加1,每循环一次i加14.每循环一次,把下标为i的数组赋值给根结点5.直到i和j的值相等为止四、本函数包含九个模块1、创建一棵树主要代码:cin>>ch;if(ch=='#')T=NULL;else{if(!(T
5、=(BiTree)malloc(sizeof(BiNode))))exit(OVERFLOW);T->ch=ch;T->Lsubtree=CreateTree();T->Rsubtree=CreateTree();}returnT;151、递归前序遍历主要代码:if(T){cout<ch;PreOrder(T->Lsubtree);PreOrder(T->Rsubtree);}2、递归中序遍历主要代码:if(T){InOrder(T->Lsubtree);cout<ch;InOrder(T->Rsubtree);}3、递归后序遍历主要代码:if(T){PostOrder(T->
6、Lsubtree);PostOrder(T->Rsubtree);cout<ch;}4、层序遍历主要代码:while(i!=j){p=q[i];15cout<ch;if(p->Lsubtree!=NULL){q[j]=p->Lsubtree;j++;}if(p->Rsubtree!=NULL){q[j]=p->Rsubtree;j++;}i++;1、计算总结点数主要代码:if(T){node++;nodecount(T->Lsubtree);nodecount(T->Rsubtree);}2、计算叶子数主要代码:if(T){if(T->Lsubtree==NULL&&T->Rs
7、ubtree==NULL)count++;leafcount(T->Lsubtree);leafcount(T->Rsubtree);}151、计算深度主要代码:if(T){intdepthleft=depthcount(T->Lsubtree);intdepthright=depthcount(T->Rsubtree);Bdepth=1+(depthleft>depthright?depthle
此文档下载收益归作者所有