《数据结构与算法统计》
实验报告
——实验三
学院：
班级：
学号：
姓名：
一、实验目的
1 熟悉VC环境，学会使用C++解决关于二叉树的问题。
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，<root,x1>∈H，且存在D1上的关系H1 ⊆H；若Dr≠Φ，则Dr中存在惟一的元素xr，<root,xr>∈H，且存在上的关系Hr ⊆H；H={<root,x1>,<root,xr>,H1,Hr}；
（4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。
    基本操作：
CreatBiTree(BiTree &T)
            操作结果：按先序次序建立二叉链表表示的二叉树T        PreOrderTraverse(BiTree T,int (*visit)(char e))
            初始条件：二叉树T已经存在，visit是对结点操作的应用函数
操作结果：先序遍历二叉树T ，对每个结点调用visit函数仅一次；一旦visit（）失败，则操作失败。
    InOrderTraverse(BiTree T,int (*visit)(char e))
            初始条件：二叉树T已经存在，visit是对结点操作的应用函数
操作结果：中序遍历二叉树T ，对每个结点调用visit函数仅一次；一旦visit（）失败，则操作失败。
PostOrderTraverse(BiTree T,int (*visit)(char e))
            初始条件：二叉树T已经存在，visit是对结点操作的应用函数
操作结果：后序遍历二叉树T ，对每个结点调用visit函数仅一次；一旦visit（）失败，则操作失败。
} ADT BinaryTree
⑵主程序流程
主程序先调用CreatBiTree(BiTree &T)函数，根据输入的先序序列构造出一棵二叉树，再依次调用PreOrderTraverse(BiTree T,int (*visit)(char e))，InOrderTraverse(BiTree T,int (*visit)(char e))，PostOrderTraverse(BiTree T,int (*visit)(char e))函数，对该二叉树进行先序、中序、后序遍历并输出结果。
⑶模块调用关系
    由主函数调用创建模块，再调用计算模块，由计算模块将结果输出。
⑷流程图
2、详细设计
⑴数据类型设计
typedef struct BiTNode//二叉树结构类型
{
二叉树定义    char data;//建立数据域
    struct BiTNode *lchild,*rchild;//建立左指针和右指针
}BiTNode,*BiTree;
⑵操作算法设计
int CreatBiTree(BiTree &T)
//按先序次序建立二叉链表表示的二叉树T
{
    char ch;
    scanf("%c",&ch);
    if(ch==' ')
    {
        T=NULL;
    }
    else
    {
        T=(BiTNode *)malloc(sizeof(BiTNode));
        if(!T)
        {
            exit (OVERFLOW);
        }
        T->data=ch;
        CreatBiTree(T->lchild);
        CreatBiTree(T->rchild);
    }
    return 1;
}
int visit(char e)
//对数据进行输出
{
    printf("%c",e);
    return 1;
}
int PreOrderTraverse(BiTree T,int (*visit)(char e))
//先序遍历二叉树T的递归算法
{
    if(T)
    {
        if(visit(T->data))
            if(PreOrderTraverse(T->lchild,visit))
                if(PreOrderTraverse(T->rchild,visit)) return 1;
                    return 0;
    }
    else
        return 1;
}
int InOrderTraverse(BiTree T,int (*visit)(char e))
//中序遍历二叉树T的递归算法
{
    if(T)
    {
        if(InOrderTraverse(T->lchild,visit))
            if(visit(T->data))
                if(InOrderTraverse(T->rchild,visit)) return 1;
                return 0;
    }
    else
        return 1;
}
int PostOrderTraverse(BiTree T,int (*visit)(char e))
//后序遍历二叉树T的递归算法
{
    if(T)
    {
        if(PostOrderTraverse(T->lchild,visit))
            if(PostOrderTraverse(T->rchild,visit))
                if(visit(T->data)) return 1;
                return 0;
    }
    else
        return 1;
}
⑶主函数设计
void main()
//主函数
{
    BiTree T;
    CreatBiTree(T); //按先序次序建立二叉链表表示的二叉树T
    printf("PreOrderTraverse:\n");