《数据结构与数据库》
实验报告
实验题目
二叉树的基本操作及运算
一、需要分析
问题描述：
实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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，失败。
删除B 后，以广义表形式打印A （，C （F （，G ）））
二、 概要设计
程序中将涉及下列两个抽象数据类型：一个是二叉树，一个是队列。
1、设定“二叉树”的抽象数据类型定义：
ADT BiTree{
数据对象D ：D 是具有相同特性的数据元素的集合。
数据关系R ：
若 Φ=D ，则Φ=R ，称BiTree 为空二叉树；
若 Φ≠D ，则{}H R =，H 是如下二元关系：
（1） 在D 中存在唯一的称为根的数据元素root ，它在关系H 下无前驱；
（2） 若{} ,Φ≠-root D 则存在{}{},,r l D D root D =-且Φ=?r l D D ;
（3） 若,Φ≠l D 则l D 中存在唯一的元素l x ,,,H x root l >∈<且存在l D 上的关系
;H H l ?若,Φ≠r D 则r D 中存在唯一的元素r x ,,,H x root r >∈<且存在r D 上的
关系{}
r l r l r H H x root x root H H H ,,,,,;><><=?；
（4） {}()l l H D ,是一棵符合本定义的二叉树，称为根的左子树，{}()r r H D ,是一棵符合本
定义的二叉树，称为根的有字树
基本操作：
CreateBiTree&T)
操作结果：按照T 的定义构造一个二叉树。
BiTreeDepth(& T)
初始条件：二叉树T 已存在。
操作结果：返回T 的深度。
BiTreeWidth(&T)
初始条件：二叉树T 已存在。
操作结果：返回T 的宽度。
PreOderTraverse&T)
初始条件：二叉树T 已存在。
操作结果：先序遍历打印T ，
InOderTraverse(&T)
初始条件：二叉树T 已存在。
操作结果：中序遍历打印T 。
PostOderTraverse(&T)
初始条件：二叉树T 已存在。
操作结果：后序遍历打印T 。
LevelTraverse(&T)
初始条件：二叉树T 已存在。
操作结果：层次遍历T 。
DeleteXTree(&T,TElemType x)
初始条件：二叉树已存在。
操作结果：删除元素为x 的结点以及其左子树和右子树。
CopyTree(&T)
初始条件：二叉树T 已存在。
操作结果：以T 为模板，复制另一个二叉树。
｝ADT BiTree
2、设定队列的抽象数据类型定义：
ADT Queue{
数据对象：D={i a },+∈∈N i BiTree a i 数据关系：R1={<1,-i i a a >|1-i a ,D a i ∈,i=2,…，n}
约定1a 端为队列头，n a 端为队列尾。
基本操作：
InitQueue(&Q)
操作结果：构造一个空队列Q 。
EnQueue(&Q,&e)
初始条件：队列Q 已存在。
操作结果：插入元素e 为Q 的新的队尾元素。
DeQueue(&Q)
初始条件：队列Q 已存在。
操作结果：删除Q 的对头元素，并返回其值。
QueueEmpty(&Q)
初始条件：队列Q 已存在。
操作结果：若Q 为空队列，则返回1，否则0。
} ADT Queue
3、本程序包含四个模块
1）主程序模块
void main( )
{
初始化；
先序输入二叉树各结点元素；
各种遍历二叉树；
对二叉树进行常见运算；
复制二叉树；
在复制的二叉树上进行二叉树的常见操作；
｝
2）二叉树模块——实现二叉树的抽象数据类型和基本操作
2）队列模块——实现队列的抽象数据类型及今本操作
3）广义表打印模块——以广义表形式打印二叉树
4）二叉树运算模块——对二叉树的叶子、非空子孙结点数目、度为2或1的结点数
三、 详细设计
1、主程序中需要的全程量
#define M 10 // 统计二叉树宽度时需用数组对每层宽度进行存储，这M表示数组的长度
2、队列的建立与基本操作
typedef struc t QNode{
BiTree data; //队列中存储的元素类型
struct QNode *next; //指向二叉树结点的指针
}QNode,*Queueptr;
typedef struct{
Queueptr front; //队列的队头指针
Queueptr rear; //队列的队尾指针
}LinkQueue;
算法描述：
为了对二叉树进行层次遍历，需要“先访问的结点，其孩子结点必然也先访问”，故需运用到队列。而考虑到层次遍历对队列操作的需要，只需进行队列的初始化，入队和出队以及检查队列是否为空。
伪码算法：
void InitQueue(LinkQueue *Q)
{//初始化队列申请一个结点
Q->front=Q->rear=(Queueptr)malloc(sizeof(QNode));
if(!Q->front)
exit(1);//存储分配失败处理
Q->front->next=NULL;//构成带头结点里的空链队列
}
void EnQueue(LinkQueue *Q,BiTree e)
{//插入元素为e为Q的队尾元素
Queueptr q;
q=(Queueptr)malloc(sizeof(QNode));
if(!q)
exit(1);
q->data=e;
q->next=NULL;
Q->rear->next=q; //元素e的结点入列
Q->rear=q;
}
BiTree DeQueue(LinkQueue *Q)
{//从队列中删除队头元素，并直接返回给调用的主函数
Queueptr p;
BiTree q;
if(Q->front==Q->rear)
{//队列为空
printf("ERROR!\n");
exit(1);
}
p=Q->front->next;
q=p->data;
Q->front->next=p->next; //删除该结点
if(Q->rear==p)
Q->rear=Q->front;
free(p);
return q;//返回队头元素
}
int QueueEmpty(LinkQueue *Q)
{//检查队列是否为空，若为空则返回真值，否则返回0
if(Q->front==Q->rear)
return 1;
else
return 0;
}
3、二叉树的建立与基本操作
typedef struct BiTNode{
TElemType data; //二叉树结点存储的元素类型
struct BiTNode *lchild,*rchild; //二叉树左右孩子指针
}BiTNode,*BiTree;
算法分析：
二叉树的基本操作是本程序的核心，考虑到二叉树的定义就是采用递归定义，所以很容易想到对二叉树的操作可通过递归调用来实现。
1）二叉树的遍历
算法描述：
二叉树中常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就需要遍历二叉树。即要求按某条路径寻访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。
回顾二叉树的递归定义可知，二叉树是由3个基本单元组成：根节点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整棵二叉树。如果以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。
若限定先右后左，则只有前三种情况，分别称之为先（根）序遍历。中（根）序遍历和后（根）序遍历。基于二叉树的递归定义，可得下述遍历二叉树的递归定义算法。
先序遍历二叉树的操作定义：
若二叉树为空，则空操作；否则
（1）访问根结点；
（2）先序遍历左子树；
（3）先序遍历右子树。
伪码算法：
void PreOderTraverse(BiTree T)
{//采用二叉链表存储结构
if(T)
{
putchar(T->data);//最简单的访问结点法，输出结点元素，这里先访问根结点
PreOderTraverse(T->lchild);
PreOderTraverse(T->rchild);
}
}
中序遍历二叉树的操作定义：
若二叉树为空，则空操作；否则
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树。
伪码算法：
void InOderTraverse(BiTree T)
{//采用二叉链表存储结构
if(T)
{
InOderTraverse(T->lchild);//先遍历左子树
putchar(T->data);// 最简单的访问结点法，输出结点元素，这里第二访问根结点
InOderTraverse(T->rchild);
}
}
后序遍历二叉树的操作定义：
若二叉树为空，则空操作；否则
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根结点。
伪码算法：
void PostOderTraverse(BiTree T)
{//采用二叉链表存储结构
if(T)
{
PostOderTraverse(T->lchild);//先遍历左子树
PostOderTraverse(T->rchild);//再遍历右子树
putchar(T->data);//最后访问根结点
}
}
2）二叉树的建立
算法描述：
对二叉树“遍历”基本操作已经建立的基础上，可以在便利过程中对结点进行各种操作，如：在遍历过程中生成结点，建立二叉树存储结构。
采用先序遍历建立二叉树链表：
（1）按先序序列输入二叉树中结点的元素，以空格表示空，直到输入回车为止；
（2）若元素值为空，则赋值NULL；否则生成一个新的结点，将元素值赋值给该跟结点的数值域；
（3）建立该跟结点的左子树；
（4）建立该根结点的右子树。
伪码算法;
BiTree CreateBiTree(BiTree T)
{//构造二叉树T，按先序序列输入二叉树中结点的值（一个字符），空格表示空树
char ch;
if((ch=getchar())==' ')
T=NULL;
else
if(ch!='\n')
{
if(!(T=(BiTree)malloc(sizeof(BiTNode))))
exit(1);
T->data=ch; //生成根结点
T->lchild=CreateBiTree(T->lchild);//构造左子树
T->rchild=CreateBiTree(T->rchild);//构造右子树
}
return T;//返回所构造二叉树（子）树的地址
}
3）二叉树的层次遍历
算法分析：
有时需要一层层访问二叉树，比如判断二叉树是否为完全二叉树、找出指定层中含有的叶子/度为2/度为1的结点等，这就需要另一种遍历方法——层次遍历。
先访问的结点，其孩子结点必然也先访问，引入队列存储已被访问的，但其左右孩子尚未访问的结点的指针。
算法描述:
（1）若结点不为空，则访问该结点，并将其入列；
（2）接着从队列中取已被访问的，但其左右孩子尚未被访问的；
（3）访问该结点的左孩子，将其入列；
（4）访问该结点的右孩子，将其入列。
伪码算法：
int visit(TElemType e)
{//简单的结点访问函数
if(e)
{
putchar(e);//打印该结点元素
return 1;
}
else
return 0;
}
void LevelTraverse(BiTree T)
{
LinkQueue *Q=(LinkQueue *)malloc(sizeof(LinkQueue));
BiTree p=(BiTree)malloc(sizeof(BiTNode));
InitQueue(Q);//初始化队列，队列的元素为二叉树的结点指针
if(T!=NULL)
{
if(!visit(T->data))//访问该结点
exit(1);
EnQueue(Q,T);//将已被访问的，但左右孩子没被访问的结点入列
while(!QueueEmpty(Q))
{//队列不为空，则尚有未被访问其孩子的结点
p=DeQueue(Q);//将该结点出列，返回其地址
if(p->lchild!=NULL)
{
if(!visit(p->lchild->data))//访问左孩子
exit(1);
EnQueue(Q,p->lchild);//将其入列
}
if(p->rchild!=NULL)
{
if(!visit(p->rchild->data))//访问右孩子
exit(1);
EnQueue(Q,p->rchild);//将其入列
}
}
}
}
4）求二叉树的深度
算法描述：
（1）若结点不为空，则求其左子树的深度，并返回其值h1；
（2）求其右子树的深度，也返回其值h2；
（3）选择左右子树深度的最大值，将其加一（该结点本身深度）即为该结点子树的深度。
伪码算法：
int BiTreeDepth(BiTree T)
{//后序遍历求树T所指二叉树的深度
int hl=0,hr=0;
if(!T)
return 0;
else
{
hl=BiTreeDepth(T->lchild);//求左子树的深度
hr=BiTreeDepth(T->rchild);//求右子树的深度
if(hl>=hr)return hl+1;
else return hr+1;//子树深度的最大值再加上本身所在结点的深度记为子树的深度}
}
5）求二叉树的宽度
算法描述：
（1）定义一个数组，来存放每层的结点数，max来存放到这层为止时的最大结点数；
（2）计算每一层的结点数将其赋值给对应的数组元素；
（3）每层计算完后，用max与本层结点数比较，若max小，则将本层结点数赋值给max;
（4）最后返回max。
伪码算法：
in t BiTreeWidth(BiTree T,int i)
{
int static n[M]={0};//存放各层结点数，M为最先预料的最大树的最大深度
int static max=0;//最大宽度
if(T!=NULL)
{
if(i==1)//若是访问根结点
{
n[i]++;//第一层加1
i++;//到第二层
if(T->lchild)
n[i]++;//若有左孩子则该层加1
if(T->rchild)
n[i]++;//若有右孩子则该层加1
}
else
{//访问子树的结点
i++;//向下一层
if(T->lchild)
n[i]++;
if(T->rchild)
n[i]++;
}
if(max max=n[i];//取出目前为止，各层结点数的最大值 BiTreeWidth(T->lchild,i);//遍历左子树 BiTreeWidth(T->rchild,i--);//网上退一层后遍历右子树 } return max; } 6）删除二叉树的某个结点 算法描述： （1）先序遍历找到该结点； （2）若此结点为空，不必释放；若不为空，则先释放其左右子树的所有结点的空间，再赋为空； （3）再释放根结点的空间，并将这个结点的父节点指向该结点的指针域赋为空。 伪码算法： BiTree DeleteBiTree(BiTree t) {//释放该结点空间的函数 if(t!=NULL) { t->lchild=DeleteBiTree(t->lchild);//释放其左子树的空间 t->rchild=DeleteBiTree(t->rchild);//释放右子树的空间 free(t);//释放根结点的空间 t=NULL;//将其值赋为空 } return t; } BiTree DeleteXTree(BiTree t,TElemType x) {//先序查找到需删结点位置 if(t!=NULL) { if(t->data==x){//判断是否为指定结点 DeleteBiTree(t);//释放树的空间 t=NULL; } else { t->lchild=DeleteXTree(t->lchild,x); t->rchild=DeleteXTree(t->rchild,x); } } return t; } 7）复制二叉树 算法描述: （1）先复制其左子树； （2）再复制其右子树； （3）生成一个新结点，将根复制。 伪码算法： BiTree GetTreeNode(TElemType item,BiTree lptr,BiTree rptr) {//生成一个其元素值为item，左指针为lpttr，右指针为rptr的结点BiTree t; t=(BiTree)malloc(sizeof(BiTNode)); t->data=item; t->lchild=lptr; t->rchild=rptr; return t; } BiTree CopyTree(BiTree T) {//已知二叉树的根指针T，返回它的复制品的根指针 BiTree newlptr,newrptr,newnode; if(!T) return NULL;//复制一颗空树 if(T->lchild) newlptr=CopyTree(T->lchild);//复制（遍历）其左子树 else newlptr=NULL; if(T->rchild) newrptr=CopyTree(T->rchild); //复制（遍历）其右子树 else newrptr=NULL; newnode=GetTreeNode(T->data,newlptr,newrptr);//生成根结点 return newnode; } 4、广义表形式打印二叉树 算法分析： 为了让打印的二叉树更形象，更清楚的反映二叉树各结点的关系，采用广义表形式打印则可以满足要求。 算法描述： （1）打印根结点，若其还有孩子，则输出“（”； （2）若有左孩子，则打印左子树； （3）若还有右子树，则先打印“，”区分左右孩子，再打印右子树，并输出“）”表示输除完毕。 伪码算法： void print(BiTree T) {//广义表形式打印二叉树 if(T!=NULL) { printf("%c",T->data); if(T->lchild!=NULL || T->rchild!=NULL)//该结点还有孩子 { printf("("); print(T->lchild);//广义表打印左子树 if(T->rchild!=NULL) printf(","); print(T->rchild);//广义表打印右子树 printf(")"); } } } 5、二叉树的常见运算 1）求二叉树的叶子数 算法描述： （1）若该结点无孩子，则表示为叶子，计数器加一； （2）若该结点右孩子，求其左子树的的叶子； （3）再求其右子树的叶子。 伪码算法： int LeafNum(BiTree T) {//统计叶子数 int static n=0;//定义一个静态局部变量作为计数器 if(T!=NULL) { if(T->lchild==NULL && T->rchild==NULL)//结点无孩子 n++;//计数器加一 LeafNum(T->lchild);//求左子树的叶子数 LeafNum(T->rchild); //求右子树的叶子数 } return n; } 2）求不同的度的结点数 算法描述： （1）定义一个静态局部数组变量来统计不同度的结点数 （2）若该结点既有左孩子又有右孩子则度为2的计数器加一，若该节点只有左孩子或只有右孩子，则度为1的结点数的计数器加一、 （3）在对其左右子树进行相同操作。 伪码算法： int *JudgeCBT(BiTree T) {//统计不同度的结点数 int static d[3]={0};//d[1]作为度为1的计数器，d[2]作为度为2的计数器 if(T!=NULL) { if(T->lchild!=NULL && T->rchild!=NULL)//左右孩子都有 d[2]++; else {//只有一个孩子 if(T->lchild!=NULL && T->rchild==NULL) d[1]++; else if(T->lchild==NULL && T->rchild!=NULL) d[1]++; } JudgeCBT(T->lchild);//统计左子树 JudgeCBT(T->rchild);//统计右孩子 } return d;//返回数组的指针 } 3）求非空子孙结点数 算法描述： （1）定义一个静态局部变量，作为计数器； （2）若该节点的左孩子非空则加一，右孩子非空亦加一； （3）统计左子树；统计右子树。 伪码算法： int BiTreeDescendant(BiTree T) {//统计非空子孙结点数 int static n=0;//初始化计数器 if(T!=NULL) { if(T->lchild) n++; if(T->rchild) n++; BiTreeDescendant(T->lchild);//统计左子树 BiTreeDescendant(T->rchild);//统计右子树 } return n; } 4）查找二叉树的某个位置的结点（先序序列） 算法描述： （1）定义一个静态局部变量，用作记录已查结点的个数； （2）从根节点开始，如果相查找的位置理由元素，则打印该元素，如果想查的位置超过二叉树本身的元素数则返回出错。 伪码算法： int PreOderKNode(BiTree T,int k,TElemType *e) {//T为二叉树，k为带查找的结点位序；e为指针带值返回查找到的数。 int static count=0;//作为计数器，记录已查找的结点数 if(T==NULL) return 0; count++;//访问结点，对已访问的结点进行计数 if(count==k)//判断该结点是否是待查找的结点 { e=&T->data; printf("存在你想查找位置的元素，先序序列中第%d个元素是%c\n",k,*e); return 1;//查找成功 } else if(count>k)//计数器count已经超出k，则直接返回0，查找不成功 return 0; else {//在左或右子树中查找 if(PreOderKNode(T->lchild,k,e)==0) return PreOderKNode(T->rchild,k,e); return 1; } } 6、主程序的伪码算法： void main() { BiTree T=NULL,T_1=NULL,T_2=NULL; int i=1,*n=0,*kd,k=0; char x=0; printf("请按先序序列输入各结点\n"); T=CreateBiTree(T);//先序序列构造一棵二叉树 //遍历二叉树 printf("先序遍历二叉树：\n"); PreOderTraverse(T);putchar('\n'); printf("中序遍历二叉树：\n"); InOderTraverse(T);putchar('\n'); printf("后序遍历二叉树：\n"); PostOderTraverse(T);putchar('\n'); printf("层次遍历二叉树：\n"); LevelTraverse(T);putchar('\n'); printf("以广义表形式打印二叉树:\n");//广义表形式打印二叉树 print(T);putchar('\n'); //二叉树的基本操作和运算 printf("二叉树的叶子数LeafNumber为:%d\n",LeafNum(T));//统计叶子数 printf("二叉树的深度Depth为:%d\n",BiTreeDepth(T));//计算深度 printf("二叉树的宽度Width为:%d\n",BiTreeWidth(T,i));//计算宽度 //统计非空子孙结点数 printf("二叉树非空子孙结点DescendantNumber数为:%d\n",BiTreeDescendant(T)); kd=JudgeCBT(T);//统计不同度的结点数 printf("二叉树度为1的结点数为:%d，度为2的结点数为:%d\n",kd[1],kd[2]); //二叉树的基本操作，删除和查找 printf("下面进行二叉数的查找和删除操作\n"); T_2=CopyTree(T);putchar('\n');//运用二叉树的复制操作 printf("复制后的T_2,以先序序列输出:\n"); PreOderTraverse(T_2);putchar('\n'); printf("请输入你想查找在在先序序列的第几个位置的元素\n"); scanf("%d",&k); if(!PreOderKNode(T_2,k,e)) printf("不存在你想查找的位置\n"); T_1=CopyTree(T);putchar('\n'); printf("复制后的T_1,以先序序列输出:\n"); PreOderTraverse(T_1);putchar('\n'); getchar(); printf("请输入你想删除元素值为多少的结点\n"); x=getchar();getchar(); DeleteXTree(T_1,x); printf("先序遍历二叉树：\n"); PreOderTraverse(T_1);putchar('\n'); printf("以广义表形式打印二叉树:\n"); print(T_1);putchar('\n'); } 四、调试分析 1、在调试过程中，在进行二叉树的基本操作时就出现错误了，为了方便检查错误，故逐渐将主函数的谋 部分调用的函数先屏蔽后，再运行调试，才发现了错误。 2、在调试过程中，为了方便对调用函数的检查，每当计数器变化时，就输出该值，就可以看出是哪里的 问题。 3、在调试过程中，在运行删除时，程序出现错误，当输入欲删除结点后，程序并没有删除该结点。后来 经过调试才发现，因为在输入删除元素时，是由getchar（）接收，而在查找时遗留下的回车直接被getchar （）接收，当作NULL去运行了。 4、在调试过程中，更改了4的错误，在删除一个结点后，虽然能删除元素了，但再次打印该树后，就发 现每当打印到删除结点位置时，程序就报错。后来经过老师和同学的帮助才发现，虽然将待删结点的空间释放，但并没有把指向该结点的父结点的指针域赋空，后来更改后，程序完美运行了。 5、从程序实验题的编制过程中容易看出，线性表的广泛应用，特别是顺序存储结构的队列和链式存储结 构的二叉树的应用。 五、用户使用说明 1、本程序的运行环境为Windows7旗舰版操作系统，执行文件为：二叉树的基本操作及运算.exe； 2、进入程序后即显示提示信息：“请按先序序列输入各结点”以等待用户输入欲构造的二叉树的各元 素值；若用户输入的的是一个不符合先序序列的字符串，则程序报错； 3、在用户正确输入二叉树的元素后，程序会自动对其先序、中序、后序和层次遍历，并对二叉树进 行求叶子数、深度、宽度、非空子孙结点数、度为1的结点数和度为2的结点数。并在自动复制一棵树后，出现“请输入你想查找在先序序列的第几个位置的元素”，等待用户输入欲查找的元素位置； 4、输入查找的位置后，如果存在该位置的元素，则程序会显示“存在你想查找位置的元素，先序序 列中第x个元素是x”；然后会弹出“请输入你想删除元素值为多少的结点”，等待用户输入某个元素值； 5、输入某个元素值后，若删除成功则会先序遍历和广义表形式打印删除后的二叉树。 6、本程序要求在输入二叉树元素是一定要正确，空格不能少，也不能多，不然程序会报错。 六、测试结果 1、正确输入：ABC□□DE□G□□F□□□,查找5,删除E 运行界面： 2、正确输入：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B 运行界面： 以上结果与自己在进行程序概要分析时的预测结果一致 七、心得体会 这次实验设计让我更加了解并更加灵活运用到大一学到的C程序设计和这个学期学到的数据结构。实验任务要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。 这次实验设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。在进行编程时一定要把每个问题都分析清楚，比如自己在编写删除删除BiTree DeleteBiTree(BiTree t)，BiTree DeleteXTree(BiTree t,TElemType x)时，只是把一个指针忘记赋为空，则导致程序报错，希望以后在运用递归调用时，一定要弄清各种值的传递关系。 还有，在编写函数时，编写时能把每一步的结果都打印出来，这能很方便的调试程序。 在编写实验报告时自己无意发现，其实统计非空子孙结点数、不同度的结点数甚至叶子数的函数思想与算法十分相似，都可以编写在一个函数里，这也说明了实验报告的重要性，我们应该在实验报告里多反思、总结，尽量完善自己的程序设计。 程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时体会到C语言具有的语句简洁，使用灵活，执行效率高等特点。发现上机的重要作用，特别算术表达式有了深刻的理解。 最后，感谢老师在这次课程设计的悉心指导，祝老师身体健康，工作顺利。 参考文献： 1.《数据结构(C语言版)》严蔚敏清华大学出版社 2.《C程序设计》谭浩强清华大学出版社 3.《数据结构题集（C语言版）》严蔚敏吴伟民米宁清华大学出版社 4.《C程序设计学习指导与练习》贾伯琪中国科学技术大学出版社 八、附录 “二叉树的基本操作及运算”源程序代码： #include #include #include typedef char TElemType; char *e; #define M 10 typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; typedef struct QNode{ BiTree data; struct QNode *next; }QNode,*Queueptr; typedef struct{ Queueptr front; Queueptr rear; }LinkQueue; void InitQueue(LinkQueue *Q) { Q->front=Q->rear=(Queueptr)malloc(sizeof(QNode)); if(!Q->front) exit(1); Q->front->next=NULL; } void EnQueue(LinkQueue *Q,BiTree e) { Queueptr q; q=(Queueptr)malloc(sizeof(QNode)); if(!q) exit(1); q->data=e; q->next=NULL; Q->rear->next=q; Q->rear=q; } BiTree DeQueue(LinkQueue *Q) { Queueptr p; BiTree q; if(Q->front==Q->rear) { printf("ERROR!\n"); exit(1); } p=Q->front->next; q=p->data; Q->front->next=p->next; if(Q->rear==p) Q->rear=Q->front; free(p); return q; } int QueueEmpty(LinkQueue *Q) { if(Q->front==Q->rear) return 1; else return 0; } BiTree CreateBiTree(BiTree T) 实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 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．掌握对二叉树每一种操作的具体实现。 3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 4.会用二叉树解决简单的实际问题。 二、实验内容 设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树， 2按（A:先序 B:中序 C:后序）遍历输出二叉树的所有结点 以上比做，以下选做 3求二叉树中所有结点数 4求二叉树的深度 三、实验步骤 ㈠、数据结构与核心算法的设计描述 /* 定义DataType为char类型 */ typedef char DataType; /* 二叉树的结点类型 */ typedef struct BitNode { DataType data; struct BitNode *lchild,*rchild; }*BitTree; 相关函数声明： 1、/* 初始化二叉树，即把树根指针置空 */ void BinTreeInit(BitTree *BT) { BT=(BitTree)malloc(sizeof(BitNode)); BT->data=NULL; cout<<"二叉树初始化成功!"< //二叉树的基本操作 #include 树和二叉树 一、实验目的 1.掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。 2.掌握用指针类型描述、访问和处理二叉树的运算。 二、实验要求 1.认真阅读和掌握本实验的程序。 2.上机运行本程序。 3.保存和打印出程序的运行结果，并结合程序进行分析。 4.按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运 行结果。 三、实验内容 1.输入字符序列，建立二叉链表。 2.按先序、中序和后序遍历二叉树（递归算法）。 3.按某种形式输出整棵二叉树。 4.求二叉树的高度。 5.求二叉树的叶节点个数。 6.交换二叉树的左右子树。 7.借助队列实现二叉树的层次遍历。 8.在主函数中设计一个简单的菜单，分别调试上述算法。 为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。一种方法是利用二叉树的性质5来建立二叉树，输入数据时要将节点的序号（按满二叉树编号）和数据同时给出：（序号，数据元素0）。另一种方法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#”来充当，也要输入。若当前数据不为“#”，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。 四、解题思路 1、先序遍历：○1访问根结点，○2先序遍历左子树，○3先序遍历右子树 2、中序遍历：○1中序遍历左子树，○2访问根结点，○3中序遍历右子树 3、后序遍历：○1后序遍历左子树，○2后序遍历右子树，○3访问根结点 4、层次遍历算法：采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进后出，所以能够达到按层次遍历二叉树的目的。 五、程序清单 #include 实验三二叉树的基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、实验前的准备工作 1、掌握树的逻辑结构。 2、掌握二叉树的逻辑结构和存储结构。 3、掌握二叉树的各种遍历算法的实现。 一实验分析 本次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历。二叉树的遍历有多种方法，本次试验我采用递归法，递归法比较简单。 二概要设计 功能实现 1.int CreatBiTree(BiTree &T) 用递归的方法先序建立二叉树, 并用链表储存该二叉树 2.int PreTravel(BiTree &T) 前序遍历 3. int MidTravel(BiTree &T) 中序遍历 4.int PostTravel(BiTree &T) 后序遍历 5.int Depth(BiTree &T) //计算树的深度 6.int howmuch(BiTree T,int h) 采用树节点指针数组，用于存放遍历到的元素地址，如果有左孩子，存入地址，j加一，否则没操作，通过访问数组输出层次遍历的结果。k计算叶子数，j为总节点。 7. int exchang(BiTree &T) 交换左右子树，利用递归，当有左右孩子时才交换 三详细设计 #include 二叉树的建立和遍历的实验报告 篇一：二叉树的建立及遍历实验报告 实验三：二叉树的建立及遍历 【实验目的】 （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)))) 数据结构二叉树基本操作 (1). // 对二叉树的基本操作的类模板封装 //------------------------------------------------------------------------------------------------------------------------ #include 重庆交通大学综合性设计性实验报告 姓名姚远学号 631106060113 班级：计信息一班 实验项目名称：二叉树 实验项目性质：设计性实验 实验所属课程：数据结构 实验室(中心)： 407机房 指导教师：鲁云平 实验完成时间： 2013 年 5 月 10 日 一、实验目的 1. 建立二叉树 2. 计算结点所在的层次 3.统计结点数量和叶结点数量 4.计算二叉树的高度 5.计算结点的度 6.找结点的双亲和子女 7.二叉树的遍历 8.二叉树的输出等等 二、实验内容及要求 1.二叉树的结点结构,二叉树的存储结构由学生自由选择和设定 2.实验完成后上交打印的实验报告,报告内容与前面所给定的实验模板相同 3.将实验报告电子版和源代码在网络教学平台提交 三、实验设备及软件 VISUAL C++软件 四、设计方案 ㈠题目（老师给定或学生自定） 二叉树的应用 ㈡设计的主要思路 在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，出度为2的结点数为n2，则n0 =n2 + 1。 ㈢主要功能 实现二叉树的各项操作。 五、主要代码 #include 郑州轻工业学院数据结构实验报告 题目 学生姓名 学号 专业班级 完成时间 2016年月日 目录 一、系统功能介绍 (2) 二、需求分析 (2) 三、概要设计 (2) 四、详细设计 (5) 五、调试分析 (8) 六、使用说明 (8) 七、测试结果 (9) 八、心得体会 (10) 九、附录（程序代码） (11) 一、系统功能介绍 该系统主要功能是实现二叉树的定义和基本操作，包括定义二叉树的结构类型以及各个操作的具体函数的定义和主函数的定义。 各操作主要包括：初始化二叉树、按先序次序建立二叉树、检查二叉树是否为空、前序、中序、后序遍历树的方式、求树的深度、求树的结点数目、清空二叉树等九个对树的操作。 二、需求分析 本系统通过函数调用实现二叉树初始化，建立二叉树，检查树空与否，用前序、中序、后序遍历二叉树，求树的深度，求树的结点数目，清空二叉树等功能。 1）输出的形式和输出值的范围：在选择操作中，都以整型（数字）选择操作，插入和输出的数值都是char类型的字符； 2）输出的形式：在每次操作后，都会提示操作是否成功或者操作的结果； 3）程序达到的功能：完成初始化、检查是否为空、请空、遍历、求树的深度、求树的结点数目等功能； 4)测试数据设计： A,按先序次序建立二叉树。依次输入a,b,c,d,e,f,g.建立二叉树。 B,分别按先序，中序和后序遍历输出二叉树中的结点元素。 C,求树的高度和结点数。 三、概要分析 为了实现上述功能，定义二叉树的抽象数据类型。 ADT BinTree{ 数据对象D:D是具有相同特性的数据元素的集合。 数据关系R: 若D=￠，称BinTree为空二叉树 若D≠￠,则R={H},H是如下的二元关系； （1）在D中存在唯一的称为根的数据元素root,它在关系H下无前驱； （2）若D-{root}≠￠，则存在D-{root}={D1,Dr},且D1∩Dr=￠； （3）若D≠￠，则中存在唯一的元素x1, 实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、测试数据 1、输入数据：*（+）3 正确结果： 2、输入数据：(1+2)*3+(5+6*7); 正确输出：56 七、表达式求值 由于表达式求值算法较为复杂，所以单独列出来加以分析： 1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。 例如有如下的中缀表达式： a+b-c 转换成后缀表达式为： ab+c- 然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。 2、求值过程 一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来，并以字符串的 形式保存。 二、将分解的中缀表达式转换为后缀表达式的形式，即调整各项字符串的顺序，并将括 号处理掉。 三、计算后缀表达式的值。 3、中缀表达式分解 DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示： 《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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、isLeaf函数：若该结点的左子树和右子树都为空，则为叶子结点。 2、isEmpty函数：根结点为空则为空树。 3、Parent函数：首先判断给定结点是否有双亲，根结点和空结点一定无双亲，初始化一个临时变量，用于跟进查找双亲结点，查找到后其保存的便是双亲结点。先递归在左子树中查找，如果找到，便结束递归且返回双亲结点指针；如果没有找到，再递归在右子树中查找。如果都没有找到，说明给定结点的双亲结点不在该二叉树中。 4、LeftSibling（RightSibling）函数：首先找到当前结点的双亲，然后判断双亲结点左右子树是否为空，其中必然有一个不为空，返回另一个子树指针即可。 5、DeleteBinaryTree函数：首先判断是否为空树，若为空，则返回，然后递归删除左子树，递归删除右子树，最后删除根结点。 6、PreOrder函数：首先判断是否为空树，若为空，则返回，然后访问根结点，递归遍历左子树，递归遍历右子树，结束。 7、PreOrderWithoutRecusion函数：使用栈来模拟递归过程，首先申请栈，用于保存结点指针序列，申请指针pointer保存当前根指针，然后判断栈是否为空，若栈为空且pointer为空，跳出函数，否则若pointer不为空，访问pointer所指结点，pointer入栈，pointer指向其左子树；若pointer为空，弹出栈顶元素赋给pointer，pointer指向其右子树，结束。 8、CreateTree函数：采用先序遍历序列构造二叉树，设‘0’为空结点，输入非‘0’数，生成新结点，递归创建左子树和右子树。 9、Search函数：采用先序遍历查找给定元素是否在二叉树中，首先判断树是否是空树，若是空树，则返回空指针。然后初始化临时指针temp，查找成功后temp即为所给元素所在 本程序由SOGOF完成 该完整程序主要是递归函数的使用及模板的使用，完成了对二叉树基本的链表操作，主要有二叉树的建立，前序、中序、后序遍历，求树的高度，每层结点数（包含树的最大宽度），左右结点对换，二叉树的内存释放，求解树的叶子数。 #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 << " "; } } 运行截图： 浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验十二叉树的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期2014-12-18 一.实验目的和要求 1、掌握二叉树的链式存储结构。 2、掌握在二叉链表上的二叉树操作的实现原理与方法。 3、进一步掌握递归算法的设计方法。 二.实验内容 1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test4_1.cpp，验证头文件中各个操作。 二叉树二叉链表存储表示如下： struct BTreeNode { ElemType data; // 结点值域 BTreeNode *lchild , *rchild ; // 定义左右孩子指针 } ; 基本操作如下： ①void InitBTree( BTreeNode *&BT ); //初始化二叉树BT ②void CreateBTree( BTreeNode *&BT, char *a ); //根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构 ③int EmptyBTree( BTreeNode *BT); //检查二叉树BT是否为空，空返回1，否则返回0 ④int DepthBTree( BTreeNode *BT); //求二叉树BT的深度并返回该值 ⑤int FindBTree( BTreeNode *BT, ElemType x); //查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 ⑥void PreOrder( BTreeNode *BT); //先序遍历二叉树BT ⑦void InOrder( BTreeNode *BT); //中序遍历二叉树BT ⑧void PostOrder( BTreeNode *BT); //后序遍历二叉树BT 算法与数据结构》课程实验报告 一、实验目的 1、实现二叉树的存储结构 2、熟悉二叉树基本术语的含义 3、掌握二叉树相关操作的具体实现方法 二、实验内容及要求 1. 建立二叉树 2. 计算结点所在的层次 3. 统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历 8. 二叉树的复制 9. 二叉树的输出等 三、系统分析 （1）数据方面：该二叉树数据元素采用字符char 型，并且约定“ #”作为二叉树输入结束标识符。并在此基础上进行二叉树相关操作。 （2）功能方面：能够实现二叉树的一些基本操作，主要包括： 1. 采用广义表建立二叉树。 2. 计算二叉树高度、统计结点数量、叶节点数量、计算每个结点的度、结点所在层次。 3. 判断结点是否存在二叉树中。 4. 寻找结点父结点、子女结点。 5. 递归、非递归两种方式输出二叉树前序、中序、后序遍历。 6. 进行二叉树的复制。 四、系统设计 （1）设计的主要思路 二叉树是的结点是一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。根据实验要求，以及课上老师对于二叉树存储结构、基本应用的讲解，同时课后研究书中涉及二叉树代码完成二叉树模板类，并将所需实现各个功能代码编写完成，在建立菜单对功能进行调试。 （2）数据结构的设计 二叉树的存储结构有数组方式和链表方式。但用数组来存储二叉树有可能会消耗大量的存储空间，故在此选用链表存储，提高存储空间的利用率。根据二叉树的定义，二叉 数据结构 实 验 报 告 1. 实验目的和内容： 掌握二叉树基本操作的实现方法2. 程序分析 2.1存储结构 链式存储 2．程序流程 2.3关键算法分析 算法一：Create(BiNode 算法三：PreOrder(BiNode 实验五-二叉树基本操作的编程实现实验报告 ————————————————————————————————作者：————————————————————————————————日期： HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY 数据结构 实验报告 这里一定填 写清楚自己 实验项目实验五实验类别基础篇 学生姓名朱忠栋学生学号20120231515 完成日期2014-12-16 指导教师付勇智 实验成绩评阅日期 评阅教师 实验五二叉树基本操作的编程实现 【实验目的】 内容：二叉树基本操作的编程实现 要求： 二叉树基本操作的编程实现（2学时，验证型），掌握二叉树的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找等操作，存储结构主要采用顺序或链接结构。也鼓励学生利用基本操作进行一些应用的程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 以下的选题都可以作为本次实验的推荐题目 1.建立二叉树，并以前序遍历的方式将结点内容输出。 2.将一个表示二叉树的数组结构转换成链表结构。 3.将表达式二叉树方式存入数组，以递归方式建立表达式之二叉树状结构，再分别输出前序、中序 及后序遍历结果，并计算出表达式之结果。 【注意事项】 1.开发语言：使用C。 2.可以自己增加其他功能。 【实验分析、说明过程】 页面不够，可续页。 根据自己选择的层次不同的实验内容，完善程序代码，调试通过后，分析说明该问题处理的详细算法过程。不需要写出详细的代码，只表达清楚详细的处理算法即可。可以采用流程图、形式语言或者其他数学表达方式来说明。 这次实验考查的主要是：递归建立二叉树，递归输出先序，中序和后序遍历的结果；非递归建立二叉树，再以非递归方式分别输出先序，中序和后序遍历的结果。 而对于基础篇考查的主要是：递归建立二叉树，递归输出先序，中序和后序遍历的结果，是以填空的方式进行考查的。 对于第一空：递归实现的先序遍历，其实现方法是： printf("%d",p->data); if(p->lchild!=NULL) preorder(p->lchild); if(p->rchild!=NULL) preorder(p->rchild); 对于第二空：递归实现的中序遍历，其实现方法是： if(p->lchild!=NULL) inorder(p->lchild); printf("%d",p->data); if(p->rchild!=NULL) inorder(p->rchild); 对于第三空：递归实现的后序遍历，其实现方法是： if(p->lchild!=NULL) postorder(p->lchild); if(p->rchild!=NULL) postorder(p->rchild); printf("%d",p->data); 【思考问题】 页面不够，可续页。 1.二叉树是树吗？它的定义为什么是递归的？ 答：最多有两棵子树的有序树，称为二叉树。二叉树是一种特殊的树。具有n个结点的完全二叉树的深度为log2n +1 ！！！二叉树的计算方法：若一棵二叉树为空,则其深度为0, 二叉树的基本操作实验报告 学号姓名实验日期 2012-12-26 实验室计算机软件技术实验指导教师设备编号 401 实验内容二叉树的基本操作 一实验题目 实现二叉树的基本操作的代码实现 二实验目的 1、掌握二叉树的基本特性 2、掌握二叉树的先序、中序、后序的递归遍历算法 3、通过求二叉树的深度、度为2的结点数和叶子结点数等算法三实习要求 (1)认真阅读书上给出的算法 (2)编写程序并独立调试 四、给出二叉树的抽象数据类型 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， // (4)(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树;(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。 //基本操作: CreateBiTree( &T, definition ) // 初始条件:definition给出二叉树T的定义。 // 操作结果:按definiton构造二叉树T。 BiTreeDepth( T ) // 初始条件:二叉树T存在。 // 操作结果:返回T的深度。 PreOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 InOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 PostOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 LeafNodes(p) // 初始条件:二叉树T存在。 // 操作结果:返回T的叶子结点数。数据结构二叉树实验报告
实验三 二叉树的基本操作实现及其应用
二叉树的基本 操作
树和二叉树实验报告
二叉树的基本操作实验
二叉树的建立和遍历的实验报告doc
数据结构——二叉树基本操作源代码
二叉树实验报告及代码
二叉树基本操作+数据结构+实验报告
数据结构实验二叉树
数据结构实验三——二叉树基本操作及运算实验报告
二叉树实验报告
二叉树基本操作经典实例
数据结构实验报告之树与二叉树
实验10 二叉树的基本操作
数据结构实验报告—二叉树
数据结构二叉树的实验报告
实验五-二叉树基本操作的编程实现实验分析报告
二叉树的基本操作实验报告
相关主题
文本预览