数据结构实验报告-二叉树的实现与遍历
《数据结构》第六次实验报告
学生姓名
学生班级
学生学号
指导老师
一、实验内容
1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序
以及按层次遍历的操作，求所有叶子及结点总数的操作。
2) 输出树的深度，最大元，最小元。
二、需求分析
遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。
递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。
下面重点来讲述非递归方法：
首先介绍先序遍历：
先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。
再次介绍中序遍历：
中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。
最后介绍后序遍历：
后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。
三、详细设计
源代码：
#include<>
#define MAX 100 //表示栈的最大容量
#define FULL 99//表示栈满
#define EMPTY -1//表示栈空
typedef struct Tnode //定义结点
{
char data;//存储结点数据
struct Tnode *left;//定义结点左子指针
struct Tnode *right;//定义右子指针
}Tnode,*Pnode;//声明Tnode类型的变量和指针typedef struct Stack//定义栈
{
Pnode pnode[MAX];//存放数据
int p;//栈顶指针
}Stack,*Pstack;//定义Stack类型的变量和指针void Push (Pstack pstack,Pnode pnode)//入栈{
pstack->p ++;
pstack->pnode[pstack->p] = pnode;//赋值}
Pnode Pop(Pstack pstack)//出栈
{
return pstack->pnode[pstack->p--];
}
Pnode Top (Pstack pstack)//看栈顶元素
{
return pstack->pnode[pstack->p];
}
int Isempty (Pstack pstack)//栈判空
{
if(pstack->p==EMPTY)
return 1;
else
return 0;;
}
int Isfull (Pstack pstack )//栈满
{
if (pstack ->p==FULL)
return 1;
else
return 0;
}
void Initstack (Pstack pstack)//初始化栈
{
pstack->p=EMPTY;
}
void Inittnode(Pnode root,Pnode left,Pnode right,char data)//初始化结点{
root->left=left;
root->right = right;
root->data = data;
}
void PreorderR(Pnode proot)//递归先序遍历算法
{
if(proot)
{
printf("%2c",proot->data);
PreorderR(proot->left);
PreorderR(proot->right);
}
}
void InorderR(Pnode proot)//递归中序遍历算法
{
if(proot)
{
InorderR(proot->left);
printf("%2c",proot->data);
InorderR(proot->right);
}
}
void PostorderR(Pnode proot)//递归后序遍历算法
{
if(proot)
{
PostorderR(proot->left);
PostorderR(proot->right);
printf("%2c",proot->data);
}
}
void PreorderI(Pnode proot,Pstack pstack)//非递归先序遍历算法
{
Initstack(pstack);//初始化栈
while(proot||!Isempty(pstack))//如果栈空并且结点指针空，则结束循环{
if(proot)
{
printf("%2c",proot->data);
if(Isfull(pstack))//如果栈满不能执行入栈操作
{
printf("栈满，不能执行入栈操作！！");
return;
}
Push(pstack,proot);//入栈
proot=proot->left;//指针指向左子
}
else
{
if(Isempty(pstack))//栈空时不能出栈
{
printf("栈空，不能执行出栈操作！！");
return;
}
proot = Pop(pstack);//执行出栈操作
proot=proot->right;//指针指向右子
}
}
}
void InorderI(Pnode proot,Pstack pstack)//非递归中序遍历算法{
Initstack(pstack);//初始化栈
while(proot||!Isempty(pstack))//循环结束条件
{
if(proot)
{
if(Isfull(pstack))
{
printf("栈满，不能执行入栈操作！！");
return;
}
Push(pstack,proot);//执行入栈操作
proot = proot->left;//指针指向左子
}
else
{
if(Isempty(pstack))
{
printf("栈空，不能执行出栈操作！！");
return ;
}
proot = Pop(pstack);//出栈
printf("%2c",proot->data);//打印数据
proot=proot->right;//指针指向右子
}
}
}
void PostorderI(Pnode proot,Pstack pstack)//非递归后续遍历算法{
int flags[MAX];//定义标志位栈
int p =-1;//初始化标志位栈
int flag;//存放标志位
Initstack(pstack);//初始化栈
while(proot||!Isempty(pstack))//循环结束条件
{
if(proot)
{
if(Isfull(pstack))
{
printf("栈满，不能执行入栈操作！！");
return ;
}
flags[++p] = 0;//标志位置0，并入栈
Push(pstack,proot);//结点入栈
proot=proot->left;//指针指向左子
}
else
{
proot = Pop(pstack);//指针出栈
flag = flags[p--];//相应标志位出栈
if(flag==0)//如果标志位为0表示右子还未访问过
{
flag =1;//将标志位置1，右子已访问
flags[++p] = flag;//标志位入栈
Push(pstack,proot);//结点入栈
proot = proot->right;//指针指向右子
}
else
{
printf("%2c",proot->data);//打印数据
proot = NULL;//将结点指针置空
}
}
}
}
void main ()
{
Tnode A,B,C,D,E,F,G;//声明结点变量
Stack stack;//声明栈
Inittnode(&A,&B,&C,'A');//初始化结点
Inittnode(&B,NULL,&D,'B');
Inittnode(&C,&E,&F,'C');
Inittnode(&D,NULL,NULL,'D');
Inittnode(&E,NULL,NULL,'E');
Inittnode(&F,&G,NULL,'F');
Inittnode(&G,NULL,NULL,'G');
printf("你定义的树的结构是：\n");
/*一下是调用相应的函数输出遍历结果*/
printf("A(B(D)C(E F(G)))\n");
printf("=====================下面是遍历结果====================\n");
printf("=====================递归先序遍历：====================\n");
PreorderR(&A);
printf("\n");
printf("=====================非递归先序遍历：==================\n");
PreorderI(&A,&stack);
printf("\n");
printf("=====================递归中序遍历：====================\n");
InorderR(&A);
printf("\n");
printf("=====================非递归中序遍历：==================\n");
InorderI(&A,&stack);
printf("\n");
printf("=====================递归后序遍历：====================\n");
PostorderR(&A);
printf("\n");
printf("=====================非递归后序遍历：==================\n");
PostorderI(&A,&stack);
printf("\n");
}
五、遇到的问题及解决办法
这部分我主要遇到如下两个问题，其内容和解决方法如下所列：执行程序时程序停止运行，其效果如图：
解决方法：看到程序停止运行，推测可能的原因：遇到死循环、参数设置不合理或者结构体没有造好。首先对结构体进行了检查，各个成员声明正常无误，在对程序进行调试，程序正常跳出循环，因此最可能是自定义函数的参数设置的不合理，因此对调用的自定义函数进行相应的改动，将参数由具体类型改为指针类型后，程序正常运行。
程序不停的输出同一个结点的数据，其效果入图：
解决方法：分析运行结果可知，第一不停的输出证明遇到了死循环，第二输出的是同一个结点的数据，表示指针没有按预期进行指向，首先对程序进行调试，发现程序没有添加循环结束条件，添加循环结束条件后，只能输出树的部分结点的数据，对标志位进行修改后，程序运行正常，也能正确输出遍历结果。
六、心得体会
通过这次作业真的受益匪浅，感触良多：
首先，要提高编程能力，必须多动手，多实践，而不是仅仅局限在书本上，更不能眼高手低。眼高手低，懒得动手，这就犯了编程人员的大忌。大一我们开始接触C语言，这是我们接触到的第一种编程语言，但是当时徒有对编程的兴趣，却没有付诸行动，动手少，结果考试险过，通过这次作业，我再次看了C语言课本，边看边写代码，理解快，印象深刻，思维也活跃许多，状态也好，真正的意识到，编程能力需要靠实践来提升。
当自己写出意想的程序后，真的有些成就感。再者，在吴老师的指导和要求下，我们改掉了很多的编程坏习惯的同时也养成了良好的编程习惯，另一方面我们态度端正了很多，认真完成好每一项任务，这样无形中提高了对自己的要求，同时也增强了我们的动手能力和编程能力。
七、附录
运行结果截图。
数据结构课程实验指导书
数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程，也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法，并做了相应的性能分析和比较，课程内容丰富，理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： 1）理论艰深，方法灵活，给学习带来困难； 2）内容丰富，涉及的知识较多，学习有一定的难度； 3）侧重于知识的实际应用，要求学生有较好的思维以及较强的分析和解决问题的能力，因而加大了学习的难度； 根据《数据结构》课程本身的特性，通过实验实践内容的训练，突出构造性思维训练的特征，目的是提高学生分析问题，组织数据及设计大型软件的能力。 课程上机实验的目的，不仅仅是验证教材和讲课的内容，检查自己所编的程序是否正确，课程安排的上机实验的目的可以概括为如下几个方面： （1）加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变" 活" ，起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时，觉得无从下手。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出
现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境，学习上机调试程序一个程序从编辑，编译，连接到运行，都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件，软件条件，只有学会使用这些环境，才能进行 程序开发工作。通过上机实验，熟练地掌握程序的开发环境，为以后真正编写计算机程序解决实际问题打下基础。同时，在今后遇到其它开发环境时就会触类旁通，很快掌握新系统的使用。 完成程序的编写，决不意味着万事大吉。你认为万无一失的程序，实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作，尽快掌握程序调试方法是非常重要的。分析问题，选择算法，编好程序，只能说完成一半工作，另一半工作就是调试程序，运行程序并得到正确结果。 二、实验要求 常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目： 1) 问题分析和任务定义 在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的
数据结构二叉树实验报告
实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。 二、实验环境 运行Ｃ或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) {
二叉树的建立及其应用程序代码
#include
{ inorder(p->lchild); printf("%c ",p->data); inorder(p->rchild); } } void postorder(TREE *p) //后序遍历 { if (p!=NULL) { postorder(p->lchild); postorder(p->rchild); printf("%c ",p->data); } } void shu(TREE *p,int len) //数的形状{ if (p!=NULL) { shu(p->lchild,len+1); for (int i=1;i<=4*len;i++) { printf(" "); } printf("%c",p->data); printf("------\n"); shu(p->rchild,len+1); } } int shendu(TREE *p) //计算深度 { int l,r; if (p==NULL) { return 0; } l=shendu(p->lchild)+1; r=shendu(p->rchild)+1; if (l>=r) //左右子树比较return l; else
数据结构实验一的源代码
#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"); }
二叉树实验报告
实验题目：实验九——二叉树实验 算法设计（3） 问题分析： 1、题目要求：编写算法交换二叉树中所有结点的左右子树 2、设计思路：首先定义一个二叉树的数据类型，使用先序遍历建立该二叉树，遍历二叉树，设计左右子树交换的函数，再次遍历交换之后的二叉树，与先前二叉树进行比较。遍历算法与交换算法使用递归设计更加简洁。 3、测试数据： A、输入：1 2 4 0 0 5 0 0 3 0 0 交换前中序遍历：4 2 5 1 3 交换后中序遍历：3 1 5 2 4 交换前：交换后： B、输入：3 7 11 0 0 18 17 0 0 19 0 0 6 13 0 0 16 0 0 交换前中序遍历：11 7 17 18 19 3 13 6 16 交换后中序遍历：16 6 13 3 19 18 17 7 11 概要设计： 1、为了实现上述功能：①构造一个空的二叉树；②应用先序遍历输入，建立二叉树；③中序遍历二叉树；④调用左右子树交换函数；⑤中序遍历交换过后的二叉树。 2、本程序包括4个函数： ①主函数main（） ②先序遍历二叉树建立函数creat_bt（） ③中序遍历二叉树函数inorder（） ④左右子树交换函数 exchange（）
各函数间关系如下： 详细设计： 1、结点类型 typedef struct binode //定义二叉树 { int data; //数据域 struct binode *lchild,*rchild; //左孩子、右孩子 }binode,*bitree; 2、各函数操作 ① 先序遍历建二叉树函数 bitree creat_bt() { 输入结点数据； 判断是否为0{ 若是，为空； 不是，递归；} 返回二叉树； } ② 左右子树交换函数 void exchange(bitree t) { 判断结点是否为空{ 否，交换左右子树； 递归；} } ③ 中序遍历函数 void inorder(bitree bt) { 判断是否为空{ 递归左子树； 输出； 递归右子树；} } main （） creat_bt （） inorder （） exchange （）
二叉树的遍历和应用
内蒙古科技大学 本科生课程设计说明书 题目：数据结构课程设计 ——二叉树的遍历和应用 学生姓名： 学号： 专业： 班级： 指导教师： 2013年5月29日
内蒙古科技大学课程设计说明书 内蒙古科技大学课程设计任务书 I
内蒙古科技大学课程设计说明书 目录 内蒙古科技大学课程设计任务书..............................................................错误！未定义书签。目录....................................................................................................................................II 第一章需求分析 (3) 1.1课程设计目的 (3) 1.2任务概述 (3) 1.3课程设计内容 (3) 第二章概要设计 (5) 2.1设计思想 (5) 2.2二叉树的遍历 (5) 2.3运行界面设计 (6) 第三章详细设计 (7) 3.1二叉树的生成 (7) 3.2二叉树的先序遍历 (7) 3.3 二叉树的中序遍历 (8) 3.4二叉树的后续遍历 (8) 3.5主程序的设计 (8) 第四章测试分析 (11) 4.1二叉树的建立 (11) 4.2二叉树的先序、中序、后序遍历 (11) 第五章课程设计总结 (12) 附录：程序代码 (13) 致谢 ···········································································································错误！未定义书签。 II
数据结构实验报告-二叉树的实现与遍历
《数据结构》第六次实验报告 学生姓名 学生班级 学生学号 指导老师
一、实验内容 1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序 以及按层次遍历的操作，求所有叶子及结点总数的操作。 2) 输出树的深度，最大元，最小元。 二、需求分析 遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。 递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。 下面重点来讲述非递归方法： 首先介绍先序遍历： 先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。 再次介绍中序遍历： 中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。 最后介绍后序遍历： 后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。 三、详细设计 源代码：
数据结构实验程序
顺序表的基本操作 #include int j=0; while(L.data[j]!=x) j++; if(j==https://www.sodocs.net/doc/2310098130.html,st) { cout<<"所查找值不存在！"< 二叉树的建立和遍历的实验报告 篇一：二叉树的建立及遍历实验报告 实验三：二叉树的建立及遍历 【实验目的】 （1）掌握利用先序序列建立二叉树的二叉链表的过程。 （2）掌握二叉树的先序、中序和后序遍历算法。 【实验内容】 1. 编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。 如：输入先序序列abc###de###，则建立如下图所示的二叉树。 并显示其先序序列为：abcde 中序序列为：cbaed 后序序列为：cbeda 【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4．写好代码 5．编译－＞链接－＞调试 #include #include #define OK 1 #define OVERFLOW -2 typedef int Status; typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; }BiTNode,*BiTree; Status CreateBiTree(BiTree &T) { TElemType ch; scanf("%c",&ch); if (ch=='#') T= NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) #include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 100 //栈存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 //------二叉树的存储结构表示------// typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //-----顺序栈的存储结构表示------// typedef struct{ BiTree *top; BiTree *base; int stacksize; }SqStack; //*************************************************** //构造一个空栈s SqStack *InitStack(); //创建一颗二叉树 BiTree CreatBiTree(); //判断栈空 int StackEmpty(SqStack *S); //插入元素e为新的栈顶元素 void Push(SqStack *S,BiTree p); //若栈不为空，则删除s栈顶的元素e，将e插入到链表L中void Pop(SqStack *S,BiTree *q); //非递归先序遍历二叉树 void PreOrderTraverse(BiTree L); //非递归中序遍历二叉树 void InOrderTraverse(BiTree L); //非递归后序遍历二叉树 void PostOrderTraverse(BiTree L); //递归后序遍历二叉树 void PostOrder(BiTree bt); //递归中序遍历二叉树 void InOrder(BiTree bt); //递归先序遍历二叉树 void PreOrder(BiTree bt); //*************************************************** ******************************* 实验题目：二叉树的操作 实验者信息：班级13007102，姓名庞文正，学号1300710226 实验完成的时间3:00 ****************************** 一、实验目的 1,掌握二叉树链表的结构和二叉树的建立过程。 2,掌握队列的先进先出的运算原则在解决实际问题中的应用。 3,进一步掌握指针变量、指针数组、动态变量的含义。 4,掌握递归程序设计的特点和编程方法。 二、实验内容 已知以二叉链表作存储结构，试编写按层次遍历二叉树的算法。（所谓层次遍历，是指从二叉树的根结点开始从上到下逐层遍历二叉树，在同一层次中从左到右依次访问各个节点。）调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。 三、算法设计与编码 1.本实验用到的理论知识 总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，最好能加上自己的解释。 本算法要采用一个循环队列que，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉的目的。2.算法概要设计 给出实验的数据结构描述，程序模块、功能及调用关系 #include 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include >验目的 掌握顺序栈的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。 2.实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）分析问题的要求，编写和调试完成程序。 （3）保存和打印出程序的运行结果，并分析程序的运行结果。 3.实验内容 利用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否正确配对的程序。具体完成如下： （1）定义栈的顺序存取结构。 （2）分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。 （3）定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中，括号配对共有四种情况：左右括号配对次序不正确；右括号多于左括号；左括号多于右括号；左右括号匹配正确。 （4）设计一个测试主函数进行测试。 （5）对程序的运行结果进行分析。 实验代码： #include < > #define MaxSize 100 typedef struct { ??? int data[MaxSize]; ??? int top; }SqStack; void InitStack(SqStack *st) 验目的 （1）进一步掌握指针变量的用途和程序设计方法。 （2）掌握二叉树的结构特征，以及链式存储结构的特点及程序设计方法。 （3）掌握构造二叉树的基本方法。 （4）掌握二叉树遍历算法的设计方法。 3．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）掌握一个实际二叉树的创建方法。 （3）掌握二叉链存储结构下二叉树操作的设计方法和遍历操作设计方法。 4．实验内容 （1）定义二叉链存储结构。 二叉树实验报告 09信管石旭琳 20091004418 一、实验目的： 1、理解二叉树的遍历算法及应用 2、理解哈夫曼树及其应用。 3、掌握哈夫曼编码思想。 二、实验内容： 1、建立二叉树二叉链表 2、实现二叉树递归遍历算法（中序、前序、后序） 3、求二叉树高度 4、求二叉树结点个数 5、求二叉树叶子个数 6、将序号为偶数的值赋给左子树 三、主要程序： #include 江南大学通信与控制工程学院标准实验报告 （实验）课程名称：计算机软件技术基础实验名称：二叉树的遍历和应用 班级：自动化 姓名：李玉书 学号：03 指导教师：卢先领 江南大学通信与控制学院 江南大学 实验报告 学生姓名：张晓蔚学号：0704090304 实验地点：信控机房实验时间：90分钟 一、实验室名称：信控学院计算中心 二、实验项目名称：二叉树的遍历和应用 三、实验学时：4学时 四、实验原理： 二叉树的遍历和应用 五、实验目的： 1、掌握二叉树的数据类型描述及特点。 2、掌握二叉树的存储结构（二叉链表）的建立算法。 3、掌握二叉链表上二叉树的基本运算的实现。 六、实验内容： 阅读后面的程序，并将其输入到计算机中，通过调试为下面的二叉树建立二叉链表，并用递归实现二叉树的先序、中序、后序三种遍历。 七、实验器材（设备、元器件）： 计算机 八、实验步骤： 1、输入示例程序 2、构建按序插入函数实现算法 3、用C语言实现该算法 4、与源程序合并，编译，调试 5、测试，查错，修改 6、生成可执行文件，通过综合测试，完成实验 九、实验数据及结果分析： 测试用例 初始数据：ABDH,,I,,EJ,,K,,CFL,,,G,, 测试结果 十、实验结论： 该程序可以完成线性表的常规功能，且增加了异常处理，在异常情况下，例如： 表空，删除结点号不合法或出界，删除数值未找到等，这些情况下都能作出处理。可以通过边界测试。 十一对本实验过程及方法、手段的改进建议： 对书中程序的几点错误做了改正，见源程序。 附：源程序 #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 二叉树的遍历实验报告 一、需求分析 在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就是二叉树的遍历问题。 对二叉树的数据结构进行定义，建立一棵二叉树，然后进行各种实验操作。 二叉树是一个非线性结构，遍历时要先明确遍历的规则，先访问根结点还时先访问子树，然后先访问左子树还是先访问有右子树，这些要事先定好，因为采用不同的遍历规则会产生不同的结果。本次实验要实现先序、中序、后序三种遍历。 基于二叉树的递归定义，以及遍历规则，本次实验也采用的是先序遍历的规则进行建树的以及用递归的方式进行二叉树的遍历。 二、系统总框图 三、各模块设计分析 （1）建立二叉树结构 建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则来建立的。本实验用的是先序遍历的规则进行建树。 二叉树用链表存储来实现，因此要先定义一个二叉树链表存储结构。因此要先定义一个结构体。此结构体的每个结点都是由数据域data 、左指针域Lchild 、右指针域Rchild 组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。最后，还需要一个链表的头指针指向根结点。 要注意的是，第一步的时候一定要先定义一个结束标志符号，例如空格键、＃等。当它遇到该标志时，就指向为空。 建立左右子树时，仍然是调用create （）函数，依此递归进行下去， 直到遇到结束标志时停止操作。 （2）输入二叉树元素 输入二叉树时，是按上面所确定的遍历规则输入的。最后，用一个返回值来表示所需要的结果。 （3）先序遍历二叉树 当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （4）中序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （5）后序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （6）主程序 需列出各个函数，然后进行函数调用。 四、各函数定义及说明 因为此二叉树是用链式存储结构存储的，所以定义一个结构体用以存储。 typedef struct BiTNode { char data; struct BiTNode *Lchild; struct BiTNode *Rchild; 实验8 二叉树的遍历与应用 一、实验目的 1.进一步掌握指针变量的含义。 2.掌握二叉树的结构特征，理解并熟悉掌握创建二叉树和实现二叉树的三种遍历。 3.学会编写实现二叉树基本操作的递归算法，领会递归的实质。 二、实验要求 1. 给出程序设计的基本思想、原理和算法描述。 2. 源程序给出注释。 3. 保存和打印出程序的运行结果，并结合程序进行分析。 三、实验题目 1.编写算法，按层输出一棵顺序存储的二叉树所有结点的值。 /**********level.c************/ #include 二叉树的建立和遍历的实验报告doc
二叉树的建立及几种简单的遍历方法
数据结构实验-二叉树的操作
数据结构实验报告全集
二叉树的遍历算法实验报告
实验四 二叉树的遍历和应用04
数据结构实验报告之树与二叉树
数据结构上机实验线性表单链表源代码
二叉树的遍历实验报告
实验八：二叉树的遍历与应用