线索二叉树课程设计说明书格式.doc

实用文档

中 北 大 学
课程设计说明书

学 院、系：
软件学院
专 业：
软件工程
班 级：
15140X04
学 生 姓 名：
张航
学 号：
1514040423
设 计 题 目：
线索二叉树的应用

起 迄 日 期:
2016年12月16日~2016年12月29日
指 导 教 师:
付东来

日期: 2016年12月29日

1 设计目的
《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的：
n 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；
n 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
n 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
2 任务概述
设计内容：
（1）建立线索二叉树，实现插入、删除操作。
（2）线索二叉树的遍历（本程序中使用中序遍历方法）
设计要求：
实现线索树建立、插入、删除、恢复线索
任务分析：
该任务是关于线索二叉树的运算，其中的基本运算应基于二叉树，但又有所不同，首先应了解问题有：
（1）线索二叉树如何建立：是通过二叉树来实现线索化，还是直接进行线索化的输入。若由二叉树建立而来，该二叉树应如何输入，对具体的二叉树应该使初次使用者明白使用的格式。
（2）该程序重点内容是有关二叉树的插入、删除和查找前驱后继，在进行具体操作时，该如何实现查找到相应结点，线索应该如何改变才能不破坏线索二叉树的结构。重点在于插入删除是分清楚插入删除位置的双亲结点与被插入删除的结点的孩子关系。
3 模块划分
（1）定义数据结构模块：
typedef struct BiThrNode{
ElemType data;
struct BiThrNode *lchild,*rchild;
int LTag,RTag;
}BiThrNode,*BiThrTree;
（2）功能函数：
二叉树的建立函数：void CreateBiTree(BiThrTree &T)
询二叉树深度函数：int Depth(BiThrTree T)
带头结点的二叉树中序线索化函数：void InOrderThreading(BiThrTree &Thrt,BiThrTree T)
以结点T为根的子树中序线索化：void InThreading(BiThrTree &T)
中序遍历函数：void InOrderTraverse_Thr(BiThrTree Thrt)
查找某结点函数：BiThrTree Search(BiThrTree T,ElemType key)
查找某结点函数：BiThrTree SearchPre(BiThrTree point,BiThrTree child)
插入函数：Status InsertTree(BiThrTree T)
删除函数：Status DeleteTree(BiThrTree T)
主函数：main()

整体结构图：
开 始
创建二叉树
线索化二叉树
Main( )
打印二叉树

插入结点

删除结点

4 主要函数说明及其N-S图
4.1详细设计思想
建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需添加虚结点，使其成为完全二叉树。
二叉树的中序线索化算法与中序遍历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL），而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋，而*p是*pre的后继。
结点插入算法：由线索二叉树的定义易知插入的节点定是个叶子节点，需注意线索的修改，可分为两种情况：
（1）：插入的节点t是右儿子，t的中序后继是其父亲的中序后继，中序前驱是其父亲。
（2）：插入的节点t是左儿子，t的中序前驱是其父亲的中序前驱，中序后继是其父亲。
结点删除算法：删除的情况与搜索二叉树的删除的类似
（1）：删除的节点p是叶子节点，直接删除，修改其父亲的线索。
（2）：删除的节点p有一个儿子，p有一个左儿子，以p为根的左子树中的具有最大值节点的t中序后继是p的中序后继，中序前驱不变；p有一个右儿子，以p为根的右子中的具有最小值节点t中序前驱是p的中序前驱，中序后继不变。
（3）：删除的节点p有二个儿子，转化为叶子节点或只有一个儿子节点的删除。
4.2各功能函数流程图

图4.1 ：创建二叉树

图4.2 ：查询二叉树深度

图4.3 ：中序线索化二叉树

图4.4 ：中序遍历输出二叉树

图4.5 ：查询结点

图4.6 ：查询结点的双亲结点

图4.7 ：插入结点

图4.8 ：删除结点
5 程序运行数据及其结果

1_按中序输入一课二叉树，建树并实现线索化

2_建树完成后进入主菜单，可执行相应插入、删除、打印操作

3_选择操作1，以中序遍历输出线索二叉树

4_选择操作2，在线索二叉树中插入新结点

5_选择操作3，删除二叉树中的结点

6 课程设计心得
通过这次做课程设计，发现了学习中的很多问题，平时学习的东西在做起来时有很大的困难，独立构思一个程序很难，不仅仅是要实现某个功能，而且还要把这些功能结合起来，成为一个能良好运行的程序，需要对错误输入提示，需要排除debug，需要设计每个使用界面等等。刚开始的时候是先写了一部分代码，后来就发觉应该先把函数的功能需要弄清楚，整理出一个大框架。再此基础上完善程序的功能。这次的线索二叉树的插入和删除课本上没有相应的内容，为了完成课设，在网络上一直翻看别人的博客，先看明白思想，在尽量看懂人家的代码。最后是借鉴了别人的思想，自己画图，才把代码实现出来。其间废了好大的力气。而且虽说是实现了，但函数的语句还是显得有些乱，自己为了看懂还加了一大堆注释。不便于和同学交流。一直以来，觉得自己数据结构学的还行，起码概念那些都能理解，知道说了些什么，也大致知道怎么个原理，考完试也感觉良好，但是一到课程设计，看的题目挺简单，二叉树，可是一去上手做了去无从下手，一点都不会，只会纸上谈兵，我也知道变成这东西是需要多实践的，但没想到真的坐到那儿去编时，却怎么也下不了手，于是很失落的回宿舍查阅书籍以及上网百度资料，仔细的参读了很长时间后，自己不停的磨合，终于完成个大概，不可避免调试中又出些问题，经过好几遍的查错，一点一点的改，最终终于完成现在的程序。
通过这段时间的课程设计，我认识到数据结构是一门比较难的课程，但同时有时一门基础切极为重要的课程。需要多花时间上机练习。这次的程序训练培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我适应实际，实践编程的能力。
总的来说，这次课程设计让我获益匪浅，对数据结构也有了进一步的理解和认识。

附录：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<windows.h>//windows自带函数库：Sleep()函数

#define ERROR 0
#define OK 1

typedef char ElemType;//二叉树结点数据域可随时修改数据类型
typedef int Status;

typedef struct BiThrNode{//二叉树的存储结构
ElemType data;
struct BiThrNode *lchild,*rchild;
int LTag,RTag;
}BiThrNode,*BiThrTree;//BiThrTree用来声明指针类型变量

static BiThrTree pre = (BiThrTree)malloc(sizeof(BiThrNode));

void CreateBiTree(BiThrTree &T){//前序创建
char ch;
ch = getchar();
if(ch == '#') T = NULL;
else{
T = (BiThrTree)malloc(sizeof(BiThrNode));
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}

void InThreading(BiThrTree &T){//以T为根节点的二叉树线索化
if(T){
InThreading(T->lchild);
if(!(T->lchild)){
T->LTag = 1;
T->lchild = pre;
}
else T->LTag = 0;
if(!(pre->rchild)){//pre被定义为全局变量
pre->RTag = 1;
pre->rchild = T;
}
else T->RTag = 0;
pre = T;
InThreading(T->rchild);
}
}
void InOrderThreading(BiThrTree &Thrt,BiThrTree T){//带头结点的二叉树中序线索化
Thrt = (BiThrTree)malloc(sizeof(BiThrNode));
Thrt->LTag = 0;
Thrt->RTag = 1;
Thrt->rchild = Thrt;
if(!T) Thrt->lchild = Thrt;
else{
Thrt->lchild = T;pre = Thrt;
InThreading(T);
pre->rchild = Thrt;
pre->RTag = 1;
Thrt->rchild = pre;
}
}

void InOrderTraverse_Thr(BiThrTree Thrt){//中序遍历线索二叉树
BiThrTree p = (BiThrTree)malloc(sizeof(BiThrNode));
p = Thrt->lchild;
printf("二叉树中序遍历结果为：");
while(p!=Thrt){
while(p->LTag==0) p = p->lchild;
printf(" -> %c",p->data);
while(p->RTag==1&&p->rchild!=Thrt){
p = p->rchild;printf(" -> %c",p->data);
}
p = p->rchild;
}
puts("");//回车换行
}

BiThrTree Search(BiThrTree T,ElemType key){//查找data == key 的结点 ,并返回该节点的指针地址
BiThrTree p = (BiThrTree)malloc(sizeof(BiThrNode));
p = T->lchild;
while(p!=T){
while(p->LTag==0) p = p->lchild;
if(p->data==key) return p;
while(p->RTag ==1&&p->rchild!=T){
p = p->rchild;
if(p->data==key) return p;
}
p = p->rchild;
}
return NULL;
}

BiThrTree SearchPre(BiThrTree point,BiThrTree child) // 查找以point为根，child的双亲结点
{
BiThrTree p1,p2;
if(point!=NULL)
{
if((point->LTag!=1&&point->lchild==child)||(point->RTag!=1&&point->rchild==child))
return point;//找到则返回
else
if(point->LTag!=1)
{
p1=SearchPre(point->lchild,child);
if(p1!=NULL) return p1;
}
if(point->RTag!=1)
{
p2=SearchPre(point->rchild,child);
if(p2!=NULL) return p2;
}
return NULL;
}
else return NULL;
}

Status InsertTree(BiThrTree T){//线索二叉树的插入函数
BiThrTree p = (BiThrTree)malloc(sizeof(BiThrNode));//新结点，要插入的结点
BiThrTree t ;//要插入结点的父母结点
ElemType key;
int n = 1,temp = 0;
while(temp==0){
n = 1;t = NULL;
InOrderTraverse_Thr(T);//遍历输出线索二叉树
printf("请输入新结点的值：");
scanf("%c",&(p->data));getchar();
printf("请问新结点的父母结点为：");
scanf("%c",&key);getchar();
printf("请问新结点是%c结点的左孩子or右孩子：(0-左,1-右)",key);
while(1){//循环执行
scanf("%d",&n);getchar();
if(n==0||n==1) break;
puts("输入的值应为0或1，请重新输入！");
}
t = Search(T,key);
if(!t) puts("输入的父母结点不存在于树中，查找失败！");
else{
if(n == 0){//插入左子树
p->RTag = 1;
p->rchild = t;//父母结点的前驱
p->LTag = t->LTag;
p->lchild = t->lchild;
t->LTag = 0;
t->lchild = p;
t = p;
if(p->LTag==0){//找到p的左子树的最右结点，改为自己前驱
p = p->lchild;
while(p->RTag == 0)
p = p->rchild;
p->rchild = t;
}
}else{ //插入右子树
p->LTag = 1;
p->lchild = t;
p->RTag = t->RTag;
p->rchild = t->rchild;
t->RTag = 0;
t->rchild = p;
t = p;
if(p->RTag==0){
p = p->rchild;
while(p->LTag == 0)
p = p->lchild;
p->lchild = t;
}
}
}
printf("继续 插入结点请按 —0 返回主界面 —请按1：");
while(1){
scanf("%d",&temp);getchar();
if(temp == 1) break;
else if(temp == 0) break;
else puts("输入错误，应输入0-继续插入 1-主界面：");
}
}
return OK;
}

Status DeleteTree(BiThrTree T){//线索二叉树的删除函数
BiThrTree t,pre,save;//pre_待删结点的双亲，屏蔽了全局变量pre save_保留要删除的结点，用以free(save);
ElemType key;
int n = -1,temp = 0;//temp 用来判断是否循环，继续使用删除结点函数
while(temp == 0){
InOrderTraverse_Thr(T);//遍历输出
printf("请输入要删除的结点：");
scanf("%c",&key);getchar();
t = Search(T,key);//在头结点为T的树中找到key结点的位置
if(!t) puts("所要删除的结点不存在！！");
else{
pre = SearchPre(T,t);
save = t;
if(t->LTag==1&&t->RTag==1){//要删除的结点没有孩子
if(pre->lchild==t){pre->LTag = t->LTag;pre->lchild = t->lchild;}
else if(pre->rchild==t){pre->RTag = t->RTag;pre->rchild = t->rchild;}
else puts("查找双亲结点可能有误1");
}else if(t->LTag==1&&t->RTag==0){//要删除的结点仅有右孩子
if(pre->lchild==t){//被删结点是双亲的左孩子
pre->lchild = t->rchild;
pre = t;
t = t->rchild;
while(t->LTag==0) t = t->lchild;
t->lchild = pre->lchild;
}else if(pre->rchild==t){//被删结点是双亲的右结点
pre->rchild = t->rchild;
t = t->rchild;
while(t->LTag==0) t = t->lchild;
t->lchild = pre;
}else puts("查找双亲结点可能有误2");
}else if(t->LTag==0&&t->RTag==1){//要删除的结点仅有左孩子
if(pre->lchild==t){//被删结点是双亲的左孩子
pre->lchild = t->lchild;
pre = t;
pre = pre->lchild;//修改pre为待删结点的左孩子
while(pre->RTag==0) pre = pre->rchild;
pre->rchild = t->rchild;
}else if(pre->rchild==t){//被删结点是双亲的右孩子
pre->rchild = t->lchild;
pre = t;
pre = pre->lchild;
while(pre->RTag) pre = pre->rchild;
pre->rchild = t->rchild;
}else puts("查找双亲结点可能有误3");
}else{//要删除的结点有两个孩子
if(pre->lchild==t){
pre->lchild = t->lchild;//被删除结点的左树作为根节点
pre = t->lchild;//开始查找t的前驱
while(pre->RTag==0) pre = pre->rchild;
pre->RTag = 0;
pre->rchild = t->rchild;
t = t->rchild;//开始查找t的后继
while(t->LTag==0) t = t->lchild;
t->LTag = 1;
t->lchild = pre;
}else if(pre->rchild==t){
pre->rchild = t->lchild;
pre = t->lchild;//开始查找t的前驱
while(pre->RTag==0) pre = pre->rchild;
pre->RTag = 0;
pre->rchild = t->rchild;
t = t->rchild;//开始查找t的后继
while(t->LTag==0) t = t->lchild;
t->LTag = 1;
t->lchild = pre;
}else puts("查找双亲结点可能有误4");
}
free(save);
}
printf("继续删除结点 —请按 0 返回主界面 —请按1：");
while(1){
scanf("%d",&temp);getchar();
if(temp == 1) break;
else if(temp == 0) break;
else puts("输入错误，应输入0-继续插入 1-主界面：");
}
}
return OK;
}

main(){
BiThrTree T = NULL;
pre->rchild = NULL;//初始化pre
BiThrTree Thrt;
int Temp = -1;

puts("请输入字符串以建立二叉树，输入 # 表示空树。例:AB##C##");
CreateBiTree(T);getchar();
puts("正在建立二叉树......."); Sleep(1000);
InOrderThreading(Thrt,T);//线索化
puts("正在线索化二叉树....."); Sleep(1000);
printf("线索二叉树已经建好，接下来请进入菜单使用程序。\n");Sleep(500);
system("pause");
while(1){
system("cls");
puts("\n\n\n");
printf("\t\t****************主菜单*****************\n");
printf("\t\t* 打印二叉树请按 - 1 *\n");
printf("\t\t* 插入结点请按 - - 2 *\n");
printf("\t\t* 删除结点请按 - - 3 *\n");
printf("\t\t* 退出程序请按 - - 0 *\n");
printf("\t\t***************************************\n");
printf("\n 请输入要执行的操作：");
scanf("%d",&Temp);getchar();
switch(Temp){
case 1:InOrderTraverse_Thr(Thrt);break;
case 2:InsertTree(Thrt);break; //遍历输出
case 3:DeleteTree(Thrt);break;
case 0:puts("感谢您的使用。");exit(1);
default : puts("错误！您应输入 0 —3 的数字");
}
getchar();
}
system("pause");
}