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

线索化二叉树遍历实验报告09040502班学号:052415朱博凯一、 需求分析（1） 本程序需要用户自行输入二叉树（二叉树的数据可以是任何字符），用”#”表示空格，按回车键结束！（2） 程序功能：遍历二叉树，线索化二叉树，遍历线索化二叉树，二叉树去线索化。（3） 测试数据：ABC#DE#G#F#；二、 概要设计为实现本程序功能，应以二叉树结构存储二叉树，而为了实现非递归遍历二叉树的功能，应以带头节点的栈存储二叉树。1、 二叉树的抽象数据类型定义ADT BinaryTree 数据对象D：D是具有相同特性的数据元素集合。 数据关系R：如D=，则R=，称BinaryTree为空二叉树； 如D，则R=H，H是如下二元关系：（1） 在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；（2） 如D-root,则存在D-root=D1,Dr,且D1Dr=;（3） 如D1,则D1中存在唯一元素x1,ROOT,X1H,且存在D1上的关系H1H；如Dr，则Dr中存在唯一的元素xr，ROOT,XrH,且存在Dr上的关系Hr包含于H；H=ROOT,X1,ROOT,Xr,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 BinaryTree2、 栈的抽象数据类型定义ADT Stack数据对象：d= ai |aielemset,i=1,2,3,，n，n0数据关系：r=| 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 Stack3、 程序包括6个模块1） 主程序模块：2） 创建二叉树；3） 计算树的高度；4） 递归遍历二叉树（先、中、后序）；5） 非递归遍历二叉树（先、中序）；6） 线索化二叉树（先、中序）；7） 二叉树去线索化；三、 详细设计1、 元素类型、结点类型typedef struct BiTNodeTElemType data;struct BiTNode *lchild ,*rchild;PointerTag LTag , RTag;BiTNode , *BiTree , BiThrNode , *BiThrTree;/二叉树typedef structBiTree *base;BiTree *top;int stacksize;SqStack;/栈2、 栈的实现typedef structchar *base;char *top;int stacksize;SqStack;/栈类型栈的基本操作设置如下：void InitStack(Stack &S)/初始化，设S为空栈（S.top=NULL）void DestroyStack(Stack &S)/销毁栈S，并释放所占空间void ClearStack(Stack &S)/将S清为空栈int StackLength(Stack S)/返回栈S的长度S.sizeStatus StackEmpty(Stack S)/若S为空栈（S.top=NULL），则返回TRUE；否则返回FALSEStatus GetTop(Stack S,ElemType e)/若栈S不空，则以e带回栈顶元素并返回TRUE，否则返回FALSEStatus Push(Stack&S,ElemType e)/若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE，/否则返回FALSEvoid StackTraverse(Stack S,Status (*visit)(ElemType e)/从栈底到栈顶依次对S中的每个结点调用函数visit3、 主函数和其他函数的伪码typedef int status;typedef char TElemType;typedef enum PointerTagLink,Thread;/二叉树的操作status CreatBiTree(BiTree &T);status treedepth(BiTree T);status Visit(TElemType e);status PreOrderTraverse(BiTree T,status(*Visit)(TElemType e);status InOrderTraverse(BiTree T,status(*Visit)(TElemType e);status PostOrderTraverse(BiTree T,status(*Visit)(TElemType e);status UnInOrderTraverse(BiTree T,status(*Visit)(TElemType e);/非递归中序遍历status UnPreOrderTraverse(BiTree T,status(*Visit)(TElemType e);/非递归先序遍历/线索化二叉树的操作void InOrderThreading(BiThrTree &Thrt,BiThrTree T);void InThreading(BiThrTree p);status InOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType e);void PreOrderThreading(BiThrTree &Thrt,BiThrTree T);status PreOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType e);void PreThreading(BiThrTree p);void UnThreading(BiThrTree &Thrt);/栈的操作status InitStack(SqStack &S);status GetTop(SqStack S , BiTree &e);status Push(SqStack &S , BiTree e);status Pop(SqStack &S , BiTree &e);status StackEmpty(SqStack S);/全局变量SqStack S;BiThrTree pre;BiThrTree i;void main()/主函数printf(t*nt*二叉树演示*nt*n);BiTree T;BiThrTree Thrt;printf(n创建二叉树(用#表示空格):n);CreatBiTree(T);printf(树的高度为:%d,treedepth(T);printf(n递归先序遍历:);PreOrderTraverse(T , Visit);printf(n递归中序遍历:);InOrderTraverse(T , Visit);printf(n递归后序遍历:);PostOrderTraverse(T , Visit);printf(n非递归中序遍历:);UnInOrderTraverse(T , Visit);printf(n非递归先序遍历:);UnPreOrderTraverse(T , Visit);printf(n中序遍历线索化二叉树:);InOrderThreading(Thrt , T);InOrderTraverse_Thr(Thrt , Visit);printf(n后序递归去线索化并输出:);UnThreading(Thrt);printf(n先序遍历线索化二叉树:);PreOrderThreading(Thrt , T);printf(n);status CreatBiTree(BiTree &T)/创建二叉树char ch;ch=getchar();if(ch=#)T=NULL;elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode)return ERROR;T-data=ch;if (CreatBiTree(T-lchild) T-LTag=Link;if (CreatBiTree(T-rchild) T-RTag=Link;return OK;status treedepth(BiTree T)/计算树的高度int lchilddep,rchilddep;if(T=NULL)return 0;elselchilddep=treedepth(T-lchild);rchilddep=treedepth(T-rchild);if(lchilddeprchilddep)return lchilddep+1;elsereturn rchilddep+1;status Visit(TElemType e)printf(%c,e);return OK;status PreOrderTraverse(BiTree T,status(*Visit)(TElemType e)/递归先序遍历if(T)if(Visit(T-data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverse(T-rchild,Visit)return OK;return ERROR;elsereturn OK;/PreOrderTraversestatus InOrderTraverse(BiTree T,status(*Visit)(TElemType e)/递归中序遍历if(T)if(InOrderTraverse(T-lchild,Visit)if(Visit(T-data)if(InOrderTraverse(T-rchild,Visit)return OK;return ERROR;else return OK;/InOrderTraversestatus PostOrderTraverse(BiTree T,status(*Visit)(TElemType e)/递归后序遍历if(T)if(PostOrderTraverse(T-lchild,Visit)if(PostOrderTraverse(T-rchild,Visit)if(Visit(T-data)return OK;return ERROR;else return OK;/PostOrderTraversestatus UnInOrderTraverse(BiTree T,status(*Visit)(TElemType e)/非递归中序遍历BiTree p;InitStack(S);Push(S,T);while(!StackEmpty(S)while(GetTop(S,p) & p)Push(S,p-lchild);Pop(S,p);if(!StackEmpty(S)Pop(S,p);if(!Visit(p-data)return ERROR;Push(S,p-rchild);/if/whilereturn OK;/UnInOrderTraversestatus UnPreOrderTraverse(BiTree T,status(*Visit)(TElemType e)/非递归先序遍历BiTree p;InitStack(S);p=T;while(p|!StackEmpty(S)if(p)if(!Visit(p-data)return ERROR;Push(S,p);p=p-lchild;elsePop(S,p);p=p-rchild;/else/whilereturn OK;/UnPreOrderTraversevoid InOrderThreading(BiThrTree &Thrt,BiThrTree T)/中序遍厉二叉树T，并将其中序线索化，Thrt指向头结点if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW);Thrt-LTag=Link;/建头结点Thrt-RTag=Thread;Thrt-rchild=Thrt;/右指针回指if(!T)Thrt-lchild=Thrt;elseThrt-lchild=T;pre=Thrt;InThreading(T);/中序遍历进行中序线索化pre-rchild=Thrt;pre-RTag=Thread;/最后一个结点线索化Thrt-rchild=pre;i=Thrt;/InOrderThreadingvoid InThreading(BiThrTree p)/线索化if(p)InThreading(p-lchild);if(!p-lchild)p-LTag = Thread;p-lchild = pre;if(!pre-rchild)pre-RTag = Thread;pre-rchild = p;pre = p;InThreading(p-rchild);/InThreadingvoid UnThreading(BiThrTree &Thrt) /后序去线索化BiThrTree p=Thrt;if(p)if(p-LTag = Thread)p-lchild = NULL;p-LTag = Link;if(p-LTag = Link & p-lchild) UnThreading(p-lchild);if(p-RTag = Link & p-rchild)UnThreading(p-rchild);if(p != i) Visit(p-data);status InOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType e)/中序遍历线索化后的二叉树BiThrTree p;p=T-lchild;while(p!=T)while(p-LTag=Link)p=p-lchild;if(!Visit(p-data)return ERROR;while(p-RTag=Thread & p-rchild!=T)p=p-rchild;Visit(p-data);p=p-rchild;return OK;void PreOrderThreading(BiThrTree &Thrt,BiThrTree T)/先序遍厉二叉树T，并将其先序线索化，Thrt指向头结点if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread;/建头结点Thrt-rchild=Thrt;/右指针回指if(!T)Thrt-lchild=Thrt;elseThrt-lchild=T;pre=Thrt;PreThreading(T);/先序遍历进行先序线索化pre-rchild=Thrt;pre-RTag=Thread;/最后一个结点线索化Thrt-rchild=pre;i=Thrt;status PreOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType e) /先序遍历线索化后的二叉树BiThrTree p;p=T-lchild;while(p!=T)while(p-LTag=Link)p=p-lchild;if(!Visit(p-data)return ERROR;while(p-RTag=Thread & p-rchild!=T)p=p-rchild; Visit(p-data);p=p-rchild;return OK;/PreOrderTraverse_Thrvoid PreThreading(BiThrTree p)/先序线索化if(p)if(!p-lchild)p-LTag = Thread;p-lchild = pre;if(!pre-rchild)pre-RTag = Thread;pre-rchild = p;pre = p;Visit(p-data);if(p-LTag=Link)PreThreading(p-lchild);if(p-RTag = Link)PreThreading(p-rchild);/PreThreadingstatus InitStack(SqStack &S)/栈的初始化S.base=(BiTree *)malloc(STACK_INIT_SIZE * sizeof(BiTree);if(!S.base)exit(OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;status GetTop(SqStack S , BiTree &e)/取顶元素if(S.top = S.base) return ERROR;elsee = *(S.top-1);return OK;status Push(SqStack &S , BiTree e)/进栈if(S.top - S.base = S.stacksize)S.base = (BiTree *)realloc(S.base , (S.stacksize + STACKINCREMENT) * sizeof(BiTree);if(!S.base) exit(OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;*S.top+ = e;return OK;status Pop(SqStack &S , BiTree &e)/出栈if(S.top = S.base)return ERR