三叉链表存储结构及其非递归遍历算法.pdf

数据结构实验报告

知识范畴：树

实验题目：二叉树的基本算法二(三叉链表的建立、非递归遍历)

实验内容及要求：

设二叉树采用三叉链表存储结构，结点数据域为字符类型，从键盘输入先序遍历字符序列

（用#字符表示NULL指针域）建立三叉链表存储结构。对先序、中序、后序遍历分别定义各自

的求第一访问结点地址first(bt)以及下一访问结点地址next(p)函数，然后用三种遍历的

first(bt)和next(p)函数实现非递归遍历。

实验目的：掌握二叉树的三叉链表存储结构及其非递归遍历算法。

数据结构设计简要描述：

采用双向链表，每个结点包括字符类型的数据域和一个指针域。链表结点结构如下：

typedefstructnode

{

ElemTpdata;//字符数据域

structnode*lchild;//左儿子指针

structnode*rchild;//右儿子指针

structnode*parent;//双亲指针

}

算法设计简要描述：

采用三叉链表的存储结构，双亲指针指向根结点，左右指针指向左右儿子构造双向链表的

二叉树。

每一次遍历时先用该遍历的first函数获取第一个访问的结点地址，调用next函数获取

下一个访问的结点地址，当结点为空为循环的结束条件。

获取下一个访问的结点地址时需要判断是否需要回溯，需要回溯时通过双亲指针获取根节

点地址，再判断是否需要再回溯。回溯的结束条件为根节点地址为空。

输入/输出设计简要描述：

从键盘输入二叉树的数据域，用#表示空。按先序遍历的顺序依次构建二叉树。

输出三种遍历的遍历结果，并有文字提示。

编程语言说明：

使用VisualC++编程。主要代码采用C语言实现；动态存储分配采用C的malloc操作

符实现；输入与输出采用C的printf和scanf流；程序注释采用C/C++规范。

1/10

主要函数说明：

voidInitTrT(TrTbt)//初始化二叉树

voidcrtTrT(TrT*bt)//创建三叉结构的二叉树

voiddestroyTrT(TrT*bt)//销毁二叉树

StatusemptyTrT(TrTbt)//判断二叉树是否为空

intdepthTrT(TrTbt)//求二叉树的深度

TrTprefirst(TrTbt)//找出先序遍历的第一个结点

TrTprenext(TrTbt)//找出先序遍历的下一结点

voidpreorder(TrTbt)//先序非递归遍历

TrTmidfirst(TrTbt,intmark)//查找中序遍历的第一个结点

TrTmidnext(TrTbt,intmark)//查找中序遍历的下一个结点

voidmidorder(TrTbt)//中序非递归遍历

TrTlastfirst(TrTbt,intmark)//查找后序遍历的第一个结点

TrTlastnext(TrTbt,intmark)//查找后序遍历的下一个结点

voidlasorder(TrTbt)//后序非递归遍历

程序测试简要报告：

输入：ABC#F##D##E##

输出：

程序输出结果与期望输出结果相符。

源程序代码：

#includestdio.h

#includestdlib.h

typedefcharElemTp;

typedefenum{ERROR,OK}Status;

typedefstructnode

{

ElemTpdata;//字符数据域

structnode*lchild;//左儿子指针

structnode*rchild;//右儿子指针

2/10

structnode*parent;//双亲指针

}*TrT,T