【二叉树的建立和遍历实验报告】二叉树的遍历实验心得
[题目] 建立二叉树并求指定结点路径、深度、叶子个数和左右子树交换。
[问题描述]
要求能够按先序遍历次序输入二叉树中结点的值来构造二叉树T；然后用递归和非递归算法实现二叉树T 的中序遍历；接着编写算法
实现求二叉树T中指定结点的路径，即从键盘输入二叉树T 的任一
结点，可以输出从根结点到该结点所经历的结点；最后编写二叉树
的三个应用算法（求二叉树的深度、求二叉树的叶子结点个数、将二叉树左右子树交换）。
[基本要求]
分别建立二叉树存储结构的输入输出函数、输出中序遍历函数、
指定节点路径函数、求深度函数、求叶子个数函数和将二叉树左右子树交换函数
一、需求与规格说明
1、定义二叉树的存储结构，每个结点中设置三个域，即值域、左指针域、右指针域。要建立二叉树T的链式存储结构，即建立二叉链表。根据输入二叉树结点的形式不同，建立的方法也不同，本系统采用先序序列递归建立二叉树，建立如下图所示的二叉树。应该在程序运行窗口的主控菜单后，先选择“1”并回车，紧接着在程序运行窗口中提示信息“输入二叉树的先序序列结点值:”之后，采用以下字符序列：abc@@de@g@@f@@@ （以@替代空格，但是程序中直接输入空格就是，详细见代码注释）作为建立二叉树T的输入字符序列并回车，窗口出现：二叉树的链式存储结构建立完成!
图1 二叉树的图形结构
2、二叉树的遍历。本系统采用非递归中序遍历算法进行中序遍历，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。需要在程序运行窗口的主控菜单中选择“2”并回车，程序运行窗口会出现以下中序遍历序列：
该二叉树
的中序遍历序列是: cbegdfa
3、求二叉树的指定结点路径。在程序运行窗口的主控菜单中选择“3”并回车，在程序运行窗口中提示信息“输入要求路径的结点值:”输入“g”并回车，会得到结果为：→a→b→d→e→g如果输入“i”并回车，会得到结果为：没有要求的结点！
4、求二叉树的深度。在程序运行窗口的主控菜单中选择“4”并回车，在会得到结果为：该二叉树的深度为：5
5、求二叉树的叶子结点个数。在程序运行窗口的主控菜单中选择“5”并回车，在会得到结果为：该二叉树的叶子结点数为：3
6、将二叉树左右子树交换（此处我用交换后的中序遍历来检验是否成功）。在程序运行窗口的主控菜单中选择“6”并回车.得到结
果为：该二叉树的左右节点已交换成功，其中序遍历序列是：afdgebc
7、退出程序。在程序运行窗口的主控菜单中选择“0”并回车。退出程序。
二、设计
1、设计
在二叉树上无论采用哪种遍历方法，都能够访问遍树中的所有结点。由于访问结点的顺序不同，前序遍历和中序遍历都很难达到设计的要求（求路径）；但采用后序遍历二叉树是可行的，因为后序遍历是最后访问根结点，按这个顺序将访问过的结点存储到一个顺序栈中，然后再输出即可。因此，我们可以非递归地后序遍历二叉树T，当后序遍历访问到结点*p时，此时栈中存放的所有结点均为给定结点*p
的祖先，而由这些祖先便构成了一条从根结点到结点*p之间的路径。而求二叉树的深度和叶子结点数可以直接判断结点孩子的数目来完成，将二叉树的左右子树交换也可以利用递归的方法，交换左右孩子来实现。
2、设计表示
为实现上述的设计思想，首先要定义二叉树的链式存储结构，我
们采用二叉链表的方式，相应的类型说明为：
typedef char DataType;
typedef struct node{
DataType data; struct node *lchild,*rchild;
}BinTNode,*BinTree;
函数接口说明:
Status CreateBiTree(BinTree &bt) //1,按照先序遍历次序递归建立二叉树
Status Inorder(BinTree bt) //2,二叉树非递归中序遍历算法*/
BinTree NodePath(BinTree bt, BinTNode *ch) //3,求二叉树根结点到给定结点*p的路径 int Depth(BinTree bt) //4.求二叉树的深度
int Leaf(BinTree bt)// 5.求二叉树的叶子结点个数
BinTNode *huhuan(BinTNode *p)// 将p指针指向的二叉树的左
右子树进行互换
函数调用关系如图所示：
三、实现注释
二叉树的创建模块: 按照先序遍历次序递归建立二叉树,通过读入的字符，分配存储空间生成新结点后再逐个构建根结点、左子树和右子树。
二叉树中序遍历模块：采用非递归中序遍历算法，先逐步扫描二叉树的左子树，并压入堆栈，如果栈不为空，左子树为空，则弹出栈顶的一个元素并输出。然后再扫描右子树，然后再重复上面的步骤扫描该分支的左子树，直至整棵二叉树都扫描完成。此时输出的序列便是该二叉树的中序遍历序列。语句注释见代码。
二叉树指定结点路径模块：该模块由NodePath、FindBT、Findx 三个函数体构成，main函数通过先调用Findx 函数来查找结点，Findx又通过逐步调用FindBT函数遍历查找结点的路径，最后main 函数再通过调用NodePath函数得到给定结点的路径。该模块需定义全局变量p和found以方便查找，否则容易出错，出错情况见调试报告。语句注释见代码。
求二叉树的深度模块：通过判断左右孩子结点是否存在，如存在（h不等于零），则
有一个孩子h加一，然后比较左右孩子结点数大小，较大的为树的深度。具体见代码。
求二叉树的叶子结点个数模块：判断左右子树的叶子结点是否存在，如存在，则记下，左后返回左右子树叶子结点的和。具体见代码。
二叉树的左右子树进行互换模块：通过指针p指定结点，然后用递归的方法将其孩子结点互换。具体见代码。
四、调试报告
编程的最初阶段，在case4语句中，缺少peak，使得每次执行case4的时候，自动弹出该二叉树的叶子节点数，经过调试后发现，原来是缺少了peak，补上之后，程序正常运行。其实这只是很小的问题！在调试中，还有很多的问题，如果在这里一一列举，恐怕很难写完。具体的看运行结果吧。
五、程序清单
#include
#include
#define num 100
#define OK 1
typedef int Status;
typedef char DataType;
typedef struct node{
DataType data; struct node *lchild,*rchild;
}BinTNode,*BinTree;
int found;
BinTNode *p;
Status CreateBiTree(BinTree &bt) //1.按照先序遍历次序递建立二叉树。
{ //ABC@@DE@G@@F@@@ 以@代替空格。但是程序中直接输入空格。
char ch; printf("ch="); scanf("%c",&ch); getchar(); if (ch==" ") bt=NULL; //程序中直接输入空格，不用以@代替空格。
} else { bt=(BinTNode *)malloc(sizeof(BinTNode));
bt->data=ch; //生成根结点 CreateBiTree(bt->lchild); //构造左子树 CreateBiTree(bt->rchild); //构造右子树 } return OK;
Status Inorder(BinTree bt) //二叉树非递中序遍历算法
{ BinTNode *stack[num]; //定义栈数组
}
BinTree NodePath(BinTree bt, BinTNode *ch) //3.求二叉树指定结点的路径 { typedef enum{FALSE,TRUE}boolean;
BinTNode *stack[num];//定义栈
int i,top,tag[num];
boolean find;
BinTNode *s;
find=FALSE;//初始化
int top=0; //初始化栈 stack[top]=bt; do
{ while(NULL!=stack[top]) //扫描根结点及其所有的左结点并入栈{ top=top+1; } top=top-1; //退栈 if(top>=0) //判断栈是否为空{ printf("%c",stack[top]->data); //访问结点 }
stack[top]=stack[top]->rchild; //扫描右子树
stack[top]=stack[top-1]->lchild; }while(top>=0); return OK; top=0;
s=bt;
do
{while(s!=NULL)
{ top++; } if(top>0) {s=stack[top]; if(tag[top]==1)
{ if(s==ch) {for(i=1;i%c",stack[i]->data); stack[top]=s;
tag[top]=0; s=s->lchild; find=TRUE; top--; }else
s=stack[top]; }//endif if(top>0&&!find) { if(tag[top]!=1) { s=s->rchild;//扫描右子树 tag[top]=1; } else s=NULL; }//end if } //endif
}while(!find&&top!=0);
return s;
}
void FindBT(BinTree bt,DataType x)
{ if((bt!=NULL)&&!found)
} { if(bt->data==x) } { p=bt; found=1; } else
{ FindBT(bt->lchild,x); FindBT(bt->rchild,x); }
BinTNode *Findx(BinTree bt,DataType x)
{ int found=0;
}
int Depth(BinTree bt) //4.求二叉树的深度
{ int h,lh,rh;
if (bt==NULL) h=0; else { lh=Depth(bt->lchild);
rh=Depth(bt->rchild); if (lh>=rh) h=lh+1; else h=rh+1; BinTree p=NULL; FindBT(bt,x); return(p); } return h;
}//Depth
int Leaf(BinTree bt) //5.求二叉树的叶子结点个数
{ if (bt==NULL) return 0;
else if (bt->lchild==NULL&&bt->rchild==NULL) return 1; else return Leaf(bt->lchild)+Leaf(bt->rchild);
}//Leaf
BinTNode *huhuan(BinTNode *p)
//将p指针指向的二叉树的左右子树进行互换。 {BinTNode *stack[num];//指针类型的堆栈
int k=0;
stack[k]=NULL;
if(p!=NULL)//交换p结点的左右孩子
{ k++;
stack[k]=p->lchild;
p->lchild=p->rchild;
p->rchild=stack[k];
p->lchild=huhuan(p->lchild);
p->rchild=huhuan(p->rchild);
} return (p);
}
void main()
{ BinTree bt;
//BinTNode *root; char ch1; int xz=1,sd=0,yz=0; while(xz) { printf(" 建立二叉树并求指定结点路径 \n");
printf("============================\n"); printf(" 1.建立二叉树的存储结构 \n"); printf(" 2.求解二叉树的中序遍历 \n"); printf(" 3.求二叉树指定结点的路径 \n"); printf(" 4.求二叉树的深度 \n"); printf(" 5.求二叉树的叶子结点个数 \n");
printf(" 6.将二叉树左右子树交换 \n"); printf(" 0.退出系统
\n"); printf("============================\n"); printf(" 请选择：(0-6) \n");
getchar(); switch(xz)
{ // 输入:ABC@@DE@G@@F@@@ 输出: CBEGDFA case 1:printf("
输入二叉树的先序序列结点值:\n");
CreateBiTree(bt); printf( "二叉树的链式存储结构建立完
成!\n"); peak; case 2:printf("该二叉树的中序遍历序列是:\n"); Inorder(bt); printf( "\n"); peak; case 3:printf( "请输入要求路径的结点值：\n" ); ch1=getchar(); p=NULL; found=0;
Findx(bt,ch1); if(p!=NULL) NodePath(bt,p); else printf( "没
有要求的节点！ \n" ); printf( "\n" ); peak; case 4:sd=Depth(bt); printf( "该二叉树的深度为：%d \n ",sd ); printf("\n"); peak; case 5:yz=Leaf(bt); printf( "该二叉树的叶子节点数为：\n%d
\n",yz ); printf( "\n" ); peak;
printf( "该二叉树的左右结点已交换成功，其中序遍历序列是:\n" );
Inorder(bt);
printf( "\n" );
peak;
}// switch
}// while
}
六、运行结果截图
11
文献：
[1]严蔚敏,吴伟民.数据结构(C 语言版).:清华出版社,xx
[2]严蔚敏,吴伟民等.数据结构题集(C 语言版).北京:清华大学出版社,xx
[3]苏仕华等.数据结构程设计.北京:机械工业出版社,xx
12
内容仅供参考
实验题目：实验九——二叉树实验 算法设计（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 （）
实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 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); }
二叉树的建立和遍历的实验报告 篇一：二叉树的建立及遍历实验报告 实验三：二叉树的建立及遍历 【实验目的】 （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))))
江南大学通信与控制工程学院标准实验报告 （实验）课程名称：计算机软件技术基础实验名称：二叉树的遍历和应用 班级：自动化 姓名：李玉书 学号：03 指导教师：卢先领 江南大学通信与控制学院
江南大学 实验报告 学生姓名：张晓蔚学号：0704090304 实验地点：信控机房实验时间：90分钟 一、实验室名称：信控学院计算中心 二、实验项目名称：二叉树的遍历和应用 三、实验学时：4学时 四、实验原理： 二叉树的遍历和应用 五、实验目的： 1、掌握二叉树的数据类型描述及特点。 2、掌握二叉树的存储结构（二叉链表）的建立算法。 3、掌握二叉链表上二叉树的基本运算的实现。 六、实验内容： 阅读后面的程序，并将其输入到计算机中，通过调试为下面的二叉树建立二叉链表，并用递归实现二叉树的先序、中序、后序三种遍历。 七、实验器材（设备、元器件）： 计算机 八、实验步骤： 1、输入示例程序 2、构建按序插入函数实现算法 3、用C语言实现该算法 4、与源程序合并，编译，调试 5、测试，查错，修改
6、生成可执行文件，通过综合测试，完成实验 九、实验数据及结果分析： 测试用例 初始数据：ABDH,,I,,EJ,,K,,CFL,,,G,, 测试结果 十、实验结论： 该程序可以完成线性表的常规功能，且增加了异常处理，在异常情况下，例如： 表空，删除结点号不合法或出界，删除数值未找到等，这些情况下都能作出处理。可以通过边界测试。 十一对本实验过程及方法、手段的改进建议： 对书中程序的几点错误做了改正，见源程序。 附：源程序 #include
实验8 二叉树的遍历与应用 一、实验目的 1.进一步掌握指针变量的含义。 2.掌握二叉树的结构特征，理解并熟悉掌握创建二叉树和实现二叉树的三种遍历。 3.学会编写实现二叉树基本操作的递归算法，领会递归的实质。 二、实验要求 1. 给出程序设计的基本思想、原理和算法描述。 2. 源程序给出注释。 3. 保存和打印出程序的运行结果，并结合程序进行分析。 三、实验题目 1.编写算法，按层输出一棵顺序存储的二叉树所有结点的值。 /**********level.c************/ #include
二叉树实验报告 09信管石旭琳 20091004418 一、实验目的： 1、理解二叉树的遍历算法及应用 2、理解哈夫曼树及其应用。 3、掌握哈夫曼编码思想。 二、实验内容： 1、建立二叉树二叉链表 2、实现二叉树递归遍历算法（中序、前序、后序） 3、求二叉树高度 4、求二叉树结点个数 5、求二叉树叶子个数 6、将序号为偶数的值赋给左子树 三、主要程序： #include
二叉树的遍历实验报告 一、需求分析 在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就是二叉树的遍历问题。 对二叉树的数据结构进行定义，建立一棵二叉树，然后进行各种实验操作。 二叉树是一个非线性结构，遍历时要先明确遍历的规则，先访问根结点还时先访问子树，然后先访问左子树还是先访问有右子树，这些要事先定好，因为采用不同的遍历规则会产生不同的结果。本次实验要实现先序、中序、后序三种遍历。 基于二叉树的递归定义，以及遍历规则，本次实验也采用的是先序遍历的规则进行建树的以及用递归的方式进行二叉树的遍历。 二、系统总框图
三、各模块设计分析 （1）建立二叉树结构 建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则来建立的。本实验用的是先序遍历的规则进行建树。 二叉树用链表存储来实现，因此要先定义一个二叉树链表存储结构。因此要先定义一个结构体。此结构体的每个结点都是由数据域data 、左指针域Lchild 、右指针域Rchild 组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。最后，还需要一个链表的头指针指向根结点。 要注意的是，第一步的时候一定要先定义一个结束标志符号，例如空格键、＃等。当它遇到该标志时，就指向为空。 建立左右子树时，仍然是调用create （）函数，依此递归进行下去，
直到遇到结束标志时停止操作。 （2）输入二叉树元素 输入二叉树时，是按上面所确定的遍历规则输入的。最后，用一个返回值来表示所需要的结果。 （3）先序遍历二叉树 当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （4）中序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （5）后序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （6）主程序 需列出各个函数，然后进行函数调用。 四、各函数定义及说明 因为此二叉树是用链式存储结构存储的，所以定义一个结构体用以存储。 typedef struct BiTNode { char data; struct BiTNode *Lchild; struct BiTNode *Rchild;
南昌大学实验报告 学生姓名：李木子学号：专业班级：软工 实验类型：□验证□综合□设计□创新实验日期：实验成绩：一、实验项目名称 二叉树的遍历 二、实验目的 学会链式二叉树的结构体定义，创建与前序中序后序遍历三、实验基本原理 四、主要仪器设备及耗材 电脑， 五、实验步骤 ************************************** * 链式二叉树的创建与遍历 * ************************************** ************************************** * 链式二叉树的结构体定义 * ************************************** <> <> ; { ; *; *; };
************************************** * 链式二叉树函数声明 * ************************************** *(); (*); (*); (*); ************************************** * 链式二叉树创建函数 * ************************************** *() { ; *; (); ('') ; ('\'); { (*)(()); >; >(); >(); } ; } ************************************** * 链式二叉树递归前序遍历函数 * ************************************** (*) { () { ("\">);
竭诚为您提供优质文档/双击可除二叉树的建立和遍历的实验报告 篇一：二叉树遍历实验报告 数据结构实验报告 报告题目：二叉树的基本操作学生班级： 学生姓名：学号： 一．实验目的 1、基本要求：深刻理解二叉树性质和各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算；熟练掌握二叉树的遍历算法；。 2、较高要求:在遍历算法的基础上设计二叉树更复杂操作算法；认识哈夫曼树、哈夫曼编码的作用和意义;掌握树与森林的存储与便利。二.实验学时： 课内实验学时：3学时课外实验学时：6学时三．实验题目 1．以二叉链表为存储结构，实现二叉树的创建、遍历（实验类型：验证型）1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能：1…建立树2…前序
遍历树3…中序遍历树4…后序遍历树5…求二叉树的高度6…求二叉树的叶子节点7…非递归中序遍历树0…结束2）实验要求：在程序中定义下述函数，并实现要求的函数功能：createbinTree(binTree structnode*lchild,*rchild; }binTnode;元素类型： intcreatebinTree(binTree voidpreorder(binTreevoidInorder(binTree voidpostorder(binTreevoidInordern(binTreeintleaf(bi nTree intpostTreeDepth(binTree 2、编写算法实现二叉树的非递归中序遍历和求二叉树高度。1）问题描述：实现二叉树的非递归中序遍历和求二叉树高度2）实验要求：以二叉链表作为存储结构 3)实现过程： 1、实现非递归中序遍历代码： voidcbiTree::Inordern(binTreeinttop=0;p=T;do{ while(p!=nuLL){ stack[top]=p;;top=top+1;p=p->lchild;}; if(top>0){ top=top-1;p=stack[top];
二叉树的创建与遍历 一、试验内容 根据输入的字符串创建树或二叉树，输出树或二叉树的先序遍历和后序遍历序列。 二、运行环境 Visual C++ 三、需求分析 1、建立一棵用二叉链表方式存储的二叉树。 2、从键盘接受扩展先序序列，以二叉链表作为存储结构。 3、建立二叉树，并将遍历结果打印输出。采用递归和非递归两种 方法实现。 四、设计概要 //——————二叉树的二叉链表存储表示—————— typedef struct BiTBode{ TElemType data; Struct BiTNode *lchild, *rchild //左右孩子指针 }BiTNode, *BiTree; //—————基本操作的函数原型说明———————— Status CreateBiTree(BiTree &T); //按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。 //构造二叉树链表表示的二叉树T。 Status PreOrderTraverse(BiTree T, status(*visit)(TElemType e)); //采用二叉链表存储结构，visit是对结点操作的应用函数。 //先序遍历二叉树T，对每个结点调用函数visit一次且仅以次。 //一旦visit（）失败，则操作失败。 Status PostOrderTraverse(BiTree T, status(*visit)(TElemType e)); //采用二叉链表存储结构，visit是对结点操作的应用函数。 //后序遍历二叉树T，对每个结点调用函数visit一次且仅以次。 //一旦visit（）失败，则操作失败。 —————先序遍历二叉树基本操作的递归算法———— Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)){ //采用二叉链表存储结构，visit是对数据元素操作的应用函数，
问题一：二叉树遍历 1.问题描述 设输入该二叉树的前序序列为： ABC##DE#G##F##HI##J#K##（#代表空子树） 请编程完成下列任务： ⑴请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列； ⑵按层次遍历的方法来输出该二叉树按层次遍历的序列； ⑶求该二叉树的高度。 2.设计描述 （1）二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN 与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。采用递归方式就可以容易的实现二叉树的遍历，算法简单且直观。 （2）此外，二叉树的层次遍历即按照二叉树的层次结构进行遍历，按照从上到下，同一层从左到右的次序访问各节点。遍历算法可以利用队列来实现，开始时将整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的左右子树入队，当队列结束时算法结束。
（3）计算二叉树高度也是利用递归来实现：若一颗二叉树为空，则它的深度为0，否则深度等于左右子树的最大深度加一。 3．源程序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include
《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。 问题分析： 二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题，我觉得应该：
1、建立二叉树； 2、通过递归方法来遍历（先序、中序和后序）二叉树； 3、通过队列应用来实现对二叉树的层次遍历； 4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等； 5、运用广义表对二叉树进行广义表形式的打印。 算法规定： 输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。 输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。 程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。 测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E 预测结果：先序遍历ABCDEGF 中序遍历CBEGDFA 后序遍历CGEFDBA 层次遍历ABCDEFG 广义表打印A（B（C,D（E（,G）,F））） 叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2 查找5，成功，查找的元素为E 删除E后，以广义表形式打印A（B（C,D（,F））） 输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B 预测结果：先序遍历ABDEHCFG 中序遍历DBHEAGFC 后序遍历DHEBGFCA 层次遍历ABCDEFHG 广义表打印A（B(D,E(H)),C(F(,G))） 叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3 查找10，失败。
实验四二叉树的建立和遍历 学院专业班 学号姓名 一．实习目的 1.掌握二叉链表的存储结构； 2.掌握二叉链表的建立； 3.掌握二叉树的先序遍历、中序遍历、后序遍历的递归算法； 4. 掌握二叉树遍历算法的应用； 二．实习内容 1.按先序序列建立二叉树的二叉链表（算法6.4）（空树用#表示） 2.对生成的二叉树分别进行先序遍历、中序遍历、后序遍历，输出结果。 3．统计二叉树中结点个数； 4. 求二叉树的高度； 三．实验步骤 1.定义二叉链表的存储结构 #include "stdio.h" #include "stdlib.h" typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 }BiTNode,*BiTree; 2.编写函数CreateBiTree，按先序序列建立二叉树的二叉链表; 测试的字符序列为abdg###e##c#f##; 程序代码为： void CreateBiTree(BiTree &T) { // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，构造二叉链表表示的二叉树T。以#表示空树 TElemType ch; scanf("%c",&ch); if(ch=='#') // 空 T=NULL; else { T=(BiTree )malloc(sizeof(BiTNode)); // 生成根结点 if(!T)
exit(-1); T->data=ch; CreateBiTree(T->lchild);// 递归构造左子树 CreateBiTree(T->rchild);// 构造右子树 } } 2. 编写二叉树的先序遍历、中序遍历、后序遍历的递归算法 int preOrderTraverse(BiTree T) { // 初始条件：二叉树T存在，先序递归遍历T； if(T==NULL) return 1; if(T!=NULL) // T不空 {printf("%5c",T->data); // 访问根结点preOrderTraverse(T->lchild);// 先序遍历左子树 preOrderTraverse(T->rchild);// 先序遍历右子树 } } int inOrderTraverse(BiTree T) { // 初始条件：二叉树T存在，中序递归遍历T； if(T==NULL) return 1; if(T!=NULL) // T不空 { inOrderTraverse(T->lchild);// 中序遍历左子树 printf("%5c",T->data); // 访问根结点inOrderTraverse(T->rchild);// 中序遍历右子树 } } int postOrderTraverse(BiTree T) { // 初始条件：二叉树T存在， // 操作结果：后序递归遍历T； if(T==NULL) return 1; if(T!=NULL) // T不空 { postOrderTraverse(T->lchild);// 后序遍历左子树 postOrderTraverse(T->rchild);// 后序遍历右子树 printf("%5c",T->data); // 访问根结点
南昌大学实验报告 学生姓名：李木子学号：8000113146 专业班级：软工133 实验类型：□验证□综合□设计□创新实验日期：实验成绩： 一、实验项目名称 二叉树的遍历 二、实验目的 学会链式二叉树的结构体定义，创建与前序中序后序遍历 三、实验基本原理 四、主要仪器设备及耗材 电脑，VC6.0 五、实验步骤 /**************************************/ /* 链式二叉树的创建与遍历 */ /**************************************/ /**************************************/ /* 链式二叉树的结构体定义 */ /**************************************/ #include
/**************************************/ /* 链式二叉树函数声明 */ /**************************************/ BinTreeNode * CreateTree(void); void PreOrder( BinTreeNode * t ); void InOrder( BinTreeNode * t ); void PostOrder( BinTreeNode * t ); /**************************************/ /* 链式二叉树创建函数 */ /**************************************/ BinTreeNode * CreateTree(void) { char ch ; BinTreeNode * t ; ch=getchar(); if(ch=='#') t=NULL; else if( ch=='\n'); else { t=( BinTreeNode*)malloc(sizeof( BinTreeNode )); t->data =ch ; t->lchild=CreateTree(); t->rchild=CreateTree(); } return t ; } /**************************************/ /* 链式二叉树递归前序遍历函数 */ /**************************************/ void PreOrder( BinTreeNode * t ) { if(t) { printf("%c\t",t->data);
青岛理工大学数据结构课程实验报告
void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ if(T){ Visit(T->data);//首先访问根结点 PreOrderTraverse(T->lchild,Visit);//然后递归遍历左子树 PreOrderTraverse(T->rchild,Visit);//最后递归遍历右子树}} //中序遍历时先递归遍历左子树，然后访问根结点，最后递归遍历右子树；后序遍历时先递归遍历左子树，然后递归遍历右子树，最后 访问根结点 3、//先把栈及队列相关操作的头文件包括进来 1）根指针入栈， 2）向左走到左尽头（入栈操作） 3）出栈，访问结点 4）向右走一步，入栈，循环到第二步，直到栈空 //层次遍历时，若树不空，则首先访问根结点，然后，依照其双亲结 点访问的顺序，依次访问它们的左、右孩子结点; 4.首先建立二叉线索存储：包含数据域，左右孩子指针以及左右标志 typedef enum { Link=0,Thread=1 } PointerTag; typedef struct BiThrNode{ TElemType data; struct BiThrNode *lchild,*rchild;//左右孩子指针 PointerTag LTag,RTag;//左右标志 }BiThrNode, *BiThrTree; 建立前驱线索和后继线索，并用中序遍历进行中序线索化，然后最 后一个结点线索化 调 试 过 程 及 实 验 结 果 把测试数据放在f:\\file\\data.txt里，测试数据为：1 2 4 0 0 0 3 5 0 0 0 总访问结点是指访问该结点的数据域，弄清楚各个指针所指的类型
实验六二叉树的递归遍历及其应用 一、实验目的 1、深入了解二叉树递归的逻辑结构特征及其基本操作。 2、了解二叉树各种存储结构的特点及其适用范围，熟练掌握二叉树的二叉链表结构的定义及其递归遍历算法、按层次遍历算法的c语言实现，能深入了解递归算法的执行过程。 3、熟练掌握二叉树递归遍历算法的应用。 一、实验内容和要求 2、设计并验证如下算法：与“12.7.4参考源程序”类似，按中序序列输入建立两棵二叉树的二叉链表结构，求双分支结点数，判断两棵树是否相等。 3、设计并验证如下算法：按层次遍历二叉树，打印结点所在的层次，并求该二叉树的宽度。 二、实验过程及结果 （第一题） 一、需求分析 1、从键盘输入二叉树的序列，但由于建树是从根结点往下建立的，故只能输入先 序序列，则按照中序建树完成二叉树的创建。 2、从键盘输入一段正确的序列后，按回车键自动生成二叉树，若该序列不能生成 一颗二叉树，则程序无法继续进行，只能退出。 3、程序能实现的功能包括： ①初始化二叉树；②创建一棵完整二叉树；③先中后序遍历二叉树； ④求二叉树双分支结点数；⑤比较两棵二叉树是否相等； 二、概要设计 1、二叉树的抽象数据类型定义： ADT BinaryTree{ 数据对象D：D是具有相同特征的数据元素的集合。 数据关系R： 若D=空，则R=空，称BinaryTree为空二叉树； 若D！=空，则R={H}，H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D-{root}!=Φ，则存在D-{root}={D1,Dr}，且D1∩Dr=Φ； （3）若D1！=Φ，则D1中存在唯一元素x1，
太原师范学院 实验报告Experimentation Report of Taiyuan Normal University 系部计算机系年级XX 课程数据结构 姓名XXX 同组者日期 项目二叉树的遍历 一、实验目的： ①设计程序分别实现实现对二叉树的先序、中序、后序遍历。 ②计算出二叉树的节点个数、叶子节点个数、二叉树的深度等。 二、实验要求： ①掌握先序、中序、后序遍历二叉树的过程。 ②掌握二叉树的先序、中序、后序遍历算法。 三、实验平台 硬件：笔记本电脑一台； 软件：Windows 10，visual_studio_2010； 四、运行结果（运行界面图及说明） 测试数据：ABC##DE#G##F### -*a##b##c##
五、实验体会 1.上机多加练习才能真正学会相关内容； 2.应对二叉树的性质熟练掌握； 3．实验错误太多，应加强基础知识的学习。 六、附完整代码 #include
数据结构 实 验 报 告
1. 实验目的和内容： 掌握二叉树基本操作的实现方法2. 程序分析 2.1存储结构 链式存储 2．程序流程
2.3关键算法分析 算法一：Create(BiNode
算法三：PreOrder(BiNode
实验报告 | | 实验名称二叉树的遍历 课程名称算法与数据结构试验 | | 专业班级：信息管理信息系统 学号： 实验日期： 姓名：慕鑫鑫 一、实验名称：二叉树的遍历 二、实验目的 综合应用所学的知识分析问题、解决问题，学会用建立二叉树并对其进行遍历，提高实际编程能力及程序调试能力。 三、实验要求 建立一个二叉树并对其进行遍历（先序，中序，后序） 四、实验内容 1、问题描述：建立一个二叉树，并分别用前序、中序、后序遍历该二叉树。 2、说明： 输入数据： 1,2,3,0,0,4,5,0,0,6,7,0,0,0,8,9,0,0,10,11,12,0,0,13,0,0,14,0,0其中 “0”表示空子树。 输出数据： 先序：1,2,3,4,5,6,7,8,9,10,11,12,13,14。 中序：3,2,5,4,7,6,1,9,8,12,11,13,10,14。 后序：3,5,7,6,4,2,9,12,13,11,14,10,8,1。 五、实验仪器与设备 计算机，ＪＤＫ，记事本 六、实验原理 建立一个二叉树，利用递归的方法实现对该二叉树的前序，中序，后序的遍历，并输出遍历结果。 七、实验程序及结果 #include
using namespace std; typedef struct btnode { int data; btnode *Lchild,*Rchild; }*Btnode; void Creat(Btnode & t) { int ch; cin>>ch; if(ch==0) t=NULL; else { btnode *p=new btnode; p->data=ch; t=p; Creat(t->Lchild); Creat(t->Rchild); } } void Preorder(Btnode & p) { if(p!=NULL) { cout<