线索二叉树课程设计说明书-模板

2021年1月25日发(作者：副部级)













数学与计算机学院

课程设计说明书


课

程

名

称
:


数据结构与算法课程设计


课

程

代

码
:



















题







目
:






线索二叉树的应用




年级
/
专业
/
班
:




2010
级软件
1
班







学

生

姓

名
:


























学





号
:



1127







开

始

时

间
:


2011


年


12


月

9



日

完

成

时

间
:


2011


年


12


月

23


日

课程设计成绩：

1


学习态度及平
技术水平与实际
创新（
5
）

时成绩（
30
）

能力（
20
）


说明书（计算书、图纸、分
析报告）撰写质量（
45
）

总

分
（
100
）






指导教师签名：

















年



月



日


摘



要

首 先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给
出测试数据。其次是概要设计， 说明所有抽象数据类型的定义、主程序的流程以
及各程序模块之间的层次关系，以及
ADT描述。然后是详细设计，描述实现概要
设计中定义的基本功操作和所有数据类型，以及函数的功能及 代码实现。再次是
对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说
明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。

关键词：
线索化；先序遍历；中序遍历；后续遍历


































线索二叉树的运用


引

言

数据结构是计算机专业重要的专业基础课程与核心课程之一，
在计算机领域应用广
泛，计算 机离不开数据结构。数据结构课程设计为了能使我们掌握所学习的知识并有应
用到实际的设计中的能力， 对于掌握这门课程的学习方法有极大的意义。本课程设计的
题目为“线索二叉树的应用”
，完成 将二叉树转化成线索二叉树，采用前序、中序或后
序线索二叉树的操作。本课程设计采用的编程环境为< br>Microsoft Visual Stdio 2008
。

目

录


1
需求分析

............. ........................................
3

2
开发及运行平台

......................... ......................
4

3
概要设计

.
............................ ........................
5

4
详细设计

.
............................ ........................
7

5
调试分析

.
............................ .......................
1
2

6
测试结果

.
............................ .......................
1
3

7
结论

.
.............................. .........................
1
8

致

谢

.
............................... ........................
1
9

参考文献

.
............................ .........................
2
0

附

录

.
............................... .......................
2
1


1
、需求分析



为了能更熟练精准的掌握二叉树的各种算 法和操作，同时也为了开拓视野，综合
运用所学的知识。为此，需要将二叉树转化成线索二叉树，采用前 序、中序或后序线索
二叉树，以实现线索树建立、插入、删除、恢复线索等。

1.1
任务与分析

中次系统要实现对二叉树的建立，
以及线索化 该二叉树，
同时实现对其先序、
中序、
后序线索话的并输出结果。

1.2
测试数据

表
1
：入的二叉树结点序号和数据

结点序号

1
2
3
4
5
6
数据

11
22
33
44
55
66
7
8
9
77
88
99

































线索二叉树的运用

2
开发及运行平台

开发平台：
Microsoft Visual Studio 2008
运行平台：
Windows XP/2003/7
- 3 -

3
概要设计


3.1 ADT
描述


ADT BiTree{

数据对象：
D={
“树节点”
}
；


数据关系：
R
＝
{H}

若
D=
∮为 空，则
R=
∮
,Tree
为空树；


若
D
仅有一个数据元素，则
R=
∮；


否则
R={H}
详细描述如下：

D
中存在唯一的称之为根 的节点
root
，它在关系
H
下无前驱；

1.

若
D-{root}
≠
∮
，
则
存
在
对
根
以
外
剩
余
元
素
的
一
个
划
分
D1
、

D2......
，
Dm
（
m>0
）
，并对任意
j
≠
k< br>（
1
≦
j
≦
m
，
1
≦
k< br>≦
m
）有
Dj
∩
Dk=
∮；且对任意
i（
1
≦
i
≦
m
）唯一存在数据元素
xi
∈
Di
，有二元关系

∈
H
。这里描述 的是从总节点到各个子树根节点
xi
的边。

2.

对应
于
D-{root}
的
划
分
，
关
系
集
H-{
，


，
......}
也有唯一的划分
H1
、
H2......Hm(m>0)
，
并且对任意的
j
≠
k
（
1
≦
j
≦
m
，
1
≦
k
≦
m
）有
Hj
∩
Hk=
∮，对任意的
i
（
1
≦
i
≦
m
）
，
Hi
是
Di
上的二元关系，则（
Di
，
{H}
）是一颗树，且是
r oot
的子树。


基本操作：

void creat ();//
创建一个二叉树。

void inorder ();//
中序便利。

void ThTree::threpreorder ();//
先序遍历二叉树。

void ThTree::threinorder ();//
中序遍历二叉树。

void ThTree::threpostorder ();//
后序遍历二叉树。

void ThTree::destroy ();//
删除线索二叉树。

int main();//
主函数。

}


































线索二叉树的运用

3.2
程序模块结构

< br>菜单
新建
中序递归线索
化
先序递归线
索化
后序递归线
索化




























图
2
程序模块结构

3.2.1

结构体定义

书的结构体定义如下：

struct ThreNode //
定义结点结构体

{

ElemType data;
ThreNode *lch;

ThreNode *rch;

int ltag,rtag;
};
3.3
各功能模块

新建模块
:

void ThTree::creat ()
新建二叉树并储存。

树类模块
:void ThTree ()
定义书的结点，孩子以及各成员函数。

先序遍历模块
:

void ThTree::threpreorder ()
对树进行先序线索遍历。

中序遍历模块
:

void ThTree::threinorder ()
对树进行中序线索遍历。

后序遍历模块
:

void ThTree::threpostorder()
对树进行后序线索遍历。

删除模块
:

void ThTree::destroy ()
：删除所有节点。

- 5 -

4
详细设计

4.1
结构体定义

树的结构体定义如下：

struct ThreNode //
定义结点结构体

{

ThreType data;
ThreNode *lch;

ThreNode *rch;

int ltag,rtag;
};
4.2
初始化

构造函数初始化变量，定义双亲结点和左右标志域以及根结点：

void ThTree::creat() //
建立二叉树

{















ThreNode *q,*s[20]; ElemType x; int i,j;
cout<<
请按二叉树的层序自上而下自左至右顺序组织数据

cout<<
每次输入结点的序号和数据，假设根结点值是
11
；

cout<<
那么输入应该是：
1 11
cout<<
cin>>i>>x;
while(i!=0&&x!=0)
{







q=new ThreNode; //
产生一个接点

q->data=x;q->lch=NULL;q->rch=NULL;
q->ltag=0;q->rtag=0; //
左右标志域

s[i]=q;
if(i==1)root=q; //q
为根接点

else{j=i/2;
if((i%2)==0)s[j]->lch=q;else s[j]->rch=q; //j
为双亲结点编号


































线索二叉树的运用





}
cout<<
}
}
4.3
新建操作

void ThTree::creat() //
建立二叉树

{

















ThreNode *q,*s[20]; ElemType x; int i,j;
cout<<
请按二叉树的层序自上而下自左至右顺序组织数据

c out<<
每次输入结点的序号和数据，假设根结点值是
11
；

co ut<<
那么输入应该是：
1 11
cout<<
cin>>i>>x;
while(i!=0&&x!=0)
{









q=new ThreNode; //
产生一个接点

q->data=x;q->lch=NULL;q->rch=NULL;
q->ltag=0;q->rtag=0; //
左右标志域

s[i]=q;
if(i==1)root=q; //q
为根接点

else{j=i/2;
if((i%2)==0)s[j]->lch=q;else s[j]->rch=q; //j
为双亲结点编号

}
cout<<
}
}
void ThTree::threpreorder(ThreNode *p,ThreNode *pre) //
先根线索化二叉树

{if(p!=NULL)
{cout<data<<
if(p->lch==NULL){p->lch=pre;
- 7 -

p->ltag=1;

}

pre=p;

if(p->ltag==0)threpreorder(p->lch,pre);

threpreorder(p->rch,pre);


4.4
、录入信息

int main ()
{









}
int k;ThTree root0;
do{cout<<
cout<<














1.
建立二叉树

cout<<














2.
中序递归线索二叉树

cout<<














3.
先序线索化二叉树


cout<<














4.
后续线索化二叉树

cout<<














5.
结束程序运行

cout<<














请输入您的选择
:
switch(k)
4.5
先序遍历线索化操作

void ThTree::threpreorder(ThreNode *p,ThreNode *pre)




//
先根线索化二叉树

{if(p!=NULL)
{cout<data<<





if(p->lch==NULL){p->lch=pre;











p->ltag=1;


}








pre=p;


}
}

if(p->ltag==0)threpreorder(p->lch,pre);

threpreorder(p->rch,pre);