资源描述：
《线索化二叉树遍历实验报告2》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、线索化二叉树遍历实验报告09040502班学号:052415朱博凯一、需求分析（1）本程序需要用户自行输入二叉树（二叉树的数据可以是任何字符），用”#”表示空格，按回车键结束！（2）程序功能：遍历二叉树，线索化二叉树，遍历线索化二叉树，二叉树去线索化。（3）测试数据：ABC##DE#G##F###；二、概要设计为实现本程序功能，应以二叉树结构存储二叉树，而为了实现非递归遍历二叉树的功能，应以带头节点的栈存储二叉树。1、二叉树的抽象数据类型定义ADTBinaryTree{数据对象D：D是具有相同特性的数据元素集合。数据关系R：如D=Ф，则R=Ф，称B
2、inaryTree为空二叉树；如D≠Ф，则R={H}，H是如下二元关系：（1） 在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；（2） 如D-{root}≠Ф,则存在D-{root}={D1,Dr},且D1∩Dr=Ф;（3） 如D1≠Ф,则D1中存在唯一元素x1,1>∈H,且存在D1上的关系H1∈H；如Dr≠Ф，则Dr中存在唯一的元素xr，r>∈H,且存在Dr上的关系Hr包含于H；H={1>,r>,H1
3、,Hr}；（4） (D1,{H1})是一棵符合本定义的二叉树，称为根的右子树。基本操作P：InitBiTree(&T);操作结果：构造空二叉树T.DestroyBiTree(&T);初始条件：二叉树T存在。操作结果：销毁二叉树T.CreateBiThrTree(&T);操作结果：先序构造二叉树T,Ltag和RTag初始置为Link.PreOrderTraverse(T);初始条件：二叉树T存在。操作结果：先序递归遍历T。InOrderTraverse(T);初始条件：二叉树T存在。操作结果：中序递归遍历T。PostOrderTravers
4、e(T);初始条件：二叉树T存在。操作结果：后序递归遍历T。InOrderThreading(&ThrT,T);初始条件：二叉树T存在。操作结果：建立头结点ThrT,并调用InThreading(T);函数。InThreading(T);初始条件：二叉树T存在。操作结果：中序线索化二叉树T;InOrderTrasverse_Thr(T);初始条件：二叉树T存在。操作结果：中序扫描线索化的二叉树。}ADTBinaryTree1、栈的抽象数据类型定义ADTStack{数据对象：d={ai
5、ai∈elemset,i=1,2,3,……，n，n≥0}数据关系
6、：r={
7、ai-1,ai∈d,i=2,3,……，n}约定a1为栈底，an为栈顶。基本操作：（1）InitStack(&S)操作结果：构造一个空栈S。（2）DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。（3）ClearStack（&S）初始条件：栈S已存在。。操作结果：将栈清空为空栈。（4）StackEmpty(&S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALSE。（5）StackLength（&S）初始条件：栈S已存在。操作结果：返回栈的长度（或者说深度）。（6）Get
8、Top（S，&e）初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。（7）Push（&S,e）初始条件：栈S已存在。操作结果：在栈顶插入新的元素e。（8）Pop（&S,&e）初始条件：栈S已存在且非空。操作结果：删除栈S的栈顶元素，并且用e返回它的值。（9）StackTraverse（S，visit（））初始条件：栈S已存在。操作结果：遍历访问栈，一次对S的每个元素调用函}ADTStack1、程序包括6个模块1）主程序模块：2）创建二叉树；3）计算树的高度；4）递归遍历二叉树（先、中、后序）；5）非递归遍历二叉树（先、中序）；6）线索化二
9、叉树（先、中序）；7）二叉树去线索化；三、详细设计1、元素类型、结点类型typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;PointerTagLTag,RTag;}BiTNode,*BiTree,BiThrNode,*BiThrTree;//二叉树typedefstruct{BiTree*base;BiTree*top;intstacksize;}SqStack;//栈2、栈的实现typedefstruct{char*base;char*top;intstacksize;
10、}SqStack; //栈类型栈的基本操作设置如下：voidInitStack(Stack&S)
