《数据结构与数据库》
实验报告
实验题目
二叉树的基本操作及运算
一、 需要分析
问题描述：
实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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：
      若，则，称BiTree为空二叉树；
      若，则，H是如下二元关系：
（1） 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；
（2） 若则存在且;
（3） 若则中存在唯一的元素,且存在上的关系若则中存在唯一的元素,且存在上的关系；
（4） 是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的有字树
基本操作：
  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={
    数据关系：R1={<>|, ,i=2,…，n}
约定端为队列头，端为队列尾。
基本操作：
            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 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)
{//插入元素为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)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。