数据结构实验四树与二叉树
班级学号姓名分数
一、实验目的:
1、掌握二叉树的定义、性质及存储方式,各种遍历算法。
2、掌握这种存储结构的构造算法以及基于每一种结构上的算法设计
3、初步掌握算法分析方法并对已设计出的算法进行分析,给出相应的结果。
二、实验要求:
采用二叉树链表作为存储结构,完成二叉树的建立,先序、中序和后序以及按层次遍历的操作,求所有叶子及结点总数的操作。
三、实验内容及分析:
1、分析、理解程序。
2、调试程序,设计一棵二叉树,输入完全二叉树的先序序列,用#代表虚结点(空指针),
如ABD###CE##F##,建立二叉树,求出先序、中序和后序以及按层次遍历序列,求所有叶子及结点总数。
四、程序的调试及运行结果
先序遍历
中序遍历
后序遍历
树的深度及叶子树
层次遍历
五、程序代码
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数,leaf为叶子数
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列,其中加入虚结点"#"以示空指针的位置========== BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#,返回空指针
else{
T= (BinTNode *)malloc(sizeof(BinTNode)); //生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//========NLR 先序遍历=============
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//========LNR 中序遍历===============
void Inorder(BinTree T)
{
if(T) {
Inorder(T->lchild); //中序遍历左子树
printf("%c",T->data); //访问结点
Inorder(T->rchild); //中序遍历右子树
}
}
//==========LRN 后序遍历============
void Postorder(BinTree T)
{
if(T) {
Postorder(T->lchild); //后序遍历左子树
Postorder(T->rchild); //后序遍历右子树
printf("%c",T->data); //访问结点
}
}
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法======== int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0,即为叶子。
return(max+1);
}
else return(0);
}
//====利用"先进先出"(FIFO)队列,按层次遍历二叉树==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出队
printf("%c",p->data); //出队,输出结点的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子树入队
}
}
}
//====数叶子节点个数==========
int countleaf(BinTree T)
{
int hl,hr;
if(T){
hl=countleaf(T->lchild);
hr=countleaf(T->rchild);
if(hl==0&&hr==0) //若左右深度为0,即为叶子。
return(1);
else return hl+hr;
}
else return 0;
}
//==========主函数=================
void main()
{
BinTree root;
char i;
int depth;
printf("\n");
printf("Creat Bin_Tree; Input preorder:"); //输入完全二叉树的先序序列,
// 用#代表虚结点,如ABD###CE##F##
root=CreatBinTree(); //创建二叉树,返回根结点
do { //从菜单中选择遍历方式,输入序号。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //按层次遍历之前,先选择4,求出该树的结点数。
printf("\t0: Exit\n");
printf("\t*******************************\n");
fflush(stdin);
scanf("%c",&i); //输入菜单序号(0-5)
switch (i-'0'){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
break;
case 4:
depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",countleaf(root));
break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}
数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程,也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法,并做了相应的性能分析和比较,课程内容丰富,理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: 1)理论艰深,方法灵活,给学习带来困难; 2)内容丰富,涉及的知识较多,学习有一定的难度; 3)侧重于知识的实际应用,要求学生有较好的思维以及较强的分析和解决问题的能力,因而加大了学习的难度; 根据《数据结构》课程本身的特性,通过实验实践内容的训练,突出构造性思维训练的特征,目的是提高学生分析问题,组织数据及设计大型软件的能力。 课程上机实验的目的,不仅仅是验证教材和讲课的内容,检查自己所编的程序是否正确,课程安排的上机实验的目的可以概括为如下几个方面: (1)加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常,实验题中的问题比平时的习题复杂得多,也更接近实际。实验着眼于原理与应用的结合点,使学生学会如何把书上学到的知识用于解决实际问题,培养软件工作所需要的动手能力;另一方面,能使书上的知识变" 活" ,起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时,觉得无从下手。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出
现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法,而实验题是软件设计的综合训练,包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧,多人合作,以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容,进一步提高灵活运用数据结构、算法和程序设计技术的能力,而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点,使学生学会如何把书本上和课堂上学到的知识用于解决实际问题,从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境,学习上机调试程序一个程序从编辑,编译,连接到运行,都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件,软件条件,只有学会使用这些环境,才能进行 程序开发工作。通过上机实验,熟练地掌握程序的开发环境,为以后真正编写计算机程序解决实际问题打下基础。同时,在今后遇到其它开发环境时就会触类旁通,很快掌握新系统的使用。 完成程序的编写,决不意味着万事大吉。你认为万无一失的程序,实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误,也能够顺利运行,但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误,只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作,尽快掌握程序调试方法是非常重要的。分析问题,选择算法,编好程序,只能说完成一半工作,另一半工作就是调试程序,运行程序并得到正确结果。 二、实验要求 常用的软件开发方法,是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高,但为了培养一个软件工作者所应具备的科学工作的方法和作风,也应遵循以下五个步骤来完成实验题目: 1) 问题分析和任务定义 在进行设计之前,首先应该充分地分析和理解问题,明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型,而是对所需完成的任务作出明确的回答。例如:输入数据的类型、值的范围以及输入的
一,实验题目 实验十一:图实验 采用邻接表存储有向图,设计算法判断任意两个顶点间手否存在路径。 二,问题分析 本程序要求采用邻接表存储有向图,设计算法判断任意两个顶点间手否存在路径,完成这些操作需要解决的关键问题是:用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1,数据的输入形式和输入值的范围:输入的图的结点均为整型。 2,结果的输出形式:输出的是两结点间是否存在路径的情况。 3,测试数据:输入的图的结点个数为:4 输入的图的边得个数为:3 边的信息为:1 2,2 3,3 1 三,概要设计 (1)为了实现上述程序的功能,需要: A,用邻接表的方式构建图 B,深度优先遍历该图的结点 C,判断任意两结点间是否存在路径 (2)本程序包含6个函数: a,主函数main() b,用邻接表建立图函数create_adjlistgraph() c,深度优先搜索遍历函数dfs() d,初始化遍历数组并判断有无通路函数dfs_trave() e,输出邻接表函数print() f,释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示: 四,详细设计 (1)邻接表中的结点类型定义:
typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; (2)邻接表中头结点的类型定义: typedef struct{ char vexdata; arcnode *firstarc; }adjlist; (3)邻接表类型定义: typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; (4)深度优先搜索遍历函数伪代码: int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } (5)初始化遍历数组并判断有无通路函数伪代码: void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五,源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组
《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程,是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法,介绍了常用的多种查找和排序技术,并做了性能分析和比较,内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: (1)内容丰富,学习量大,给学习带来困难; (2)贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点; (3)所用到的技术多,而在此之前的各门课程中所介绍的专业性知识又不多,因而加大了学习难度; (4)隐含在各部分的技术和方法丰富,也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性,设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练,突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时,觉得无从下手,做起来特别费劲。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程,理解和掌握算法设计所需的技术,为整个专业学习打好基础,要求运用所学知识,上机解决一些典型问题,通过分析、设计、编码、调试等各环节的训练,使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法,如算法设计的构思方法,动态链表,算法的编码,递归技术,与特定问题相关的技术等,要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上,掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时,要求完成以下六个题目: 实习一约瑟夫环问题(2学时)
实验三二叉树的遍历 一、实验目的 1、熟悉二叉树的结点类型和二叉树的基本操作。 2、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解,逐步培养解决实际问题的编程能力。 二、实验环境 运行C或VC++的微机。 三、实验内容 1、依次输入元素值,以链表方式建立二叉树,并输出结点的值。 2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。 四、设计思路 1. 对于这道题,我的设计思路是先做好各个分部函数,然后在主函数中进行顺序排列,以此完成实验要求 2.二叉树采用动态数组 3.二叉树运用9个函数,主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数,关键在于访问节点 五、程序代码 #include
int data; //数据域 struct TNode *lchild,*rchild; // 指针域包括左右孩子指针 }TNode,*Tree; void CreateT(Tree *T)//创建二叉树按,依次输入二叉树中结点的值 { int a; scanf("%d",&a); if(a==00) // 结点的值为空 *T=NULL; else // 结点的值不为空 { *T=(Tree)malloc(sizeof(TNode)); if(!T) { printf("分配空间失败!!TAT"); exit(ERROR); } (*T)->data=a; CreateT(&((*T)->lchild)); // 递归调用函数,构造左子树 CreateT(&((*T)->rchild)); // 递归调用函数,构造右子树 } } void InitT(Tree *T)//构建空二叉树 { T=NULL; } void DestroyT(Tree *T)//销毁二叉树 { if(*T) // 二叉树非空 { DestroyT(&((*T)->lchild)); // 递归调用函数,销毁左子树 DestroyT(&((*T)->rchild)); // 递归调用函数,销毁右子树 free(T); T=NULL; } } void visit(int e)//访问结点 { printf("%d ",e); }
线性表 代码一 #include "stdio.h" #include "malloc.h" #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { int * elem; int length; int listsize; }SqList; int InitList_Sq(SqList *L) { L->elem = (int*)malloc(LIST_INIT_SIZE*sizeof(int)); if (!L->elem) return ERROR; L->length = 0; L->listsize = LIST_INIT_SIZE; return OK; } int ListInsert_Sq(SqList *L, int i,int e) { int *p,*newbase,*q; if (i < 1 || i > L->length+1) return ERROR; if (L->length >= L->listsize) { newbase = (int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof (int)); if (!newbase) return ERROR; L->elem = newbase; L->listsize += LISTINCREMENT; } q = &(L->elem[i-1]); //插入后元素后移for(p=&(L->elem[L->length-1]);p>=q;p--) *(p+1)=*p; *q=e; L->length++; return OK; } int ListDelete_Sq(SqList *L, int i, int *e) {
图实验一,邻接矩阵的实现 1.实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历 3.设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10;
template
#include
数据结构实验报告 一.题目要求 1)编程实现二叉排序树,包括生成、插入,删除; 2)对二叉排序树进行先根、中根、和后根非递归遍历; 3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么? 二.解决方案 对于前三个题目要求,我们用一个程序实现代码如下 #include #include return q; } void Delete_m(Link &L, Link p, Link q)//删除第m个{ p->next = q->next; free(q); } void main() { Link L, p, q; int n, m; L = NULL; InitList(L);//构造出一个只有头结点的空链表 printf("请输入初始密码人数每个人的密码:\n"); scanf("%d", &m);//初始密码为m scanf("%d", &n);// Creatlinklist(n, L);//构建 p = L; for (int i = 1; i <= n; i++) { q = Locate_m(p, m);//找到第m个 printf("%d", q->num); Delete_m(L, p, q);//删除第m个 } system("pause"); } 邻接矩阵的实现 1. 实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历3.设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 数据结构实验报告全集 实验一线性表基本操作和简单程序 1.实验目的 (1)掌握使用Visual C++ 6.0上机调试程序的基本方法; (2)掌握线性表的基本操作:初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2.实验要求 (1)认真阅读和掌握和本实验相关的教材内容。 (2)认真阅读和掌握本章相关内容的程序。 (3)上机运行程序。 (4)保存和打印出程序的运行结果,并结合程序进行分析。 (5)按照你对线性表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果 实验代码: 1)头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表,由用户输入各结点data域之值,//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 《数据结构》第六次实验报告 学生姓名 学生班级 学生学号 指导老师 一、实验内容 1) 采用二叉树链表作为存储结构,完成二叉树的建立,先序、中序和后序 以及按层次遍历的操作,求所有叶子及结点总数的操作。 2) 输出树的深度,最大元,最小元。 二、需求分析 遍历二叉树首先有三种方法,即先序遍历,中序遍历和后序遍历。 递归方法比较简单,首先获得结点指针如果指针不为空,且有左子,从左子递归到下一层,如果没有左子,从右子递归到下一层,如果指针为空,则结束一层递归调用。直到递归全部结束。 下面重点来讲述非递归方法: 首先介绍先序遍历: 先序遍历的顺序是根左右,也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下:如果结点的指针不为空,结点指针入栈,输出相应结点的数据,同时指针指向其左子,如果结点的指针为空,表示左子树访问结束,栈顶结点指针出栈,指针指向其右子,对其右子树进行访问,如此循环,直至结点指针和栈均为空时,遍历结束。 再次介绍中序遍历: 中序遍历的顺序是左根右,中序遍历和先序遍历思想差不多,只是打印顺序稍有变化。具体实现算法如下:如果结点指针不为空,结点入栈,指针指向其左子,如果指针为空,表示左子树访问完成,则栈顶结点指针出栈,并输出相应结点的数据,同时指针指向其右子,对其右子树进行访问。如此循环直至结点指针和栈均为空,遍历结束。 最后介绍后序遍历: 后序遍历的顺序是左右根,后序遍历是比较难的一种,首先需要建立两个栈,一个用来存放结点的指针,另一个存放标志位,也是首先访问根结点,如果结点的指针不为空,根结点入栈,与之对应的标志位也随之入标志位栈,并赋值0,表示该结点的右子还没有访问,指针指向该结点的左子,如果结点指针为空,表示左子访问完成,父结点出栈,与之对应的标志位也随之出栈,如果相应的标志位值为0,表示右子树还没有访问,指针指向其右子,父结点再次入栈,与之对应的标志位也入栈,但要给标志位赋值为1,表示右子访问过。如果相应的标志位值为1,表示右子树已经访问完成,此时要输出相应结点的数据,同时将结点指针赋值为空,如此循环直至结点指针和栈均为空,遍历结束。 三、详细设计 源代码: 顺序表的基本操作 #include int j=0; while(L.data[j]!=x) j++; if(j==https://www.doczj.com/doc/5811884690.html,st) { cout<<"所查找值不存在!"< 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列,要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 2009级数据结构实验报告 实验名称:约瑟夫问题 学生姓名:李凯 班级:21班 班内序号:06 学号:09210609 日期:2010年11月5日 1.实验要求 1)功能描述:有n个人围城一个圆圈,给任意一个正整数m,从第一个人开始依次报数,数到m时则第m个人出列,重复进行,直到所有人均出列为止。请输出n个人的出列顺序。 2)输入描述:从源文件中读取。 输出描述:依次从显示屏上输出出列顺序。 2. 程序分析 1)存储结构的选择 单循环链表 2)链表的ADT定义 ADT List{ 数据对象:D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系:R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作: ListInit(&L);//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表,若是,则返回1,否则返回0. ListLength(L); //求单链表L的长度 GetElem(L,i);//返回链表L中第i个数据元素的值; ListSort(LinkList [内容要求] 1、存储结构:顺序表、单链表或其他存储结构,需要画示意图,可参考书上P59 页图2-9 2.2 关键算法分析 结点类: template ******************************* 实验题目:二叉树的操作 实验者信息:班级13007102,姓名庞文正,学号1300710226 实验完成的时间3:00 ****************************** 一、实验目的 1,掌握二叉树链表的结构和二叉树的建立过程。 2,掌握队列的先进先出的运算原则在解决实际问题中的应用。 3,进一步掌握指针变量、指针数组、动态变量的含义。 4,掌握递归程序设计的特点和编程方法。 二、实验内容 已知以二叉链表作存储结构,试编写按层次遍历二叉树的算法。(所谓层次遍历,是指从二叉树的根结点开始从上到下逐层遍历二叉树,在同一层次中从左到右依次访问各个节点。)调试程序并对相应的输出作出分析;修改输入数据,预期输出并验证输出的结果。加深对算法的理解。 三、算法设计与编码 1.本实验用到的理论知识 总结本实验用到的理论知识,实现理论与实践相结合。总结尽量简明扼要,并与本次实验密切相关,最好能加上自己的解释。 本算法要采用一个循环队列que,先将二叉树根结点入队列,然后退队列,输出该结点;若它有左子树,便将左子树根结点入队列;若它有右子树,便将右子树根结点入队列,直到队列空为止。因为队列的特点是先进先出,从而达到按层次顺序遍历二叉的目的。2.算法概要设计 给出实验的数据结构描述,程序模块、功能及调用关系 #include 学生实验报告 学院:软通学院 课程名称:数据结构与算法 专业班级:软件142 班 姓名:邹洁蒙 学号: 0143990 学生实验报告 (二) 一、实验综述 1、实验目的及要求 目的:1)掌握树与二叉树的基本概念; 2)掌握二叉树的顺序存储,二叉链表的先序遍历中序遍历和后序遍历算法; 3)掌握树的双亲表示法。 要求:1)编程:二叉树的顺序存储实现; 2)编程:二叉链表的先序遍历中序遍历和后序遍历实现; 3)编程:树的双亲表示法实现。 2、实验仪器、设备或软件 设备:PC 软件:VC6 二、实验过程(编程,调试,运行;请写上源码,要求要有注释) 1.编程:二叉树的顺序存储实现 代码: BiTree::BiTree()//建立存储空间 { data = new int[MAXSIZE]; count = 0; } void BiTree::AddNode(int e)//加结点 { int temp = 0; data[count] = e; count++;//从编号0开始保存 } 运行截图: 2.编程:二叉链表的先序遍历中序遍历和后序遍历实现代码: void InOrderTraverse(BiTree* Head)//中序遍历 { if (Head) { InOrderTraverse(Head->LeftChild); cout << Head->data<<" "; InOrderTraverse(Head->RightChild); } } void PreOrderTraverse(BiTree* Head)//先序遍历 { if (Head) { cout << Head->data << " "; PreOrderTraverse(Head->LeftChild); PreOrderTraverse(Head->RightChild); } } void PostOrderTraverse(BiTree* Head)//后序遍历 { if (Head) { PostOrderTraverse(Head->LeftChild); PostOrderTraverse(Head->RightChild); cout << Head->data << " "; } } 运行截图: #include数据结构实验一的源代码
数据结构实验报告图实验
数据结构实验报告全集
数据结构实验报告-二叉树的实现与遍历
数据结构实验程序
数据结构实验
数据结构实验报告模板
数据结构实验-二叉树的操作
数据结构实验报告之树与二叉树
数据结构上机实验线性表单链表源代码