数据结构课程设计题目: 线索二叉树的生成及其遍历学院：班级：学生姓名：学生学号：指导教师：2012 年12月5日课程设计任务书摘要针对以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程中才能得到。
增设两个指针分别指示其前驱和后继，但会使得结构的存储密度降低；并且利用结点的空链域存放（线索链表），方便。
同时为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针 p 指向当前访问的结点，则 pre指向它的前驱。
由此得到中序遍历建立中序线索化链表的算法本文通过建立二叉树，实现二叉树的中序线索化并实现中序线索二叉树的遍历。
实现对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的遍历的效果。
关键词二叉树，中序线索二叉树，中序线索二叉树的遍历目录摘要 ............................................. 错误!未定义书签。
第一章,需求分析.................................. 错误!未定义书签。
第二章,概要设计.. (1)第三章,详细设计 (2)第四章,调试分析 (5)第五章,用户使用说明 (5)第六章,测试结果 (5)第七章,绪论 (6)第八章,附录参考文献 (7)线索二叉树的生成及其遍历第一章需求分析以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程中才能得到。
增设两个指针分别指示其前驱和后继，但会使得结构的存储密度降低；并且利用结点的空链域存放（线索链表），方便。
同时为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针 p 指向当前访问的结点，则 pre指向它的前驱。
由此得到中序遍历建立中序线索化链表的算法本文通过建立二叉树，实现二叉树的中序线索化并实现中序线索二叉树的遍历。
实现对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的遍历的效果。
主要任务：1.建立二叉树；2.将二叉树进行中序线索化；3.编写程序，运行并修改；4.利用中序线索遍历二叉树5.书写课程设计论文并将所编写的程序完善。
第二章概要设计下面是建立中序二叉树的递归算法，其中pre为全局变量。
BiThrNodeType *pre;BiThrTree InOrderThr(BiThrTree T){ /*中序遍历二叉树T，并将其中序线索化，pre为全局变量*/BiThrTree head;head=(BitThrNodeType *)malloc（sizeof（BiThrType））;/*设申请头结点成功*/head->ltag=0;head->rtag=1;/*建立头结点*/head->rchild=head;/*右指针回指*/if(！T)head->lchild=head;/*若二叉树为空，则左指针回指*/else{head->lchild=T;pre=head;InThreading(T);/*中序遍历进行中序线索化*/pre->rchild=head;pre->rtag=1;/*最后一个结点线索化*/head->rchild=pre;};return head;}void InThreading(BiThrTree p){/*通过中序遍历进行中序线索化*/if(p){InThreading(p->lchild);/*左子树线索化*/if(p->lchild==NULL)/*前驱线索*/{p->ltag=1;p->lchild=pre;}if(p->rchild==NULL)p->rtag=1;/*后驱线索*/if(pre!=NULL && pre->rtag==1) pre->rchild=p;pre=p;InThreading(p->rchild);/*右子树线索化*/}}进行中序线索化的算法：bithptr*pre; /* 全程变量*/voidINTHREAD(bithptr *p){if(p!=NULL){ INTHREAD(p->lchild); /* 左子树线索化*/if(p->lchild==NULL) {p->ltag=1;p->lchild=pre;}if(p->rchild==NULL) p->rtag=1;if(pre!=NULL && pre->rtag==1)pre->rchild=p;pre=p; /* 前驱指向当前结点*/INTHREAD(p->rchild); /* 右子树线索化*/}第三章详细设计#include <stdio.h>#include <malloc.h>typedef enum{Link,Thread} PointerTag; //指针标志typedef int DataType;typedef struct BiThreTree{ //定义结点元素PointerTag LTag,RTag;DataType data;struct BiThreTree *lchild,*rchild;}BiThreTree;BiThreTree *pre; //全局变量，用于二叉树的线索化BiThreTree *CreateTree() //按前序输入建立二叉树{BiThreTree *T;DataType e;scanf("%d",&e);if(e==0)T=NULL;else{T=(BiThreTree *)malloc(sizeof(BiThreTree));T->data=e;T->LTag=Link; //初始化时指针标志均为Link T->RTag=Link;T->lchild=CreateTree();T->rchild=CreateTree();}return T;}void InThread(BiThreTree *T){BiThreTree *p;p=T;if(p){InThread(p->lchild);if(!p->lchild){ p->LTag=Thread;p->lchild=pre;}if(!pre->rchild){ pre->RTag=Thread;pre->rchild=p;}pre=p;InThread(p->rchild);}}BiThreTree *InOrderThrTree(BiThreTree *T) //中序线索化二叉树{BiThreTree *Thre; //Thre为头结点的指针 Thre=(BiThreTree *)malloc(sizeof(BiThreTree));Thre->lchild=T;Thre->rchild=Thre;pre=Thre;InThread(T);pre->RTag=Thread;pre->rchild=Thre;Thre->rchild=pre;return Thre;}void InThrTravel(BiThreTree *Thre) //中序遍历二叉树{BiThreTree *p;p=Thre->lchild;while(p!=Thre) //指针回指向头结点时结束{while(p->LTag==Link)p=p->lchild;printf("%4d",p->data);while(p->RTag==Thread&&p->rchild!=Thre){p=p->rchild;printf("%4d",p->data);}p=p->rchild;}}int main(){BiThreTree *T,*Thre;T=CreateTree();Thre=InOrderThrTree(T);InThrTravel(Thre);system("pause");}第四章调试分析该程序在调试过程中遇到的问题是：对已学知识运用能力欠缺，尤其是在编程方面，由于C语言等计算机基础课程知识没有很好的掌握同时在学习数据结构时也没有真正弄懂导致编程时小错误不断，而且在遇到许多小的错误时靠自己很难再调整过来，但整体上是一次对所学知识的运用巩固，特别是对二叉树的建立以及对它进行线索方面，翻阅大量的书籍及搜集资料并求教于计算机系的同学，才找到一些解决问题的方法，在用中序遍历线索二叉树时总是搞混不过也因此让我对前序，中序，后序遍历更加理解。
同时，在经历了很多次修改重写课程设计报告的悲惨经历后，懂得了很多关于办公软件方面的知识尤其是自己做的东西一定要保存并备份。
第五章用户使用说明使用该程序时在打开程序的主界面后，输入相应要求的输入形式，然后就输出中序遍历，方便简洁。
例如：运行时，分别输入（前序输入）：1 2 3 0 0 4 0 5 0 0 6 0 0建立如下所示的二叉树：12 63 45中序遍历输出：3 2 4 5 1 6第六章测试结果运行时，分别输入（前序输入）：1 2 3 0 0 4 0 5 0 0 6 0 0建立如下所示的二叉树：12 63 45中序遍历输出：3 2 4 5 1 6第七章结论在这次的课程设计中，我明白了理论和实际还是相差很大的，理论知识能学明白单不代表程序就能编出来，大多数情况下，我们还是不具备完成这项项目的能力的。
它需要我们不仅能够将以前学过的知识与现学的知识融会贯通同时还要求我们学会怎样如何整合做项目所需要的全部知识以及对为学知识的查询及自学能力。
更重要的时她还要求我们敢于实践勤于动手，遇到有些不会处理的，我会上网去查，或者去问老师，或者去问同学。
例如以前我对二叉树的相关内容并不是很熟悉，但经过这次课程设计后现在我不仅掌握了它们的使用方法，更重要的是我学会了如何去学习，然后快速地应用到我所需要的项目当中。
同时我还得到了很多关于本门课程的体会：在编写程序的过程中，把整个系统的框架准确的描述出来是非常重要的而且写程序是需要步步为营不然一不小心就会出错。
我们的C语言老师曾经说过良好的代码风格是成功的一半。
例如在写代码时会有大量的小括号，大括号等，老师曾说这些代码在书写时一定要同时写一对，这样就可以避免丢掉或忘写其中的一个。