数据结构实验报告
知识范畴：树                     
实验题目：二叉树的基本算法二(三叉链表的建立、非递归遍历)
实验内容及要求：
设二叉树采用三叉链表存储结构，结点数据域为字符类型，从键盘输入先序遍历字符序列（用#字符表示NULL指针域）建立三叉链表存储结构。对先序、中序、后序遍历分别定义各自的求第一访问结点地址first(bt)以及下一访问结点地址next(p)函数，然后用三种遍历的first(bt)和next(p)函数实现非递归遍历。
实验目的：掌握二叉树的三叉链表存储结构及其非递归遍历算法。
数据结构设计简要描述：
采用双向链表，每个结点包括字符类型的数据域和一个指针域。链表结点结构如下：
typedef struct node
{
    ElemTp data;            //字符数据域
    struct node *lchild;    //左儿子指针
    struct node *rchild;    //右儿子指针
    struct node *parent;    //双亲指针
}
算法设计简要描述：
采用三叉链表的存储结构，双亲指针指向根结点，左右指针指向左右儿子构造双向链表的二叉树。
每一次遍历时先用该遍历的first函数获取第一个访问的结点地址，调用next函数获取下一个访问的结点地址，当结点为空为循环的结束条件。
获取下一个访问的结点地址时需要判断是否需要回溯，需要回溯时通过双亲指针获取根节点地址，再判断是否需要再回溯。回溯的结束条件为根节点地址为空。
输入/输出设计简要描述：
从键盘输入二叉树的数据域，用#表示空。按先序遍历的顺序依次构建二叉树。
输出三种遍历的遍历结果，并有文字提示。
编程语言说明：
    使用Visual C++编程。 主要代码采用C语言实现 ；动态存储分配采用C的malloc操作符实现；输入与输出采用C的printf和scanf流；程序注释采用C/C++规范。
主要函数说明：
void InitTrT(TrT bt) //初始化二叉树
void crtTrT(TrT *bt) //创建三叉结构的二叉树
void destroyTrT(TrT *bt) //销毁二叉树
Status emptyTrT(TrT bt) //判断二叉树是否为空
int depthTrT(TrT bt) //求二叉树的深度
TrT prefirst(TrT bt) //出先序遍历的第一个结点
TrT prenext(TrT bt) //出先序遍历的下一结点
void preorder(TrT bt) //先序非递归遍历
TrT midfirst(TrT bt,int &mark) //查中序遍历的第一个结点
TrT midnext(TrT bt,int &mark) //查中序遍历的下一个结点
void midorder(TrT bt) //中序非递归遍历
TrT lastfirst(TrT bt,int &mark) //查后序遍历的第一个结点
TrT lastnext(TrT bt,int &mark) //查后序遍历的下一个结点
void lasorder(TrT bt) //后序非递归遍历
程序测试简要报告：
输入：ABC#F##D##E##
输出：
程序输出结果与期望输出结果相符。
源程序代码：
#include<stdio.h>
#include<stdlib.h>
typedef char ElemTp;
typedef enum {ERROR,OK} Status;
typedef struct node
{
    ElemTp data;            //字符数据域
    struct node *lchild;    //左儿子指针
    struct node *rchild;    //右儿子指针
    struct node *parent;    //双亲指针
}*TrT,TrTnode;
//初始化二叉树
void InitTrT(TrT bt)
{
    bt =NULL;
}
//创建三叉结构的二叉树
void crtTrT(TrT *bt)
{
    ElemTp ch;   
    scanf("\n");
    scanf("%c",&ch);
    if(ch=='#') //输入#字符表示NULL指针域
        *bt = NULL;
    else
    {
        *bt = (TrT)malloc(sizeof(TrTnode));
        if(!*bt)
二叉树的遍历及应用实验报告            exit(0);
        (*bt)->data = ch;
        (*bt)->parent = NULL;    //根结点的父母结点指针置为空
        crtTrT(&(*bt)->lchild);
        if((*bt)->lchild)
            (*bt)->lchild->parent = *bt;
        crtTrT(&(*bt)->rchild);
        if((*bt)->rchild)
            (*bt)->rchild->parent = *bt;
    }
}
//销毁二叉树
void destroyTrT(TrT *bt)
{
    if(*bt)
    {
        if((*bt)->lchild)
            destroyTrT(&(*bt)->lchild);
        if((*bt)->rchild)
            destroyTrT(&(*bt)->rchild);
        free(*bt);
        *bt = NULL;
    }
}
//判断二叉树是否为空
Status emptyTrT(TrT bt)
{
    if(bt)
        return ERROR;
    return OK;
}
//求二叉树的深度
int depthTrT(TrT bt)
{
    int i,j;
    if(!bt)
        return 0;
   
    if(bt->lchild)
        i = depthTrT(bt->lchild);
    else i = 0;
   
    if(bt->lchild)
        j = depthTrT(bt->lchild);
    else j = 0;
    return i>j?i+1:j+1;
}
//出先序遍历的第一个结点
TrT prefirst(TrT bt)
{
    while(bt)
        return bt;
    return NULL;
}
//出先序遍历的下一结点
TrT prenext(TrT bt)

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