数学与计算机学院计算机系实验报告
课程名称： 数据结构
年级：2010
实验成绩：
指导教师： 黄襄念
姓名：
实验教室：6A-413
实验名称：二叉树前序或中序或后序遍历
学号：
实验日期：2012/6/10
实验序号：实验3
实验时间：8:00—11:40
实验学时：4
一、实验目的
1. 熟悉的掌握树的创建，和树的前序、中序、后序遍历。
二、实验环境
1. 操作系统：Windows7
2. 开发软件：Microsoft Visual C++ 6.0
三、实验内容
● 程序功能
本程序完成了以下功能：
1. 前序遍历
2. 中序遍历
3. 后序遍历
● 数据结构
本程序中使用的数据结构（若有多个，逐个说明）：
1. 它的优缺点
1） 可以快速的查数据。
2） 让数据层次更加清晰。
2. 逻辑结构图
                       
3. 存储结构图
                                        NULL
、、、、、、、、、、、、、、、、、、、、
4. 存储结构的C/C++ 语言描述
typedef struct node {
    DataType data;
    struct node *lchild;
    struct node *rchild;
} BiTNode, *BiTree;
typedef BiTree type;
● 算法描述
本程序中采用的算法
1. 算法名称：递归
2. 算法原理或思想
是通过访问结点的左右孩子来进行循环查的方法，拿中序遍历来说明：先从头结点开始，再去访问头结点的右孩子如果为空就访问头结点的左孩子，依次进行访问当结点的左右孩子都为空时，就访问上一级，到了最后。
3. 算法特点
它能将查进行2分，体现出了更高效快捷的特点，并且层次很清晰。
● 程序说明
1. 系统流程图
2. 程序模块
1）前序遍历模块：将树进行从头结点开始再左孩子再右孩子。
代码：void InOrder(BiTree root)
{
    Stack S(100);
    initStack(S);
    BiTNode *p = root;
    do
    {
        while(p != NULL)
        {
            Push(S, p);
            p = p->lchild;
        }
        if(!isEmpty(S))
        {
            Pop(S, p);
            cout << p->data << " ";
            p = p->rchild;
        }
    } while(p != NULL || !isEmpty(S));
    cout << endl;
}
2） 后序遍历模块：将树进行从左孩子开始再右孩子再头结点。
代码：void PostOrder(BiTree root)
{
    Stack S(100);
    Stack SS(100);
    initStack(S);
    initStack(SS);
    BiTNode *p = root;
    do
    {
        while(p != NULL)
        {
            Push(S, p);
            Push(SS, p);
            p = p->rchild;
        }
        if(!isEmpty(S))
        {
            Pop(S, p);
            p = p->lchild;
        }
先序中序后序遍历二叉树
    } while(p != NULL || !isEmpty(S));
    while(!isEmpty(SS))
    {
        Pop(SS, p);
        cout << p->data << " ";
    }
    cout << endl;
}
3） 中序遍历模块：将树进行从左孩子开始再头结点再右孩子。
代码：void PreOrder(BiTree root)
{
    Stack S(100);
    initStack(S);
    BiTNode *p = root;
    do
    {
        while(p != NULL)
        {
            Push(S, p);
            cout << p->data << " ";
            p = p->lchild;
        }
        if(!isEmpty(S))
        {
            Pop(S, p);
            p = p->rchild;
        }
    } while(p != NULL || !isEmpty(S));
    cout << endl;
}
四、调试与运行
1. 程序调试
本程序开发过程中，采用的调试方法或手段如下：
1) 方法1：在程序执行的终止的函数中加一条输出语句cout<<”*******”<<endl；进行错误的定位，调试了指针没有正确使用的错误。
2) 方法2：输出一些树中的数据，看能不能正确的输出，调试了其左右孩子是不是正确。
2. 运行结果
  本次实验多个功能需分别截图，逐个说明。
运行结果图1
……
五、实验总结
1. 结果分析：本程序完成了树的前序遍历、中序遍历、后序遍历功能；但是还是存在不完善的地方，没有对结点进行删除增加等操作，没有将树的结构给输出。
2. 心得体会：通过这个实验我更熟练的掌握了二叉树的结构同时也更了解了递归算法，觉得数据结构是一个很不错的一门课程。
代码：
#include <iostream>
#include <stack>
using namespace std;
using std::cout;
using std::endl;
typedef char DataType;
typedef struct node {
    DataType data;
    struct node *lchild;
    struct node *rchild;
} BiTNode, *BiTree;
typedef BiTree type;
class Stack
{
    friend void initStack(Stack &S);
    friend bool isEmpty(Stack &S);
    friend bool Push(Stack &S, type x);
    friend bool Pop(Stack &S, type &x);
    friend bool getTop(Stack &S, type &x);
public:
    Stack(int maxSize)
    {
        if(maxSize < 0)
        {
            throw std::exception("argument maxSize is illegal.");
        }
        this->maxSize = maxSize;
        this->s = NULL;
    }
    virtual ~Stack()
    {
        if(this->s != NULL)
        {
            delete this->s;
            this->s = NULL;
        }
    }
protected:
    int maxSize;
    std::stack<type> *s;
};
void initStack(Stack &S)
{
    if(S.s != NULL)
    {
        delete S.s;
        S.s = NULL;
    }
    S.s = new std::stack<type>();
}
bool isEmpty(Stack &S)
{
    return S.s->empty();
}
bool Push(Stack &S, type x)
{
    if(S.s->size() == S.maxSize)
    {
        return false;
    }
    S.s->push(x);
    return true;
}
bool Pop(Stack &S, type &x)
{
    if(S.s->empty())
    {
        return false;
    }
    x = S.s->top();
    S.s->pop();
    return true;
}
bool getTop(Stack &S, type &x)
{
    if(S.s->empty())
    {
        return false;
    }
    x = S.s->top();
    return true;
}
void PreOrder(BiTree root)
{
    Stack S(100);
    initStack(S);
    BiTNode *p = root;
    do
    {
        while(p != NULL)
        {
            Push(S, p);
            cout << p->data << " ";
            p = p->lchild;
        }
        if(!isEmpty(S))
        {
            Pop(S, p);
            p = p->rchild;
        }
    } while(p != NULL || !isEmpty(S));