数据结构课程设计实验报告
实验二 树和图部分            选题为：6.4.6—打印树形结构
1、需求分析
（1）创建二叉树。按照用户需要的二叉树，构建二叉树
（2）将创建的二叉树以凹入表形式打印出来。
（3）对二叉树以中序遍历方式遍历
（4）通过结点的深度标志位控制打印时结点的横向位置
2、概要设计
为了实现以上功能，可以从以下3个方面着手设计。
（1）主界面设计
为了实现二叉树相关操作功能的管理，设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本程序。本系统主控菜单运行界面如下所示。
（2）存储结构设计
本程序采用二叉链式存储类型（BITNode）存储二叉树的节点信息。二叉树的链表中的结点包含四个域：数据域（data）、左孩子指针域（lchild）、有孩子指针域（rchild）和结点深度标志域（depth）。
（3）系统功能设计
本程序设计了3个功能子菜单，其描述如下：
1二叉树的初始化。由函数CreatTree（）实现。该功能按照自上而下从左往右的顺序输入二
叉树结点，构造二叉树。
2打印树形结构。由函数RDL（）实现。该函数实现二叉树的中序遍历，并同时格式化输出结点的数据信息。
3退出操作。由exit（0）函数实现。
3、模块设计
1模块设计
本程序包含两个模块：主程序模块和二叉树操作模块。其调用关系如下图所示：
2系统子程序及功能设计
本系统共设置3个子程序，各程序的函数名及功能说明如下：
a. BiTree CreatTree()    //建立二叉树，并返回根指针
b. void RDL(BiTree T)        //使用RDL的中序遍历方式遍历二叉树，并输出打印结果
c. void main()        //主函数。调用二叉树操作模块
3函数主要调用关系图
本系统3个子程序之间的主要调用关系如图所示。
4、详细设计
（1）数据类型定义
typedef struct BiTNode{//定义二叉树结点
    char data;
    struct BiTNode *lchild;//左孩子指针
    struct BiTNode *rchild;//有孩子指针
    int depth;//结点深度，用于打印控制横向的位置
}BiTNode,*BiTree;
（2）系统主要子程序详细设计
①建立二叉树模块
BiTree CreatTree(){//建立二叉树，并返回根指针
    int front,rear;
    front=1;
    rear=0;
    char ch;//由于接收输入的字符
    char c;
    BiTree T,s;
    T=NULL;//初始置空二叉树
    printf("创建二叉树，请输入结点信息:(空结点请输入:#，结束请输入:@)\n");
    c=getchar();//用于消除菜单键的回车
    ch=getchar();//接收第一个字符
    while(ch!='@')
    {
        s=NULL;//s为新结点
        if(ch!='#')//为非空结点
        {
            s=(BiTree)malloc(sizeof(BiTree));
            s->data=ch;
            s->lchild=NULL;//左右孩子置空
            s->rchild=NULL;
            s->depth=0;//深度置为0
        }
        rear++;
        Q[rear]=s;//新结点进入队列
        if(rear==1)//为第一个结点
        {
            T=s;
        }
        else
        {
            if(s!=NULL&&Q[front]!=NULL)//孩子和双亲结点均不为空结点
            {
                if(rear%2==0)
                    Q[front]->lchild=s;//rear偶数时,为父结点的左孩子
                else
                    Q[front]->rchild=s;//rear奇数时,为父结点的右孩子
                s->depth=Q[front]->depth+1;
            }
            if(rear%2==1)
                front++;//结点的两个孩子均已处理
        }
        ch=getchar();//继续下一个输入
    }
    return T;
}
二叉树的遍历及应用实验报告②中序遍历并输出二叉树模块
void RDL(BiTree T){//使用RDL的中序遍历方式，便于打印结果
    if(T)
    {
        RDL(T->rchild);//递归遍历右子树
        for(int i=0;i<T->depth;i++)
        {
            printf("\t");//输出格式控制
        }
        printf("%4c\n",T->data);//输出结点信息
        RDL(T->lchild);//递归遍历左子树
    }
}
5、测试分析
（1）实验中遇到的问题以及对设计与实现的回顾讨论和分析
1二叉树建立时，在输入格式中，以Enter键入作为结束标志，结果导致二叉树不能建立，原因是因为菜单键中的Enter存在于缓冲区并输入到二叉树中，直接结束了。后经排查，发现了问题，将结束符用特定的’@’作为结尾，成功实现建立功能
2同样是在二叉树的建立过程中，原先在CreatTree（）函数中，并未使用一个单独的字符接收菜单中的回车字符，导致二叉树根结点建立的时候其数据为回车字符。经过加入字符c吸收回车字符，程序能够实现了。
3树形结构的输出需要使用到遍历的思想，本次算法采用RDL的中序遍历思想，因为右子树总是位于根结点的上方，故先应该遍历右子树，然后显示结点的数据，再遍历左子树。
4打印算法包含于遍历函数中，并采用格式化的方法，从结点本身存储的depth来控制横向输出的位置。
（2）算法的时空分析
在二叉树的建立过程中，花费的时间集中于while（ch!=’@’）的循环中，其时间复杂度为O（n），其中n为结点的个数。
（3）经验和体会
通过此次试验，对于二叉树的建立以及遍历有了更深的理解，能够使用不同方法按照需求实现二叉树的遍历，同时对于队列的知识也是一次复习的机会，能够综合利用所学，解决实际问题，受益颇深。
（4）测试功能展示
1二叉树的建立
在主菜单下，用户输入1并回车，然后按照提示建立二叉树，运行结果如下所示：
2打印树形结构
在主菜单下，用户输入2并回车，可以以凹入表方式打印选项1中已经建立的二叉树，运行结果如下所示：
3边界数据的测试如下：
6、源程序清单
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef struct BiTNode{//定义二叉树结点

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