线索二叉树
一目的
程序从文件中读取每个结点的信息，然后建立一个二叉树。

通过菜单的形式，选择不同的线索化方式，然后再对线索化的二叉树经行遍历并输出对应的结果。

二需求分析
1、文件的读入
程序首先要从一个文件中读入结点的信息。

故需建立一个文件，在文件中，给出每个结点的信息。

2、菜单的实现
由于需要建立两种不同的线索二叉树，故需要一个菜单，来选择需要进行的操作，并输出操作的结果。

3、树的建立
从文件中，读入每个结点的信息。

然后建立起树，然后再对已建立的树进行相应的线索化。

4、树的线索化
根据菜单的选择，对已建立的树经行相对应的线索化。

5、输出遍历的结果
对每种不同的线索化的的树，给出相对应的算法。

然后，根据算法把每种遍历的结果输出。

三概要设计
1、主程序模块
(1)主程序模块
int main()
{
welcome(); //通过welcome（）模块来让用户控制，做线索化的工作。

return 0;
}
(2)可线索化单元模块—实现各种线索化的抽象数据类型；通过welcome（）模块来调用每个线索化模块。

2、建立二叉树的模块
bool CreatBinTree();
函数会根据用户输入的文件名，打开一个存储了树中每个结点的文件，且是用广义表的形式给出结点信息的文件。

操作结果：根据文件中广义表的形式，建立相对应的二叉树，该树的根节点为root。

3、线索化的抽象数据类型
void CreatInThread();
void CreatInThread(Node *current,Node *&front)
current是中序遍历下，当前遍历的结点的指针。

front是中序遍历下，current结点的前驱的指针。

操作结果：对建立的二叉树完成中序线索化。

void CreatPostThread();
void CreatPostThread(Node *current,Node *&front)
current是后续遍历下，当前遍历的结点的指针。

front是后续遍历下，current结点的前驱的指针。

操作结果：对已建立的二叉树完成后续线索化。

4、输出结果的抽象数据类型
void InOrder()
操作结果：输出中序线索二叉树的中序遍历的结果。

Node* InFirst(Node *current)
current是中序线索二叉树中指向一个结点的指针。

操作结果：返回以current为根的树的中序遍历下的第一个结点的指针。

Node* InNext(Node *current)
current是中序线索二叉树中指向一个结点的指针。

操作结果：返回中序遍历下，current结点的后继结点的指针。

void PostOrder()
操作结果：输出后续线索二叉树的后续遍历结果。

Node* PostFirst(Node *current)
current是后续线索二叉树中指向一个结点的指针。

操作结果：返回以current为根的树的后续遍历下的第一个结点的指针。

Node* PostNext(Node *current)
current是后续线索二叉树中指向一个结点的指针。

操作结果：返回后续遍历下，current结点的后继结点的指针。

四详细设计
二叉树中，每个结点的定义
struct Node
{
char ch; //每个结点的信息域
int ltag; //左孩子指针标志域
int rtag; //右孩子指针标志域
Node *left; //左孩子
Node *right; //右孩子
Node *parent; //双亲结点
};
线索二叉树的抽象数据类型
class ThreadTree //线索二叉树的抽象数据类型
{
public:
ThreadTree(); //构造函数
bool CreatBinTree(); //从文件中读取数据并建立二叉树void CreatInThread(); //对二叉树进行中序线索化
void CreatInThread(Node *current,Node *&front);
Node* InFirst(Node *current); //寻找中序下的第一个结点
Node* InNext(Node *current); //寻找中序下当前结点的后继结点void InOrder(); //对中序线索二叉树进行遍历
void CreatPostThread(); //对二叉树进行后序线索化
void CreatPostThread(Node *current,Node *&front);
Node* PostFirst(Node *current); //需找后序下的第一个结点
Node* PostNext(Node *current); //寻找后序下当前结点的后继结点void PostOrder(); //对后序线索二叉树进行遍历
void DeleteInTree(); //析构中序线索二叉树
void DeletePostTree(); //析构后续线索二叉树
private:
Node *root; };
整个流程图如下：
五调试分析
1．程序首先要解决文件的形式问题，即文件中存储树的形式，可以给出树的先序遍历序列，也可以给出树的广义表形式。

该程序中，是给出的广义表的形式。

2．改程序可以从文件中读取信息，然后把二叉树建立起来。

3．建立二叉树后，就需要对二叉树进行线索化。

这就必须知道线索二叉树的定义，才能知道对二叉树线索化的大概算法，最终把线索二叉树通过函数建立起来。

4．线索化完成后，还要对树经行遍历。

若对树经行普通的中序或后续遍历，则对改程序没有任何的意义。

所以，要充分理解线索二叉树的好处与优势，并分析出对线索二叉树遍历的比较快速的算法。

5．要完成该程序，必须对树这种数据结构有充分的理解和认识。

并且，对递归型的算法有一定的研究。

六测试结果
1．通过写改程序，让我对树型数据结构有了更进一步的认识。

2．改程序的模块化程度很高，从中体会到了模块化的好处。

在找错误的过程中，可以一个一个模块的调试，工作量大大的减少了。

3．文件中，二叉树的广义表形式为：
则对应的二叉树为：
A
B G
C D
I H
E F
J
4．程序运行的运行过程为：
以上为中序遍历结果！
以上为后续遍历结果！
七用户使用说明
1．本程序在VC和VS等环境下运行。

2．程序运行之前，先把一个二叉树对应的广义表形式存在一个文件中，并把该文件放在程序运行的工程中。

3．程序运行时，需要用户输入存储了一个二叉树结点信息的文件，若没有找到该文件，则用户可以选择继续输入文件名或退出程序。

若找到文件，则用户可以继续选择后续的操作。

每一次操作，都会对用户有相应的提示语。

运行的菜单如下：
八课程设计总结
通过这次课程设计，让我对树的概念有了一个新的认识。

在学习《离散数学》的时候，总觉得树是很抽象的东西，但是在学习了《数据结构》这门课后，我慢慢体会到了其中的奥秘。

树能够在计算机中存在，首先要扑捉他有哪些具体化，数字化的信息，比如说：结点个数。

而线索二叉树就是对树这种数据结构深入研究而产生的一种技巧性的处理。

对树的研究还远远不止，树的应用相当的广泛。

比如：平衡二叉树，赫夫曼编码等问题，堆排序也用到了二叉树的操作。

不得不让我感到树型结构的强大，也唤起了我对树形结构研究的热情。

由于树的结构在计算机中的存储结构并不是真正的跟树一样的结构，所以涉及到的许多算法，都是递归型的。

对递归算法的研究也是必不可少的。

这次课程设计虽然是结束了，但是我对编程的热爱，却又加深了。

在程序的世界里，让我能达到一种忘我的境界。

每次在编程时，我的大脑总是处于高速运转的状态，我享受那种过程；我享受每一次找到错误；我享受每一次看到预想的结果。

我的编程日子，一直继续着！
九附录
源程序文件名清单：
bintree.txt /*存放一个二叉树对应的广义表的形式*/。