线索二叉树算法的实现数据结构课程设计
设计说明书
线索二叉树算法的实现
学号
班级
成绩
指导教师
计算机科学与技术系
2011 年3月4日
数据结构课程设计评阅书
题 目
线索二叉树算法的实现
学生姓名
学号
指导教师评语及成绩
成绩: 教师签名: 年 月 日
答辩教师评语及成绩
成绩: 教师签名: 年 月 日
教研室意见
总成绩: 室主任签名: 年 月 日
...
数据结构课程设计
设计
线索二叉树算法的实现
学号
班级
成绩
指导教师
计算机科学与技术系
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); //后序遍历二叉树(递归算法)
本文档为【线索二叉树算法的实现】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。