线索二叉树算法的实现

数据结构课程设计 设计说明 线索二叉树算法的实现   学号 班级 成绩   指导教师     计算机科学与技术系 2011 年3月4日 数据结构课程设计评阅书 目 线索二叉树算法的实现 学生姓名 学号 指导教师评语及成绩 成绩： 教师签名： 年 月 日 答辩教师评语及成绩 成绩： 教师签名： 年 月 日 教研室意见 总成绩： 室主任签名： 年 月 日         摘  要 设计了一个线索二叉树的软件，该软件具有创建二叉树、线索二叉树、先序线索二叉树、中序线索二叉树、后序线索二叉树的功能。本软件采用VC++作为软件开发环境，采用C语言各种语句和结构实现二叉树的一系列操作，并采用友好界面向用户提示所操作过程和所输入数据方式，操作简单，界面清晰，易于为用户所接受。 关键字：线索；二叉树；先序；中序；后序 目  录 1 课题描述    1 2 问题分析和任务定义    2 3 逻辑设计    3 4 详细设计    7 5 程序编码    9 6 程序调试与测试    19 7 结果分析    20 8 总结    21 参考文献    22 1 课题描述 本系统重在设计二叉树的各种线索化实现，通过C语言作为编程语言，实现对二叉树的线索化，其中包括先序线索化、中序线索化以及后序线索化。旨在使用户在使用过程中能学会直接调用各种所需函数，以及掌握对二叉树的各种线索化过程。其中各函数分别为：BiThrTree CreateBiTree(BiThrTree &T); //构造二叉树 void PreOrderTraverse(BiThrTree T); //先序遍历二叉树（递归算法） void InOrderTraverse(BiThrTree T); //中序遍历二叉树（递归算法） void PosOrderTraverse(BiThrTree T); //后序遍历二叉树（递归算法） void PreOrder_Stack_Traverse(BiThrTree T); //先序遍历二叉树（非递归算法） void InOrder_Stack_Traverse(BiThrTree T); //中序遍历二叉树（非递归算法） Status PreOrderThreading(BiThrTree &Thrt, BiThrTree T); //先序线索化二叉树 void PreThreading(BiThrTree p); Status InOrderThreading(BiThrTree &Thrt, BiThrTree T); //中序线索化二叉树 void InThreading(BiThrTree p); void PreOrderTraverse_Thr(BiThrTree Thrt); //先序遍历线索化二叉树 void InOrderTraverse_Thr(BiThrTree Thrt);  //中序遍历线索化二叉树 void InOrder_Thr_T(BiThrTree Thrt,BiThrTree &T); //将线索化二叉树还原 开发工具：c语言 运行环境：Visual c++6.0。 2 问题分析和任务定义 本软件要求制作一个能对二叉树线索化的软件，其中包括对二叉树的先序、中序、后序线索化，最后遍历线索化并输出。其中线索化要实现对同一个树的线索化，即应具备还原线索化树的程序，并重新线索化。 3 逻辑设计 本程序由主函数首先调用BiThrTree CreateBiTree(BiThrTree &T);构造二叉树，随后依次调用函数 （1）BiThrTree CreateBiTree(BiThrTree &T); //构造二叉树 void PreOrderTraverse(BiThrTree T); //先序遍历二叉树（递归算法） void InOrderTraverse(BiThrTree T); //中序遍历二叉树（递归算法） void PosOrderTraverse(BiThrTree T); //后序遍历二叉树（递归算法） void PreOrder_Stack_Traverse(BiThrTree T); //先序遍历二叉树（非递归算法） void InOrder_Stack_Traverse(BiThrTree T); //中序遍历二叉树（非递归算法） Status PreOrderThreading(BiThrTree &Thrt, BiThrTree T); //先序线索化二叉树 void PreThreading(BiThrTree p); Status InOrderThreading(BiThrTree &Thrt, BiThrTree T); //中序线索化二叉树 void InThreading(BiThrTree p); void PreOrderTraverse_Thr(BiThrTree Thrt); //先序遍历线索化二叉树 void InOrderTraverse_Thr(BiThrTree Thrt);  //中序遍历线索化二叉树 void InOrder_Thr_T(BiThrTree Thrt,BiThrTree &T); //将线索化二叉树还原; 依次完成先中后遍历和先序和中序线索化 4 详细设计 首先定义二叉树的存储结构如下： typedef enum PointerTag {Link,Thread}; //Link==0:指针，Thread==1:线索 typedef struct BiThrNode {      //线索二叉树中结点的定义 char data; int LTag,RTag; struct BiThrNode *lchild,*rchild; }BiThrNode,*BiThrTree; 然后定义栈的存储结构： typedef struct { BiThrTree *base; BiThrTree *top; int stacksize; }SqStack; 其中二叉树的遍历可用递归和非递归两种算法实现，递归可根据如下算法实现： void PreOrderTraverse(BiThrTree T) //先序遍历 { if (T){ cout<<"    "<data; /*访问根结点*/ PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } 中序和后序只需改变访问次序即可；在进行进行非递归遍历时可根据栈的访问顺序依次遍历。最后线索化该二叉树也可根据递归的算法实现，其中先序线索递归实现可根据 void PreThreading(BiThrTree p) {    if (p) { if (!p->lchild) //先驱线索 { p->lchild=pre; p->LTag=Thread; }  if (!pre->rchild) { //后继线索    pre->rchild=p;    pre->RTag=Thread; }    pre = p; if(p->LTag==Link) PreThreading(p->lchild); //左子树线索化 if(p->RTag ==Link) PreThreading(p->rchild); }  //右子树线索化 } 后续也只需改变线索化顺序即可。但在中序线索化后程序会自动还原线索化再进行先序线索化。 5 程序编码 #include #include #include #include #include #define OK 1 #define FALSE 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OVERFLOW -1 typedef int Status; typedef enum PointerTag {Link,Thread}; //Link==0:指针，Thread==1:线索 typedef struct BiThrNode {      //线索二叉树中结点的定义 char data; int LTag,RTag; struct BiThrNode *lchild,*rchild; }BiThrNode,*BiThrTree; //函数声明 BiThrTree CreateBiTree(BiThrTree &T); //构造二叉树 void PreOrderTraverse(BiThrTree T); //先序遍历二叉树（递归算法） void InOrderTraverse(BiThrTree T); //中序遍历二叉树（递归算法） void PosOrderTraverse(BiThrTree T); //后序遍历二叉树（递归算法）