线索二叉树的运算-数据结构与算法课程设计报告(共25页).doc

精选优质文档-倾情为你奉上信息科学与技术学院数据结构课程设计报告题目名称： 线索二叉树的计算 学生姓名： 刘 少 博 学 号: * 专业班级： 计算机科学与技术 指导教师： 高 攀 2014年 1月 8 一、问题分析和任务定义（1）题目：线索二叉树运算:线索二叉树的应用，实现线索二叉树的建立、插入、删除、恢复线索。（2）任务定义： 此题目是线索二叉树的一系列操作问题。首先就要明白线索二叉树是什么，利用二叉链表的空指针域将空的左孩子指针域改为指向其前驱，空的右孩子指针域改为指向其后继，这种改变指向的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。（3）分析:该任务是关于线索二叉树的运算，其中的基本运算应基于二叉树，但又有所不同，首先应解决的问题有：1，线索二叉树是如何建立的，是通过二叉树来实现线索化，还是直接进行线索化的输入。若由二叉树建立而来，该二叉树应如何输入，对于具体的二叉树应该使初使用者明白输入的格式。2，该程序重点内容是有关于线索二叉树的插入和删除，在进行具体的操作时，规则是什么，依照什么原则。3，在线索恢复中，依照插入删除后的二叉树结构，应该如何设计，是单独恢复，还是在两个重点程序中直接恢复线索。4，对于插入，删除，恢复线索等，其结果是否符合预定的目标，须由自己判定。由此，可以给出初步的分析： A。依照书上的相关内容和二叉树的定义，线索二叉树应该是在二叉树依照一定格式输入完毕后，对其进行线索化，线索化初步选定为中序线索化，然后线索化的结果进行输出。B、插入中，首先就要考虑要怎样在二叉树中插入结点。要插入结点，那么首先就应该考虑要在那里插入结点，那么就引入了结点的查找问题。结点的查找将建立一个独立的子函数。找到了结点的位置以后，由于目标节点有左右子树，设计两种情况，选择后就要考虑怎么插入了。若选择了左子树后，目标节点又有两种情况：一是已经有左子树，二是没有左子树，此时根据相应的情况，设计正确的操作。 在删除中也有类似的操作，不同的是在删除的过程中，因为要考虑被删除结点的左右子树的连接问题，必须知道要查找结点的父亲结点。那么就需要另外一个子函数来查找孩子结点的父亲结点。被删除结点和其父亲结点确定以后，就要考虑删除过程中的各种情况。C、恢复线索过程中，由于和插入删除操作分离后考虑的过程复杂，并且从设计的目标来说应该是要在删除和插入的过程中实现对线索的恢复，故选择了插入删除中直接恢复线索。D、在输出中，输出的操作分为两个一是专门用于二叉树的输出判别是否是要线索化的二叉树，此时用中序输出来体现二叉树的结点情况。二是以输出线索来观察在各种操作的过程中线索的变化情况。（4）测试用例： 其中为虚节点，#为结束标记：1.输入数据：abcd# 完全二叉树 插入结点为信息为 t； 插入的位置在点：c 删除结点为 t； 插入删除完成后得： 线索输出得：b->d->a->c-> 2.输入数据：abcdef# 插入结点为r ; 插入的位置在b点，没有左孩子的情况 删除结点为 d; 插入删除完成后得： 线索输出得：b->r->a->c-> 二、数据结构的选择和概要设计（1）数据结构的选择：因为此程序就是对二叉树进行各种操作，所以程序中必然使用的是树形结构。在将树存储到计算机中时，就有了为存树而使用的存储结构。因为对线索有大量的操作，所以选择链接存储结构。在存储的过程中还使用了队类型的数据结构。队的定义为：BItree *Qmaxlen; /存放建树过程中的每个结点的指针树的结点类型定义为： Typedef struct node Int ltag , rtag; /用来指示指针域指的为孩子还是前驱或后继 char data; /存放结点信息 struct node *lchild , *rchild; /记录孩子结点信息 Bithptr;结构图如图1为：ltag data rtaglchild rchild 图1结构图二叉树的存储结构如图2:图2二叉树的存储结构（1） 数据选择原因：要存储树在计算机中，为了使用链接存储结构，就要对结点进行设计。要存储结点信息就要有data域来存储信息，并分别设有左右孩子指针域分别记录此结点的左右孩子指针，使在建树的过程中每个结点的左右孩子指针指向其左右孩子，实现整个二叉树的建立。这样的存储结构对于二叉树的存储已经足够，但是此程序处理的是线索二叉树。在存储上就要为结点加上标志域，分别用来指示其指针是指向孩子还是前驱或后继。当tag标志为0时，表示指针指向的是该结点的左右孩子，当tag标志为1时，表示指向的是该结点的前驱或后继。（2） 概要设计：在程序中设计有完成各种功能的函数。二叉树的建立函数：BiThrNode *creat(BiThrNode *T)中序遍历函数： void inorder(BiThrNode *T)中序线索化函数： void PreThread(BiThrNode *root)输出线索函数： void Inorder(BiThrNode *T)查找孩子指针函数：BiThrNode *SearchChild(BiThrNode *T,char key_name)查找父亲指针函数：BiThrNode *SearchPre(BiThrNode *T,BiThrNode *key)插入函数： void Insert(BiThrNode *root)删除函数： BiThrNode *Delete(BiThrNode *t)主函数： void main(); （4）主要算法和结构流程图：程序的模块结构如图3插入函数查找孩子指针函数查找父亲指针函数二叉树的建立函数中序遍历函数中序线索化函数删除函数输出线索函数退出 结束输出头指针图4：开始建队并置空 、输入结点数据 判断是否为结束 Y输出头指针 N 判断是否为空 N Y建立结点结束 加入队中 是否为头结点 Y N节点是否为空 Y连接给对头 N将节点给左右子树 是否为右孩子 N队头指针加一 Y 图4树的建立函数如图 是否找到此点查找插入点结点指针插入函数流程图如图 5：开始输入要插入点信息 查找插入点结点指针结点是否有左子树结点 Y1 Y2 直接插入为此结点的右结点恢复线索1直接插入为此结点的左结点恢复线索2结束图5插入函数流程图如图专心-专注-专业输入删除结点信息开始删除函数流程图如图6查找结点信息查找父亲结点 是否为父结点左孩子 Y N左右孩子都有有左孩子没右孩子有右孩子没左孩子没有左右孩 把右子树接到左子树的最右下结点的右子树左右孩子都有有左孩子没右孩子没有左右孩子有右孩子没左孩子把左孩子作为头结点把右孩子作为头结点直接删除结点右子树接为左子树的最右下结点的右子树把左孩子作为父结点左孩子直接删除把右孩子作为父结点左孩子 恢复线索结束图6删除函数流程图三、详细设计和编码(1) 创建二叉树：1、分析：建立一个二叉链表，需要按照某种顺序依次输入二叉树中的结点，且该输入顺序必须隐含结点间的逻辑结构的信息。这个建立依照层次关系由上往下，由左往右 。以表示空结点，以#表示结束的标志 。2、实现：在函数中设置一队列，该队列是一个指针类型的数组，保存已输入的结点的地址。使队头指针front指向当前需要与孩子建立链接的父亲结点，队尾指针rear指向当前输入的结点。若rear为偶数，则该结点为父结点的左孩子，若rear为奇数，则为父结点的右孩子。若父结点或孩子结点为虚结点，则无需链接。若父结点与其两个孩子结点链接完毕，则使front指向下一个等待链接的父结点。4、主要过程： BiThrNode *qmaxlen;BiThrNode *creat(BiThrNode *T)/创建二叉树char ch; int front=1,rear=0; BiThrNode *s; T=NULL; ch=getchar(); while(ch!='#')/当没有结束输入时 s=NULL; if(ch!='') s=(BiThrNode *)malloc(sizeof(BiThrNode); s->data=ch; s->ltag=0;s->rtag=0;/先置0，在线索化中重新设置 s->lchild=NULL; s->rchild=NULL; rear+; qrear=s; if(rear=1) T=qrear; else if(s!=NULL&&qfront!=NULL) if(rear%2=0) /根从1开始，当为2的倍数时，为左子树 qfront->lchild=s; else /余1时，为右子树 qfront->rchild=s; if(rear%2=1)/右子树已输入完毕，父亲节点往下移 front+; ch=getchar(); return T;5、建树图示如图7： 0 1 2 3 4 5 6 图7建树图示(2)二叉树线索化：1、分析：线索过程必须要按照一定的顺序来进行。2、实现：要实现线索化，就要知道结点*pre是结点*p的前驱，而*p是*pre的后继。这样，当遍历到结点*p时，可以进行，若*p有空指针域，则将相应的标志置1；若*p的左线索标志已经建立（p->ltag=1），则可使其前驱线索化,令p->lchild=pre；若*pre的左线索标志已经建立（pre->rtag=1），则可使其后继线索化，令pre->rchild=p;3.具体实现：BiThrNode *pre=NULL;void PreThread(BiThrNode *root) /中序线索化算法，函数实现 BiThrNode *p; p=root; if(p) PreThread(p->lchild); /线索化左子树 if(pre&&pre->rtag=1) /前驱结点后继线索化pre->rchild=p; if(p->lchild=NULL) p->ltag=1; p->lchild=pre; if(p->rchild=NULL) /后继结点前驱线索化 p->rtag=1; pre=p; PreThread(p->rchild); (3)二叉树中插入结点1、方法：在树中插入一个结点，就必须要以一定的规则来进行插入。找到要插入的节点的父节点，然后选择是左孩子是右孩子插入，在看要插入的位置是否已经有其他节点，若有节点，则将要插入的结点作为该结点的前驱插入树中。若没有，则直接插入。 2、查找：在查找中，由于采用非递归形式会引入栈的操作，其麻烦程度有所不值，故依照中序线索输出，可以得到线索化后可以用的查找功能。 3、查找函数实现：BiThrNode *SearchChild(BiThrNode *T,char key_name) /查找孩子结点函数 BiThrNode *p,*q; if(T!=NULL) if(T->data=key_name) /找到时，直接返回 return T; else if(T->ltag!=1) /左孩子不为空，进入递归 p=SearchChild(T->lchild,key_name); if(p!=NULL) return p;if(T->rtag!=1) /右孩子不为空,进入递归 q=SearchChild(T->rchild,key_name); if(q!=NULL) return q; return NULL; else return NULL;4、插入方法：在一棵树中插入一个结点，因为插入的位置不同，就对应着不同的插入情况。通过分析总结出各种情况： 插入结点有左(右)孩子：直接将节点插入到目标位置，若该位置已有节点，则插入节点作为已有节点的父亲节点，若没有，直接插入，同时，对插入后的二叉树进行线索化。5、具体实现：void Insert2(BiThrNode *p,BiThrNode *r) /右孩子插入BiThrNode *s; if(p->rtag=0) /当目标结点有右孩子的时候 s=p->rchild; /保存右孩子，设置r的后继 r->rchild=s; /后继化 r->rtag=0; r->ltag=1; r->lchild=p; /连接 p->rchild=r; /前驱化 s->lchild=r; else /当目标结点没有右孩子的时候 r->rchild=p->rchild; /前驱化 r->rtag=1; p->rchild=r; p->rtag=0; r->lchild=p; r->ltag=1; printf("插入结点操作已经完成，并同时完成了线索化的恢复n");void Insert1(BiThrNode *p,BiThrNode *r) /左孩子插入BiThrNode *s; if(p->ltag=0) /当目标结点有左孩子的时候,接到左孩子最右下端 s=p->lchild; r->lchild=s; /前驱化 r->ltag=0; r->rchild=p; /后继化 r->rtag=1; p->lchild=r; s->rchild=r; else /当目标结点没有左孩子的时候，直接接入 r->lchild=p->lchild; /前驱化 r->ltag=1; p->lchild=r; p->ltag=0; r->rchild=p; r->rtag=1; printf("插入结点操作已经完成，并同时完成了线索化的恢复n"); 6、图形显示：如插入abcd# 中序为 a->b->c->d-> 插入的结点为：g 要插入的位置为：d 建树后，结点的线索变化如图8和图9；其中虚线为待插结点在插入过程中将要变化的线索 a g dvvv c b 待插入元素 d图8结点的线索变化(1) 则插入结点后的顺序为：b->g->d->a->c-> a c b g d图9结点的线索变化(2)(4) 删除结点函数 1、分析：要在函数中删除一个结点，也要考虑各种不同的情况。在删除结点之前也要先找到要删除的点，就调用查找孩子结点函数BiThrNode *SearchChild(BiThrNode *T,char key_name)找到其结点的指针。再后面的操作就是怎样删除了，就发现在删除过程中涉及的指针变换需要父亲结点的指针，所以就调用查找父亲结点BiThrNode *SearchPre(BiThrNode *T,BiThrNode *key)来查找该结点的父亲结点指针。 2、删除具体情况： 1).当结点是父亲结点的左孩子时 1.若孩子结点没有左右孩子：则直接删除； 2.若孩子结点有左孩子没右孩子：则将孩子结点的左孩子给父亲结点的左孩子； 3.若孩子结点有右孩子没左孩子：则将孩子结点的右孩子给父亲结点的左孩子； 4.若孩子结点左右孩子都有：将左孩子上提，孩子结点的左子树的右子树接到孩子结点的右子树的最左下结点的左子树，再将孩子结点的右子树接到孩子结点左子树的右子树。2).当结点是父亲结点的右孩子: 1若孩子结点没有左右孩子：则直接删除； 2.若孩子结点有左孩子没右孩子：则将孩子结点的左孩子给父亲结点的右孩子； 3.若孩子结点有右孩子没左孩子：则将孩子结点的右孩子给父亲结点的右孩子； 4.若孩子结点左右孩子都有：将右孩子上提，将孩子结点的右子树的左子树接到孩子结点的左子树的最右下结点的右子树，再将孩子结点的左子树接到孩子结点右子树的左子树。 3、具体实现：（只列出孩子结点是父结点的左子树的情况） 孩子结点无左右 if(child=pre->lchild|child=pre) /是父亲结点的左孩子 if(child->ltag=1&&child->rtag=1) /孩子结点无左右 pre->lchild=child->lchild; /child结点后继指向pre,只要保存前驱 pre->ltag=1; /原来是0 free(child); else if(child->ltag!=1&&child->rtag=1)/孩子结点有左无右 pre->lchild=child->lchild; /把child左孩子上提 s=child->lchild; /查找child左孩子的最右下端节点(往下) while(s->rchild) /该节点是child的前驱，保存child后继 s=s->rchild; s->rchild=child->rchild; /保存child后继，s右标为1 free(child); else if(child->ltag=1&&child->rtag!=1)/孩子结点有右无左 pre->lchild=child->rchild; /把右孩子上提 s=child->rchild; /查找child的后继节点，位置在右孩子的最左下端 while(s->lchild!=NULL) s=s->lchild; s->lchild=child->lchild; /把child前驱给s保存,s左标为1 free(child); else if(child->ltag!=1&&child->rtag!=1)/孩子结点左右都有 pre->lchild=child->lchild; /child左孩子上提到child位置 s=child->rchild; /child左孩子的右子树会与child右子树冲突 while(s->lchild) s=s->lchild; s->lchild=child->lchild->rchild;/若child->lchild右子树非空,把child的左孩子的右子树接到孩子 /右子树的最左下结点 if(child->lchild->rtag!=1) /child->lchild右子树非空，此时s->ltag本为1 s->ltag=0; q=child->lchild; while(q->rchild!=NULL) q=q->rchild; q->rchild=s; /把q的后继指到s上 child->lchild->rchild=child->rchild;/child左孩子的右子树设置 child->lchild->rtag=0; /原本不知是否为0，但可以一起考虑 free(child); 4、图形显示如图10和图11：如删除结点g 中序为: bgdac 删除后: bdac c b a g d图10图形显示删除结点g图11图形显示删除结点b四上机调试在调试时，按照原有的思路，查找二叉树中目标节点，用的是出栈和入栈相关操作，但是在具体设计时，遇到的问题有点复杂，结果是在循环时找到了问题所在，由于本身思想的设计就有问题，重新思考了一下，感觉比较麻烦，重新利用线索后二叉树输出函数改出递归遍历，在插入删除时，具体情况具体对待，分出不同的情况，插入删除操作中，规则是咨询了王教授，要求是自己设计，于是选择了不改变线索为原则，和下面的恢复线索可以对照着完成，在完成时，由于设计好了情况与应对操作，故总体上能够完成，在细节时，参考了数据结构-c语言描述.五、测试结果及分析程序运行后1、建立线索二叉树（见下图）图12建立线索二叉树2、对线索二叉树进行插入操作（见下图）图13线索二叉树的插入3、对线索二叉树进行删除操作（见下图）图14线索二叉树删除操作分析：由以上结果均符合预期的目标，成功完成。六、用户使用说明本程序是在VC+ 6.0中编写，程序运行环境：DOS根据程序的提示即可完成文本编辑器的各项功能。其中具体的操作可依照程序运行时的说明。七、参考文献王昆仑、李红。数据结构与算法。北京：中国铁道出版社。八、附录#include"stdio.h"#include"malloc.h"#include"stdlib.h"#define NULL 0#define maxlen 20typedef struct node char data; struct node *lchild, *rchild; /*左右孩子子树*/ int ltag,rtag;BiThrNode; BiThrNode *qmaxlen;BiThrNode *creat(BiThrNode *T)/创建二叉树char ch; int front=1,rear=0; BiThrNode *s; T=NULL; ch=getchar(); while(ch!='#')/当没有结束输入时 s=NULL; if(ch!='') s=(BiThrNode *)malloc(sizeof(BiThrNode); s->data=ch; s->ltag=0;s->rtag=0;/先置0，在线索化中重新设置 s->lchild=NULL; s->rchild=NULL; rear+; qrear=s; if(rear=1) T=qrear; else if(s!=NULL&&qfront!=NULL) if(rear%2=0) /根从1开始，当为2的倍数时，为左子树 qfront->lchild=s; else /余1时，为右子树 qfront->rchild=s; if(rear%2=1)/右子树已输入完毕，父亲节点往下移 front+; ch=getchar(); return T;void inorder(BiThrNode *T) /中遍历，只能在线索化前使用 if(T!=NULL) inorder(T->lchild); printf("%c ",T->data); inorder(T->rchild); void Inorder(BiThrNode *T) /中序遍历 if(T) if(T->ltag!=1) Inorder(T->lchild); printf("%c",T->data); if(T->rtag!=1) Inorder(T->rchild); BiThrNode *SearchPre(BiThrNode *T,BiThrNode *key)/查找父亲结点函数 BiThrNode *p,*q; if(T!=NULL) if(T->ltag!=1&&T->lchild=key)|(T->rtag!=1&&T->rchild=key) return T; /找到时返回point，非空量 else if(T->ltag!=1) /进入左孩子递归查找 p=SearchPre(T->lchild,key); if(p!=NULL) return p; else if(T->rtag!=1) /进入右孩子递归查找 q=SearchPre(T->rchild,key); if(q!=NULL) return q; return NULL; /分为层次性,在if里面,若前面return执行，则该句不执行 else return NULL;BiThrNode *SearchChild(BiThrNode *T,char key_name) /查找孩子结点函数 BiThrNode *p,*q; if(T!=NULL) if(T->data=key_name) /找到时，直接返回 return T; else if(T->ltag!=1) /左孩子不为空，进入递归 p=SearchChild(T->lchild,key_name); if(p!=NULL) return p; if(T->rtag!=1) /右孩子不为空,进入递归 q=SearchChild(T->rchild,key_name); if(q!=NULL) return q; return NULL; else return NULL;void Insert2(BiThrNode *p,BiThrNode *r) /右孩子插入 BiThrNode *s; if(p->rtag=0) /当目标结点有右孩子的时候 s=p->rchild; /保存右孩子，设置r的后继 r->rchild=s