数据结构课程设计报告线索二叉树的应用.doc

青岛理工大学数据结构课程设计报告题目：线索二叉树的应用 院（系）：计算机工程学院 学生姓名: 班级： 学号: 起迄日期: 2015.07.13-2015.07.24指导教师: 任务书一、数据结构课程设计的目标课程设计是数据结构课程的一个重要的实践环节，它可加深学生对该课程所学内容的进一步的理解与巩固，达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，培养基本的对基本数据结构的理解和运用，良好的程序设计方法、提高编码及调试程序技能的能力，为整个专业的学习以及软件设计水平的提高打下良好的基础。二、设计内容线索二叉树的应用【问题描述】实现中序线索树的建立、插入、删除、中序遍历输出等功能。【设计要求】每次操作后都要以凹入或横向的方式输出二叉树。 三、设计要求1、学生必须仔细阅读数据结构课程设计任务书，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。2、学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时向教师汇报。3、课程设计按照教学要求需要两周时间完成，学院安排上机时间学生不得缺席。 4、每位学生必须认真、独立完成设计任务，发现抄袭者或雷同者，一律按零分处理。5、程序设计语言可选择C或C+ 。6、程序要正确且具有一定的健壮性，不会因为用户的输入错误引起程序运行错误而中断执行，对输入值的类型、大小范围、字符串的长度等，进行正确性检查，对不合法的输入值给出出错信息，指出错误类型，等待重新输入。一、需求分析 1.问题描述题目需要完成如下要求：实现中序线索树的建立、插入、删除、中序遍历输出等功能。2.基本功能实现本程序需要实现以下几个功能：1、 建立线索二叉树。2、 实现线索二叉树的插入。3、 实现线索二叉树的删除。4、 实现线索二叉树的中序遍历输出。二、 概要设计1.设计思路：在这个题目中，要解决的任务是：实现线索二叉树的建立、插入、删除、遍历的实现。n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为"线索"）。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。而在此次课程设计中，采用的是中序线索二叉树。本问题的关键和难点在于线索二叉树的插入和删除。在线索二叉树中插入一个结点或删除一个结点，一般情况下，这些操作有可能破坏原来已有的线索，因此，在修改指针时，还需要对线索做相应的修改。因此一般来说，这个过程度的代价几乎与重新进行线索化相同。2.数据结构设计： 线索链表的结点结构线索链表中的结点结构为： 建立二叉树（即指在内存中建立二叉树的存储结构），建立一个二叉链表，需按某种顺序一次输入二叉树中的结点，且输入顺序必须隐含结点间的逻辑结构信息。对于一般的二叉树，需添加虚结点，使其成为完全二叉树。关键在于如何将新结点作为左孩子和右孩子连接到它的父结点上。可以设置一个队列，该队列是一个指针类型的数组，保存已输入的结点地址。操作：（1）令队头指针front指向其孩子结点当前输入的建立链接的父结点，队尾指针rear指向当前输入的结点，初始：front=1,rear=0; （2）若rear为偶数，则该结点为父结点的左孩子；若rear为奇数，则该结点的右孩子；若父结点和孩子结点为虚结点，则无需链接。 （3）若父结点与其两个孩子结点的链接完毕，则令front=front+1,使front指向下一个等待链接的父结点。二叉树的中序线索化算法与中序遍历算法类似。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL），而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋，而*p是*pre的后继。3.软件结构设计： 建立二叉树 Bithptr *CreatTree() 线索化二叉树 PreThread(Bithptr *r) 线索二叉树的插入 Insert(Bithptr *root) 线索二叉树的删除 Bithptr * DeleteNode(Bithptr *t) 中序遍历二叉树 Inorder(Bithptr *T)三、 详细设计 1. 定义程序中所有用到的数据及其数据结构，及其基本操作的实现； typedef struct node /定义数据结构 int ltag,rtag; /表示child域指示该结点是否孩子 char data; /记录结点的数据 struct node *lchild,*rchild; /记录左右孩子的指针Bithptr;2主函数和其他函数的算法；主函数： void main() Bithptr *T;int i;T=CreatTree();i=1;while(i) system("cls");printf("*n"); printf("n"); printf("ttt 线索二叉树的应用n"); printf("n");printf("*n"); printf("ttt1 中序线索化二叉树n"); printf("ttt2 进行插入操作n"); printf("ttt3 进入删除操作n"); printf("ttt4 中序遍历输出n"); printf("ttt0 退出n"); printf("tt二叉树："); Inorder(T);printf("n*n"); show(T,0);printf("n*n"); printf(" 请选择:"); scanf("%d",&i); printf("n"); switch(i)case 1:if (m = 0)PreThread(T); printf("中序线索化成功！n"); printf("按任意键继续！");break; case 2:if (m = 0)PreThread(T);Insert(T);printf("n按任意键继续n");break;case 3:if (m = 0)PreThread(T); T = DeleteNode(T); printf("n按任意键继续n"); break; case 4:Inorder(T); printf("n按任意键继续n"); break; case 0:exit(1); default:system("cls");getchar();getchar();建立二叉树：Bithptr *CreatTree() /建树函数，返回根指针char ch;int front,rear;Bithptr *T,*s;T=NULL;front=1;rear=0; /置空二叉树 printf("创建二叉树，请依次输入，表示虚结点，以#结束n");ch=getchar(); /输入第一个字符while(ch!='#') /判断是否为结束字符s=NULL;if(ch!='') /判断是否为虚结点s=(Bithptr *)malloc(sizeof(Bithptr);s->data=ch;s->lchild=NULL;s->rchild=NULL;s->rtag=0;s->ltag=0;rear+; Qrear=s; /将结点地址加入队列中if(rear=1)T=s; /输入为第一个结点为根结点else if(s!=NULL&&Qfront!=NULL) /孩子和双亲结点均不是虚结点if(rear%2=0) Qfront->lchild=s; else Qfront->rchild=s;if(rear%2=1)front+;ch=getchar();return T;线索化二叉树：void PreThread(Bithptr *r) /中序线索化算法，函数实现Bithptr *p;p=r; 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);m = 1;线索二叉树的插入：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");system("pause");return ;else printf("发现结点%cn",child->data);if(child->ltag=0) /当孩子结点有左孩子的时候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("nt插入结点成功n");线索二叉树的删除：Bithptr * DeleteNode(Bithptr *t)Bithptr *child,*pre,*s,*q;char ch;printf("输入查找的结点信息:"); ch=getchar();ch=getchar();child=SearchChild(t,ch); /查找该结点的孩子结点if (child = NULL)printf("没有找到结点:");return t;printf("发现结点:%cn", child->data);if(child!=t)pre=SearchPre(t,child);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;elseif(t->ltag!=1&&t->rtag!=1) /有左孩子也有右孩子t=child->lchild;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);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;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(child->ltag!=1&&child->rtag!=1) /孩子结点左右都有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;s->lchild=child->lchild; /将孩子结点的左子树接到右子树下最左下结点s->ltag=0;q->rchild=s;free(child);printf("nt删除结点成功n");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);3.主要函数的程序流程图图3.1 主函数图3.2 建立二叉树 图3.3 插入结点 图3.4 删除结点4. 画出函数之间的调用关系图。 图3.5 函数调用关系四、 调试分析 1， 实际完成的情况说明；实际完成了对二叉树的线索化，对线索二叉树的结点插入，删除，以及对二叉树的中序输出，每次操作之后以凹入表输出二叉树。2.程序的性能分析，包括时空分析； 二叉树使用链表占用的空间小，可以自动进行调整，所以空间复杂度低。操作过程中，代码尽量减少使用循环嵌套，所以时间复杂度较低，程序总体性能较优。3.上机过程中出现的问题及其解决方案； 上机过程中，插入，删除结点时，编译通过但是运行时出错，经过验证发现是因为二叉树建立后未进行线索化，而插入，删除使用的是加了线索的二叉树，所以在运行前判断二叉树是否进行了线索化。在使用凹入表时，不知道什么为凹入表，百度学习了发现与自己的实际情况不相同，经过画图去理解调整，完成了凹入表。在上机时发现屏幕过于混乱，采用了，每次操作清理屏幕的处理。4.程序中可以改进的地方说明；二叉树的凹入输出不够完善，可以加入一些符号去显示出树的双亲与孩子之间的关系。插入，删除的过程代码较复杂，可以尝试缩减冗余代码。在反复的操作过程中，程序可能出现bug崩溃。如果只有一个结点，删除结点会出现错误。程序只提供了运行时新建，在菜单中添加新建的选项。5.程序中可以扩充的功能及设计实现假想。 在程序中可以扩展数据类型的具体化，可以使程序与实际问题联系起来。在操作时有相同结点也能很好的去区分区别。可以建立多颗独立的二叉树。插入，删除的方式可以多样化。五、测试结果 图5.1 正确输入一颗二叉树图5.2 凹入输出二叉树图5.3 错误输入二叉树将导致第一个#后的内容失效六、 用户手册 图6.1 建立二叉树 图6.2 输入1选择中序线索化二叉树 图6.3 根据提示插入结点 图6.4 根据提示输入要删除的结点 图6.5 中序输出二叉树 图6.6 输入0结束程序七、体会与自我评价 本次课程设计，使我对数据结构这门课程有了更深入的理解。数据结构是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。我的课程设计题目是线索二叉树的运算。刚开始做这个程序的时候，感到完全无从下手，甚至让我觉得完成这次程序设计根本就是不可能的，于是开始查阅各种资料以及参考文献，之后便开始着手写程序，写完运行时有很多问题。特别是实现线索二叉树的删除运算时很多情况没有考虑周全，经常运行出现错误，但通过同学间的帮助最终基本解决问题。在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及编写大型程序的能力。培养了基本的、良好的程序设计技能以及合作能力。这次课程设计同样提高了我的综合运用所学知识的能力。并对c语言有了更深入的了解。数据结构是一门实践性很强的课程，上机实习是对学生全面综合素质进行训练的一种最基本的方法，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教学环节。上机实习一方面能使书本上的知识变“活”，起到深化理解和灵活掌握教学内容的目的；另一方面，上机实习是对学生软件设计的综合能力的训练，包括问题分析，总体结构设计，程序设计基本技能和技巧的训练。此外，还有更重要的一点是：机器是比任何教师更严厉的检查者。因此，在“数据结构”的学习过程中，必须严格按照老师的要求，主动地、积极地、认真地做好每一个实验，以不断提高自己的编程能力与专业素质。通过这段时间的课程设计，我认识到数据结构是一门比较难的课程。需要多花时间上机练习。这次的程序训练培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我适应实际，实践编程的能力。 总的来说，这次课程设计让我获益匪浅，对数据结构也有了进一步的理解和认识。八、 附录#include "stdio.h"#include "malloc.h"#include "windows.h"#define maxsize 20 /规定树中结点的最大数目typedef struct node /定义数据结构int ltag,rtag; /表示child域指示该结点是否孩子 char data; /记录结点的数据struct node *lchild,*rchild; /记录左右孩子的指针Bithptr; Bithptr *Qmaxsize; /建队，保存已输入的结点的地址 Bithptr *CreatTree() /建树函数，返回根指针char ch;int front,rear;Bithptr *T,*s;T=NULL;front=1;rear=0; printf("*n"); printf("n"); printf("ttt 线索二叉树的应用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;s->rchild=NULL;s->rtag=0;s->ltag=0;rear+; Qrear=s; /将结点地址加入队列中if(rear=1)T=s; /输入为第一个结点为根结点else if(s!=NULL&&Qfront!=NULL) /孩子和双亲结点均不是虚结点if(rear%2=0) Qfront->lchild=s; else Qfront->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;int m=0;void PreThread(Bithptr *r) /中序线索化算法，函数实现Bithptr *p;p=r; 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);m = 1;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) point2=SearchPre(point->rchild,child); if(point2!=NULL) return point2