线索化二叉树遍历实验报告.doc

线索化二叉树遍历实验报告 学号:052415 朱博凯 需求分析 本程序需要用户自行输入二叉树（二叉树的数据可以是任何字符），用”#”表示空格，按回车键结束！ 程序功能：遍历二叉树，线索化二叉树，遍历线索化二叉树，二叉树去线索化。 测试数据： ABC##DE#G##F###；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,X SPAN1∈H,且存在D1上的关系H1∈H；如Dr≠Ф，则Dr中存在唯一的元素xr，ROOT,X SPANr∈H,且存在Dr上的关系Hr包含于H；H={ROOT,X SPAN1,ROOT,X SPANr,H1,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。 PostOrderTraverse(T); 初始条件：二叉树T存在。 操作结果：后序递归遍历T。 InOrderThreading(ThrT, T); 初始条件：二叉树T存在。 操作结果：建立头结点ThrT,并调用InThreading(T);函数。 InThreading(T); 初始条件：二叉树T存在。 操作结果：中序线索化二叉树T; InOrderTrasverse_Thr(T); 初始条件：二叉树T存在。 操作结果：中序扫描线索化的二叉树。 }ADT BinaryTree 栈的抽象数据类型定义 ADT Stack{数据对象：d={ ai |ai∈elemset,i=1,2,3,……，n，n≥0} 数据关系：r={ai-1,ai,)| 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）GetTop（S，e）初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。（7）Push（S,e）初始条件：栈S已存在。 操作结果：在栈顶插入新的元素e。（8）Pop（S,e）初始条件：栈S已存在且非空。 操作结果：删除栈S的栈顶元素，并且用e返回它的值。（9）StackTraverse（S，visit（））初始条件：栈S已存在。操作结果：遍历访问栈，一次对S的每个元素调用函}ADT Stack 程序包括6个模块 主程序模块： 创建二叉树； 计算树的高度； 递归遍历二叉树（先、中、后序）； 非递归遍历二叉树（先、中序）； 线索化二叉树（先、中序）； 二叉树去线索化； 详细设计 元素类型、结点类型 typedef struct BiTNode{ TElemType data; struct BiTNode *lchild ,*rchild; PointerTag LTag , RTag; }BiTNode , *BiTree , BiThrNode , *BiThrTree; //二叉树 typedef struct{ BiTree *base; BiTree *top; int stacksize; }SqStack; //栈 栈的实现 typedef s