线索二叉树课程设计

线索二叉树课程设计 湖南人文科技学院计算机系 课程设计 说明书 房屋状态说明书下载罗氏说明书下载焊机说明书下载罗氏说明书下载GGD说明书下载 课程名称: 数据结构课程设计 课程代码: 408025 题 目: 线索二叉树的计算 年级 六年级体育公开课教案九年级家长会课件PPT下载六年级家长会PPT课件一年级上册汉语拼音练习题六年级上册道德与法治课件 /专业/班: 09级软件工程二班 学生姓名: 谷其飞 学号: 09436210 指导老师: 唐海波 开题时间: 2010年12 月23 日 完成时间: 2010年 12月29日 课程设计任务书及成绩评定 线索二叉树的计算 课程名称: 完成者: 谷其飞 1、设计的目的与要求 此程序需要完成如下要求:建立线索二叉树，并实现线索二叉树的插入、删除和恢复线索的实现。 实现本程序需要解决以下几个问题: 1、 如何建立线索二叉树。 2、 如何实现线索二叉树的插入。 3、 如何实现线索二叉树的删除。 4、 如何实现线索二叉树恢复线索的实现。 此题目是线索二叉树的一系列操作问题。首先就要明白线索二叉树是什么，利用二叉链表的空指 针域将空的左孩子指针域改为指向其前驱，空的右孩子指针域改为指向其后继，这种改变指向的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。 在这个问题中，要解决的任务是:实现线索二叉树的建立、插入、删除、恢复线索的实现。N个 结 点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下 的前趋和后继结点的指针(这种附加的指针称为"线索")。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。在此次课程设计中，采用的是中序线索二叉树。 2、设计进度及完成情况 日 期 内 容 12.23 分析问题，找出所要解决问题的关键 12.24 总体设计，找出解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 12..25 详细设计，列出解决步骤 12.26-12.28 程序编写，调试，修改加以完善 12.29 书写文档 3、成绩评定 设计成绩: - 1 - 指导老师: 年 月 日 - 2 - 目 录 摘要…………………………………………………………………………………………4 一、引言……………………………………………………………………………………5 二、设计任务与目的 …………………………………………………………………… 5 三、设计方案与实施………………………………………………………………………5 1、总体设计………………………………………………………………………… 5 2、详细设计………………………………………………………………………… 7 3、程序清单………………………………………………………………………… 13 4、程序调试与体会……………………………………………………………………24 5、运行结果(截图)………………………………………………………………… 24 四、结论……………………………………………………………………………………27 五、致谢……………………………………………………………………………………27 六、参考文献………………………………………………………………………………27 - 3 - 摘 要 随着人们生活水平的提高，计算机发展异常迅速。如今，计算机已经深入到我们社会 的各个领域，计算机的使用也已不再局限于科学计算，它已进入人类社会的各个领域并发 挥着越来越重要的作用。通过计算机对各类问题求解已经成为一种高效、快捷的方式。树 在计算机领域也得到了广方的应用，如在编译程序中，可以用树表示原程序的语法结构。 本次课程设计主要运用二叉树的一些特点，来实现线索二叉树的建立、插入、删除、 恢复线索等等。 关键词:二叉树～线索链表～线索化～线索。 Abstract Key words: Binary tree, Clues linked list, Clues optimization, Clues. people living standard rise, computer to abnormal development rapidly. As Today, computers have deeply into every field of our society, the use of computers is no longer limited to scientific computing, it entered the human society eachdomain and plays a more and more important role. Through computer for all kinds of problem solving has become an efficient, quick way. Trees in the field of computer also got wide square applications, such as in compiler, can use the tree says the original program grammatical structures. - 4 - 《数据结构》课程设计 --线索二叉树的计算 一、引 言 树是一种重要的非线性数据结构，直观地看，它是数据元素(在树中称为结点)按分支关系组织起来的结构，很象自然界中的树那样。结构树在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序时，可用树表示源程序的语法结构。又如在数据系统库中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。 二、设计目的与任务 通过本课程设计教学所要求达到的目的是:建立线索二叉树，并实现线索二叉树的插入、删除和恢复线索的实现。 三、设计方案 1、总体设计 首先建立二叉树，然后对二叉树进行线索化。 线索链表的结点结构 线索链表中的结点结构为: 图(1) 线索链表中的结点结构 中序线索二叉树的图示 - 5 - 图(2) 中序线索二叉树 建立二叉树(即指在内存中建立二叉树的存储结构)，建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需添加虚结点，使其成为完全二叉树。 关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。可以设置一个队列，该队列是一个指针类型的数组，保存已输入的结点地址。 (1)令队头指针front指向其孩子结点当前输入的建立链接的父结点，队尾指针 rear指向当前输入的结点，初始:front=1,rear=0; (2)若rear为偶数，则该结点为父结点的左孩子;若rear为奇数，则该结点的 右孩子;若父结点和孩子结点为虚结点，则无需链接。 (3)若父结点与其两个孩子结点的链接完毕，则令front=front+1,使front指向下一个等待链接的父结点。 二叉树的中序索化算法与中序历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中前趋结点间线索。该算法应附设一个指针pre始终指向刚刚访问过的结点(pre的初值应为NULL)，而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋，而*p是*pre的后继。 程序流程图: - 6 - 开始 定义二叉树 建立二叉树 选择菜单 输入i(0-5) i=1N Y i=2N中序输出二叉树 Y i=3N进行二叉树线索化 Y i=4N插入结点并线索化 Y i=5删除结点并线索化 YN 输出线索二叉树 结束 图(3) 程序流程图 2、详细设计 (1) 建树算法: 1、分析:建立一个二叉链表，需要按照某种顺序依次输入二叉树中的结点，且该输入顺序必须隐含结点间的逻辑结构的信息。这个建立的方法，按完全二叉树的层次顺序，依次输入结点信息建立二叉链表的过程。以@表示空结点，以#表示输入结束的标志 。 2、算法思想:依次输入结点信息，若其不是虚结点，则建立一个新结点。若新结点是第一个结点，则令其为根结点，否则将新结点作为孩子链接到它的父亲结点上。 - 7 - 3、实现:在函数中设置一队列，该队列是一个指针类型的数组，保存已输入的结点的地址。使队头指针front指向当前与孩子建立链接的父亲结点，队尾指针rear指向当前输入的结点。若rear为偶数，则该结点为父结点的左孩子，若rear为奇数，则为父结点的右孩子。若父结点或孩子结点为虚结点，则无需链接。若父结点与其两个孩子结点链接完毕，则使front指向下一个等待链接的父结点。 4、主要过程: Bithptr *Q[maxsize]; //建队为指针类型 Bithptr *CreatTree(){ front=1;rear=0; //置空队 if(ch!='@') //不是虚结点，则建立结点 s=(Bithptr *)malloc(sizeof(Bithptr)); s->data=ch; s->lchild=NULL; s->rchild=NULL; s->rtag=0; s->ltag=0; if(s!=NULL&&Q[front]!=NULL) //孩子和双亲结点都不是虚结点 if(rear%2==0) Q[front]->lchild=s; else Q[front]->rchild=s; if(rear%2==1)front++; //结点*Q[front]的两个孩子处理完，front+1 (2) 线索化算法: 1、分析:线索过程必须要按照一定的顺序来进行，在本程序中因为树的遍历过程使用的是中序遍历，所以为了方便，线索化的过程也是使用中序线索化。 2、方法:按某种遍历顺序将二叉树线索化，只需要在遍历的过程中将二叉树中每个结点的空的左右孩子指针域分别修改为指向其前驱和后继。若其左子树为空，则将其左孩子域线索化，使其左孩子指针lchild指向其后继，并且ltag置1。 3、实现:要实现线索化，就要知道结点*pre是结点*p的前驱，而*p是*pre的后继。这样，当遍历到结点*p时，可以进行，若*p有空指针域，则将相应的标志置1;若*p的左线索标志已经建立(p->ltag==1)，则可使其前驱线索化，令p->lchild=pre;若*pre的左线索标志已经建立(pre->rtag==1)，则可使其后继线索化，令pre->rchild=p; 4、主要过程: void PreThread(Bithptr *root) { 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) //后继结点前驱线索化 - 8 - p->rtag=1; pre=p; PreThread(p->rchild); } } (3) 插入结点函数 1、方法:在树中插入一个结点，就必须要以固定的规则来进行插入。在本程序中对树的输出使用了中序输出的方法，所以插入的时候使用的规则就是以中序输出为顺序，先查找到一个点，再将要插入的结点作为该结点的前驱插入树中。如中序为:?d?b?e?a?f?c?g 插入的结点为:w 要插入的位置为:b 则插入结点后的顺序为:?d?w?b?e?a?f?c?g 2、查找:使用查找孩子指针函数来查找结点位置的指针。在查找的过程中要处理好线索指针和孩子指针的关系，不能将线索也当作孩子处理了。并且在循环的判断过程中，再不能使用以前的以空为结束语句，而是要用标志域来进行判断。在查找的过程中，考虑到树的递归性质，所以将查找函数也设置为递归函数。 3、查找函数实现: Bithptr*SearchChild(Bithptr*point,char findnode) { Bithptr *point1,*point2; if(point!=NULL) { if(point->data==findnode)return point; //找到结点的信息，返回指针 else if(point->ltag!=1) { //判断是否有左子树 point1=SearchChild(point->lchild,findnode);//递归 if(point1!=NULL) return point1; } if(point->rtag!=1){ //判断是否有右子树 point2=SearchChild(point->rchild,findnode);//递归 if(point2!=NULL) return point2; } return NULL; } else return NULL; } 4、插入方法:在一棵树中插入一个结点，因为插入的位置不同，就对应着不同的插 入情况。通过分析 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 出各种情况: 插入结点有左孩子时: 插入的方法是，找到左子树的最右下结点，将待插的结点插为其结点 的右孩子。 插入结点没有左孩子时: - 9 - 插入的方法是，直接将待插的结点插为其结点的左孩子。 5、插入实现: (当结点有左子树时) p2=child; child=child->lchild; while(child->rchild&&child->rtag==0) //左子树的最右下结点 child=child->rchild; p1->rchild=child->rchild; //后继线索化 ->rtag=1; p1 child->rtag=0; child->rchild=p1; //连接结点 p1->lchild=child; //前驱线索化 p1->ltag=1; (当结点没左孩子的时) p1->lchild=child->lchild; //前驱化 child->ltag=0; p1->ltag=1; child->lchild=p1; p1->rchild=child p1->rtag=1; 6、图形显示:如插入abcdefg# 中序为:?d?b?e?a?f?c?g 插入的结点为:w 要插入的位置为:b 建树后，结点的线索变化如图4和图5; 其中虚线为待插结点在插入过程中将要变化的线索 a b c ^ d e f g ^^dvvv^^图(4) 结点的线索变化图a ^^^^ 则插入结点后的顺序为:?d?w?b?e?a?f?c?g a - 10 - b c 图(5) 结点的线索变化 图b (4) 删除结点函数 1、分析:要在函数中删除一个结点，也要考虑各种不同的情况。在删除结点之前也要先找到要删除的点，就调用查找孩子结点函数Bithptr *SearchChild(Bithptr *point,char findnode)找到其结点的指针。再后面的操作就是怎样删除了，就发现在删除过程中涉及的指针变换需要父亲结点的指针，所以就调用查找父亲结点函数Bithptr *SearchPre(Bithptr *point,Bithptr *child)来查找该结点的父亲结点指针。 2、删除方法:考虑在删除的过程中的各种不同的情况，就要在程序的设计中进行 不同的分类，进行不同的处理，考虑不同的处理过程。通过总结可以知道各种不同 的情况。 (当要删除结点是父亲结点的左孩子时) 若要删除结点没有左右孩子:则直接删除; 若要删除结点有左孩子没右孩子:则将要删除结点的左孩子给父亲结点的左孩子; 若要删除结点有右孩子没左孩子:则将要删除结点的右孩子给父亲结点的左孩子; 若要删除结点左右孩子都有:将要删除结点的左子树的右子树接到孩子结点的右子 树的最左下结点的左子树，再将孩子结点的右子树接到孩子结点左子树的右子 树。 (当要删除结点是父亲结点的右孩子时) 若要删除结点没有左右孩子:则直接删除; 若要删除结点有左孩子没右孩子:则将要删除结点的左孩子给父亲结点的右孩子; 若要删除结点有右孩子没左孩子:则将要删除结点的右孩子给父亲结点的右孩子; 若要删除结点左右孩子都有:将要删除结点的右子树的左子树接到孩子结点的左子 树的最右下结点的右子树，再将孩子结点的右子树接到孩子结点右子树的左子 树。 (当要删除结点是整个二叉树的头结点时) 若要删除结点没有左右孩子，则直接将空给头指针。 若要删除结点有左孩子没右孩子，则将孩子结点的左孩子作为头结点。 若要删除结点有右孩子没左孩子，则将孩子结点的右孩子作为头结点。 若要删除结点左右孩子都有，则将孩子结点的左孩子作为头结点，将孩子结点 的右子树插入孩子结点的左子树的最右下结点的右子树。 3、实现: (只列出要删除结点是父结点的左子树的情况) 要删除结点无左右 pre->lchild=child->lchild; pre->ltag=1; - 11 - if(child->lchild!=NULL) if(child->lchild->rtag==1)child->lchild->rchild=pre; 要删除结点有左无右: pre->lchild=child->lchild; s=child->lchild; while(s->rchild) s=s->rchild; s->rchild=child->rchild; 要删除结点有右无左: pre->lchild=child->rchild; s=child->rchild; while(s->lchild) s=s->lchild; s->lchild=child->lchild; if(child->lchild!=NULL) if(child->lchild->rtag==1)child->lchild->rchild=pre; 要删除结点左右都有: pre->lchild=child->lchild; s=child->rchild; while(s->lchild) s=s->lchild; s->lchild=child->lchild->rchild; //把要删除结点的左孩子的右子树接到 孩子右子树的最左下结点 if(child->lchild->rtag!=1)s->ltag=0; q=child->lchild; while(q->rchild) q=q->rchild; q->rchild=s; child->lchild->rchild=child->rchild; child->lchild->rtag=0; 4、图形显示如图6:如删除结点e 中序为:?d?b?e?a?f?c?g 删除后:?d?b?a?f?c?g a b c d e f g - 12 - 图(6)删除结点图示 3、程序清单 #include "stdio.h" #include "malloc.h" #define maxsize 20 //规定树中结点的最大数目 typedef struct node{ //定义数据结构 int ltag,rtag; //表示child域指示该结点是否孩子 char data; // 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 结点的数据 struct node *lchild,*rchild; //记录左右孩子的指针 }Bithptr; Bithptr *Q[maxsize]; //建队，保存已输入的结点的地址 Bithptr *CreatTree(){ //建树函数，返回根指针 char ch; int front,rear; Bithptr *T,*s; T=NULL; front=1;rear=0; //置空二叉树 printf("***********************************\n"); printf("* *\n"); printf("* 课程设计题目:线索二叉树的运算。*\n"); printf("* *\n"); printf("***********************************\n"); printf("创建二叉树，请依次输入，@表示虚结点，以#结束\n"); ch=getchar(); //输入第一个字符 while(ch!='#') //判断是否为结束字符 { s=NULL; if(ch!='@') //判断是否为虚结点 { s=(Bithptr *)malloc(sizeof(Bithptr)); s->data=ch; s->lchild=NULL; - 13 - s->rchild=NULL; s->rtag=0; s->ltag=0; } rear++; Q[rear]=s; //将结点地址加入队列中 if(rear==1)T=s; //输入为第一个结点为根结点 else { if(s!=NULL&&Q[front]!=NULL) //孩子和双亲结点均不是虚结点 if(rear%2==0) Q[front]->lchild=s; else Q[front]->rchild=s; if(rear%2==1)front++; } ch=getchar(); } return T; } void Inorder(Bithptr *T) //中序遍历 { if(T) { if(T->ltag!=1)Inorder(T->lchild); printf("?%c",T->data); if(T->rtag!=1)Inorder(T->rchild); } } Bithptr *pre=NULL; void PreThread(Bithptr *root) //中序线索化算法，函数实现 { - 14 - Bithptr *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); } } void PrintIndex(Bithptr *t) //输出线索 { Bithptr *f; f=t; if(f) { if(f->ltag==1&&f->lchild==NULL&&f->rtag==1) printf("【%c】",f->data); //如果是第一个结点 if(f->ltag==1&&f->lchild!=NULL) printf("%c?【%c】",f->lchild->data,f->data); //如果此结点有前驱就输出前驱和此结点 if(f->ltag==1&&f->rtag==1&&f->rchild!=NULL) printf("?%c",f->rchild->data); //如果此结点有前驱也有后继，就输出后继 else if(f->rtag==1&&f->rchild!=NULL) printf("【%c】?%c",f->data,f->rchild->data);//如果没有前驱，就输出此结点和后继 printf("\n"); if(f->ltag!=1)PrintIndex(f->lchild); if(f->rtag!=1)PrintIndex(f->rchild); } - 15 - } Bithptr *SearchChild(Bithptr *point,char findnode) //查找孩子结点函数 { Bithptr *point1,*point2; if(point!=NULL) { if(point->data==findnode) return point; else if(point->ltag!=1) { point1=SearchChild(point->lchild,findnode); if(point1!=NULL)return point1;} if(point->rtag!=1) { point2=SearchChild(point->rchild,findnode); if(point2!=NULL)return point2;} return NULL; } else return NULL; } Bithptr *SearchPre(Bithptr *point,Bithptr *child) //查找父亲结点函数 { Bithptr *point1,*point2; if(point!=NULL) { if((point->ltag!=1&&point->lchild==child)||(point->rtag!=1&&point->rchild==child)) return point;//找到则返回 else if(point->ltag!=1) { point1=SearchPre(point->lchild,child); if(point1!=NULL) return point1; } if(point->rtag!=1) { - 16 - point2=SearchPre(point->rchild,child); if(point2!=NULL) return point2; } return NULL; } else return NULL; } void Insert(Bithptr *root) { char ch; char c; Bithptr *p1,*child,*p2; printf("请输入要插入的结点的信息:"); scanf("%c",&c); scanf("%c",&c); p1=(Bithptr *)malloc(sizeof(Bithptr)); //插入的结点信息 p1->data=c; p1->lchild=NULL; p1->rchild=NULL; p1->rtag=0; p1->ltag=0; printf("输入查找的结点信息:"); scanf("%c",&ch); scanf("%c",&ch); child=SearchChild(root,ch); //查孩子结点的地址 if(child==NULL){ printf("没有找到结点\n"); return ; } else printf("发现结点%c\n",child->data); if(child->ltag==0) //当孩子结点有左孩子的时候 - 17 - { p2=child; child=child->lchild; while(child->rchild&&child->rtag==0) //找到左子树下，最右结点 child=child->rchild; p1->rchild=child->rchild; //后继化 p1->rtag=1; child->rtag=0; child->rchild=p1; //连接 p1->lchild=child; //前驱化 p1->ltag=1; } else //当孩子结点没有左孩子的时候 { p1->lchild=child->lchild; //前驱化 child->ltag=0; p1->ltag=1; child->lchild=p1; p1->rchild=child; p1->rtag=1; } printf("\n\t插入结点操作已经完成，并同时完成了线索化的恢复\n"); } Bithptr * DeleteNode(Bithptr *t) { Bithptr *child,*pre,*s,*q; char ch; printf("输入查找的结点信息:"); ch=getchar(); ch=getchar(); child=SearchChild(t,ch); //查找该结点的孩子结点 - 18 - printf("发现结点:%c\n",child->data); printf("ltag=%d,rtag=%d\n",child->ltag,child->rtag); if(NULL==child) { printf("没有找到结点:"); return t; } if(child!=t) { pre=SearchPre(t,child); printf("发现结点:%c\n",pre->data); } else //当是头结点的时候 if(child->ltag==1&&child->rtag==1) //没有左右孩子 t=NULL; else if(t->ltag==1&&t->rtag!=1) //有右孩子没有左孩子 { t=child->rchild; child->rchild->lchild=NULL; free(child); return t; }else if(t->ltag!=1&&t->rtag==1) //有左孩子没有右孩子 { t=child->lchild; child->lchild->rchild=NULL; free(child); return t; }else if(t->ltag!=1&&t->rtag!=1) //有左孩子也有右孩子 { t=child->lchild; - 19 - s=child->lchild; while(s->rchild&&s->rtag!=1) //查找孩子左子树的最右下结点 s=s->rchild; q=child->rchild; while(q->lchild&&q->ltag!=1) //查找孩子右子树的最左下结点 q=q->lchild; s->rchild=child->rchild; //连接 s->rtag=0; q->lchild=s; free(child); return t; } if(child==pre->lchild||child==pre) //是父亲结点的左孩子 { if(1==child->ltag&&1==child->rtag)//孩子结点无左右 { pre->lchild=child->lchild; pre->ltag=1; if(child->lchild!=NULL) if(child->lchild->rtag==1)child->lchild->rchild=pre; free(child); } else if(1!=child->ltag&&1==child->rtag)//孩子结点有左无右 { pre->lchild=child->lchild; s=child->lchild; while(s->rchild) //查找左子树的最右下结点 s=s->rchild; s->rchild=child->rchild; free(child); } - 20 - else if(1==child->ltag&&1!=child->rtag)//孩子结点有右无左 { pre->lchild=child->rchild; s=child->rchild; while(s->lchild) s=s->lchild; s->lchild=child->lchild; if(child->lchild!=NULL) if(child->lchild->rtag==1)child->lchild->rchild=pre; free(child); } else if(1!=child->ltag&&1!=child->rtag)//孩子结点左右都有 { pre->lchild=child->lchild; s=child->rchild; while(s->lchild&&s->ltag!=1) //找到右子树的最左下结点 s=s->lchild; q=child->lchild; while(q->rchild&&q->rtag!=1) //找到左子树下最右下结点 q=q->rchild; q->rchild=child->rchild; //将孩子结点的右子树接到左子树下最 右下结点 q->rtag=0; s->lchild=q; free(child); } }else { if(child==pre->rchild) //是父亲结点的右孩子 { if(1==child->ltag&&1==child->rtag)//孩子结点无左右 { pre->rchild=child->rchild; pre->rtag=1; - 21 - if(child->rchild!=NULL) if(child->rchild->ltag==1)child->rchild->lchild=pre; free(child); } else if(1!=child->ltag&&1==child->rtag)//孩子结点有左无右 { pre->rchild=child->lchild; s=child->lchild; while(s->rchild) s=s->rchild; s->rchild=child->rchild; if(child->rchild!=NULL) if(child->rchild->ltag==1)child->rchild->lchild=pre; free(child); } else if(1==child->ltag&&1!=child->rtag)//孩子结点有右无左 { pre->rchild=child->rchild; s=child->rchild; while(s->lchild) s=s->lchild; s->lchild=child->lchild; free(child); } else if(1!=child->ltag&&1!=child->rtag) //孩子结点左右都有 { pre->rchild=child->rchild; s=child->rchild; while(s->lchild&&s->ltag!=1) //找到右子树的最左下结点 s=s->lchild; q=child->lchild; while(q->rchild&&q->rtag!=1) //找到左子树下最右下结点 q=q->rchild; - 22 - s->lchild=child->lchild; //将孩子结点的左子树接到右子树下最左 下结点 s->ltag=0; q->rchild=s; free(child); } } } printf("\n\t删除结点操作已经完成，并同时完成了线索化的恢复\n"); return t; } void main() { Bithptr *T; int i; T=CreatTree(); printf("\n"); i=1; while(i) { printf("\t1 中序输出二叉树\n"); printf("\t2 进行二叉树线索化\n"); printf("\t3 进行插入操作\n"); printf("\t4 进入删除操作\n"); printf("\t5 输出线索二叉树\n"); printf("\t0 退出\n"); printf("\t 请选择:"); scanf("%d",&i); printf("\n"); switch(i) - 23 - { case 1:Inorder(T); printf("\n"); break; case 2:PreThread(T); printf("\t已经实现二叉树的线索化，(可选择'5'察看线索)\n"); printf("\n"); break; case 3:Insert(T);printf("\n");break; case 4:T=DeleteNode(T);printf("\n");break; case 5:PrintIndex(T);break; default:printf("error\n\t请继续选择:"); } } } 4、程序调试与体会 1)语法错误及修改:编译中出现的语法问题主要在于子函数和变量的定义，括号的配对，关键字 和函数名称的书写，以及一些库函数的规范使用等问题时常出现。但这些问题均可以根据编译器的警告提示，一一对应的将其解决。总结其出现原因有多方面的，比如各个变量名称前后不一致，缺少符号等。对了还有一个原因就是中英文的标点混合，这也是一个大的容易错的细节，而且出现问题之后往往难以辨明。经过这次经历后，我想以后这些低级错误会最大限度的避免的。 2)逻辑问题修改和调整:本程序所写内容基本上都是课本中所未提及知识，所以在编程过程中遇到了很多的难题，另外由于线索二叉树的插入和删除运算过程很复杂，所以设计过程中经常出现各种没有考虑到的情况，通过查找课本和资料以及询问同学及老师最终基本实现线索二叉树的运算处理。在编译过程中运用了很多的递归运算，比如中序遍历，中序线索二叉树和查找等函数中，这都是在编程中找到的具体解决方法。 5、运行结果(截图) 如图(7)所示，建立二叉树并中序输出 - 24 - 图(7) 建立二叉树并中序输出 如图(8)所示，线索化二叉树并输出线索二叉树 图(8) 线索化二叉树并输出线索二叉树 如图(9)所示，插入结点F并线索化输出 - 25 - 图(9) 插入结点F并线索化输出 如图(10)所示，删除结点D并线索化输出 图(10) 删除结点D并线索化输出 - 26 - 四、结 论 通过本次课程设计，我们了解到了课程设计的要求与方法，学会了程序设计的基本步骤，灵活应用所学数据结构知识，独立完成问题分析。初步掌握软件开发过程的问题 分析、系统设计、程序编码、测试等方法。训练用系统的观点和软件开发一般规范进行软件开发。提高综合运用所学的理论知识和方法独立分析和解决问题的能力且进一步提高了团队合作的意识。同时，我们也感觉到，一个优秀的程序，不仅仅只是可以运行，更应该具有较高的效率，合理的结构，良好的可读性和一定的容错性。其中非常重要的一点是，我们认为整个课程设计是一个团队的工作，一个人要完成所有的工作是非常困难和耗时的，必须发挥团队的团结协作精神，提高工作效率和工作质量，团结协作是我们本次课程设计取得成功的一项尤其重要的保证。在以后的学习中我们也会更加注意各个方面能力的协调和发展。 五、致谢 感谢我们的指导老师唐海波老师，谢谢他在我们的课程设计过程中提出了指导性的方案和架构，并指引我们阅读相关的资料和书籍，使我们在不熟悉的领域中仍能迅速掌握新的方法和技术。 感谢校领导给我们这次难得的锻炼机会，让我们能更好的理解和实践数据结构编程，让我们对数据结构编程有了更深刻的认知，对已学知识有了更进一步的巩固。 六、参考文献 [1] 编译原理程序设计 陈火旺等 国防工业出版社 2005年 [2] 王昆仑,李红,数据结构与算法.中国铁道出版社 [3] 赵坚,姜梅.数据结构(C语言版).中国水利水电出版社 [4] 孟祥瑞,汤文兵.数据结构(C语言版).东华理工大学出版社 [5] 候风巍.数据结构要点精析.北京航空航天大学出版社 - 27 -