数据结构课程设计-线索二叉树.docVIP

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称 数据结构 课题名称 线索二叉树 专业 计算机科学与技术 班级 10计本2班 学号10012082姓名 联系方式 指导教师20 11 年 12 月 27 日目 录1、数据结构课程设计任务书1.1、题目1.2、要求2、总体设计2.1、功能模块设计2.2、所有功能模块的流程图3、详细设计3.1、程序中所采用的数据结构及存储结构的说明3.2、算法的设计思想3.3、线索二叉树的基本操作4、调试与测试：4.1、调试方法与步骤：4.2、测试结果的分析与讨论：4.3、测试过程中遇到的主要问题及采取的解决措施：5、时间复杂度的分析：6、源程序清单和执行结果7、c程序设计总结8、致谢9、参考文献1、数据结构课程设计任务书1.1、题目线索二叉树1.2、要求（1）建立中序线索二叉树,并且遍历（2）求中序线索二叉树上已知结点中序的前驱和后继（3）插入节点到指定位置,试着删除指定结点2、总体设计2.1、功能模块设计根据课程设计题目的功能要求，各个功能模块的组成框图如下：lchildltagdatartagrchild其中: ltag= o, lchild域指示结点的左孩子 1， lchild域指示结点的前驱 rtag= 0， rchild域指示结点的右孩子 1， lchild域指示结点的后继2.2、所有功能模块的流程图3、详细设计模块功能说明：如函数功能、入口及出口参数说明，函数调用关系描述等；开始输出主菜单的选择界面输入choice的值choice=?1.中序线索化输出中序遍历结果3退出程序2后序线索化输出后续遍历结果 结束3.1、程序中所采用的数据结构及存储结构的说明在某程序中所用二叉树需经常遍历或查找结点在遍历所得线性序列中的前驱和后继，则应采用线索链表作存储结构。/-二叉树的二叉线索存储表示-/二叉树的二叉线索存储表示#include#includetypedef enum pointertagpointertype;/link=0,指针,thread=1,线索typedef char telemtype;typedef struct bithrnode telemtype data; struct bithrnode *lchild,*rchild; /左右孩子指针 pointertype ltag,rtag; /左右标志bithrnode,*bithrtree;bithrtree pre; /前驱指针void createbithrtree(bithrtree *t)/建树 char ch; scanf(%c,&ch); fflush(stdin); if(ch= ) else if(!(*t=(bithrtree)malloc(sizeof(bithrnode) exit(exit_failure); (*t)-data = ch; (*t)-lchild = (*t)-rchild = null; (*t)-ltag = (*t)-rtag = link; createbithrtree(&(*t)-lchild); createbithrtree(&(*t)-rchild); void inthreading(bithrtree t) /建立线索 if(t) inthreading(t-lchild); /左子树线索化 if(!t-lchild)/前驱线索 t-ltag = thread; t-lchild = pre; if(!pre-rchild)/后继线索 pre-rtag = thread; pre-rchild = t; pre = t; inthreading(t-rchild); void inorderthreading(bithrtree *thrt,bithrtree t)/建立线索头结点 /中序遍历二叉树t，并将其中序线索化，thrt指向头结点。 if(!(*thrt=(bithrtree)malloc(sizeof(bithrnode) exit(1); (*thrt)-ltag = link; /建立头结点 (*thrt)-rtag = thread; (*thrt)-rchild = *thrt; /右指针回指 if(!t) (*thrt)-lchild = *thrt; /若二叉树空,左指针也回指 else (*thrt)-lchild = t; pre = *thrt; inthreading(t); /进行中序线索化 pre-rchild = *thrt; pre-rtag = thread; /最后一个结点线索化 (*thrt)-rchild = pre; void inordertraverse_thr(bithrtree t)/线索化中序遍历 /t指向头结点，头结点左链lchild指向根结点。 bithrtree p; p = t-lchild; /p指向根结点 while(p!=t) /空树或遍历结束时，p=t while(p-ltag=link) p = p-lchild; /左子树为空时访问 printf(%c ,p-data); while(p-rtag=thread & p-rchild!=t) p = p-rchild; printf(%c ,p-data); /访问后继结点 p = p-rchild; int main(void) bithrtree tree,treehead; createbithrtree(&tree); inorderthreading(&treehead,tree); printf(ninordertraverse:n); inordertraverse_thr(treehead); return 0; 3.2、算法的设计思想a）构建建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一颗二叉树。在遍历过程中，访问结点的草所是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。另外，在对一颗二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的跟结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。b）遍历以中序为例，利用在中序线索二叉树上需找后续结点和前驱结点的算法，就可以遍历到二叉树的所有结点，即先找到按某序遍历的一个结点，然后再一次查询其后续；或先找到按某序遍历的最后一个结点，然后再一次查询其前驱。这样，既不用栈也不用递归就可以访问但二叉树的所有结点。4、调试与测试：4.1、调试方法与步骤：1程序首先要解决文件的形式问题，即文件中存储树的形式，可以给出树的先序遍历序列，也可以给出树的广义表形式。该程序中，是给出的广义表的形式。2改程序可以从文件中读取信息，然后把二叉树建立起来。3建立二叉树后，就需要对二叉树进行线索化。这就必须知道线索二叉树的定义，才能知道对二叉树线索化的大概算法，最终把线索二叉树通过函数建立起来。4线索化完成后，还要对树经行遍历。若对树经行普通的中序或后续遍历，则对改程序没有任何的意义。所以，要充分理解线索二叉树的好处与优势，并分析出对线索二叉树遍历的比较快速的算法。5要完成该程序，必须对树这种数据结构有充分的理解和认识。并且，对递归型的算法有一定的研究。4.2、测试结果的分析与讨论： 4程序运行的运行过程为： 以上为中序遍历结果！以上为后续遍历结果！5、时间复杂度的分析：在递归过程中对每个结点做仅做一次访问，所以对于n个结点的二叉树，线索化的算法时间复杂度为o(n)。6、源程序清单和执行结果struct nodechar 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(); /析构后续线索二叉树7、c程序设计总结在这次设计过程中，不仅复习课本上所学知识，还通过查资料、问同学学到了课本上没有的知识。从而启发我，要想写好程序，在写好课本知识的同时还需要多读和专业有关的一些书籍，同时还需要多动脑子，尽量把所学的知识综合起来应用，力争写出完美的程序。除此之外，我还得到了一些有用的教训：写程序时必须要细心，不能输错一个字符标点，就连全角半角也得注意。在修改时要有耐心，编译出错