《数据结构实验》word版

《《数据结构实验》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