数据结构与算法课程设计说明书-线索二叉树的应用

PAGEPAGE1数据结构与算法课程设计说明书

学院、系：软件学院专业软件工程设计题目：线索二叉树的应用需求分析既然题目要求要分别实现建立、删除、和恢复线索化三种功能，建立和删除一定是相互独立的模块，可分别建立两个函数来实现功能。第三个功能是恢复线索，就要考虑这个线索恢复是怎样的恢复过程，是怎样恢复的。恢复线索是对二叉树当进行了插入和删除操作过程后，因为过程中有结点的变动，而进行的在操作结束以后对整个二叉树的恢复线索，还是在实现插入和删除的过程中就对操作的结点实现局部的恢复线索。从设计的目标来说应该是要在删除和插入的过程中实现对线索的恢复。而在线索二叉树中插入一个结点或删除一个结点，一般情况下，这些操作有可能破坏原来已有的线索，因此，在修改指针时，还需要对线索做相应的修改。概要设计首先建立二叉树，然后对二叉树进行线索化。线索链表的结点结构

线索链表中的结点结构为：………. 中序线索二叉树详细设计#include"stdio.h"#include"malloc.h"#definemaxsize20//规定树中结点的最大数目typedefstructnode{//定义数据结构 intltag,rtag;//表示child域指示该结点是否孩子 chardata;//记录结点的数据 structnode*lchild,*rchild;//记录左右孩子的指针}Bithptr;Bithptr*Q[maxsize];//建队，保存已输入的结点的地址Bithptr*CreatTree(){//建树函数，返回根指针 charch; intfront,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; 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; elseQ[front]->rchild=s; if(rear%2==1)front++; } ch=getchar(); } returnT;}voidInorder(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;voidPreThread(Bithptr*root)//中序线索化算法，函数实现{ 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); }}voidPrintIndex(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);//如果此结点有前驱也有后继，就输出后继 elseif(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); }} Bithptr*SearchChild(Bithptr*point,charfindnode)//查找孩子结点函数{Bithptr*point1,*point2;if(point!=NULL){if(point->data==findnode)returnpoint;else if(point->ltag!=1){point1=SearchChild(point->lchild,findnode);if(point1!=NULL)returnpoint1;}if(point->rtag!=1){point2=SearchChild(point->rchild,findnode);if(point2!=NULL)returnpoint2;}returnNULL; }elsereturnNULL;}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))returnpoint;//找到则返回else if(point->ltag!=1) { point1=SearchPre(point->lchild,child); if(point1!=NULL) returnpoint1; }if(point->rtag!=1) { point2=SearchPre(point->rchild,child); if(point2!=NULL) returnpoint2; }returnNULL; }elsereturnNULL;}voidInsert(Bithptr*root){ charch; charc; 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; } elseprintf("发现结点%c\n",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("\n\t插入结点操作已经完成，并同时完成了线索化的恢复\n");}Bithptr*DeleteNode(Bithptr*t){ Bithptr*child,*pre,*s,*q; charch; printf("输入查找的结点信息:");ch=getchar(); ch=getchar(); child=SearchChild(t,ch);//查找该结点的孩子结点 printf("发现结点:%c\n",child->data); printf("ltag=%d,rtag=%d\n",child->ltag,child->rtag); if(NULL==child) { printf("没有找到结点:"); returnt; } if(child!=t) { pre=SearchPre(t,child); printf("发现结点:%c\n",pre->data); } else//当是头结点的时候 if(child->ltag==1&&child->rtag==1)//没有左右孩子 t=NULL; elseif(t->ltag==1&&t->rtag!=1)//有右孩子没有左孩子 { t=child->rchild; child->rchild->lchild=NULL; free(child); returnt; }else if(t->ltag!=1&&t->rtag==1)//有左孩子没有右孩子 { t=child->lchild; child->lchild->rchild=NULL; free(child); returnt; }else if(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); returnt; } 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); } elseif(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); } elseif(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); } elseif(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); } elseif(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); } elseif(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); } elseif(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