數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)說(shuō)明書(shū)-線索二叉樹(shù)的應(yīng)用

PAGEPAGE1數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)說(shuō)明書(shū)

學(xué)院、系：軟件學(xué)院專(zhuān)業(yè)軟件工程設(shè)計(jì)題目：線索二叉樹(shù)的應(yīng)用需求分析既然題目要求要分別實(shí)現(xiàn)建立、刪除、和恢復(fù)線索化三種功能，建立和刪除一定是相互獨(dú)立的模塊，可分別建立兩個(gè)函數(shù)來(lái)實(shí)現(xiàn)功能。第三個(gè)功能是恢復(fù)線索，就要考慮這個(gè)線索恢復(fù)是怎樣的恢復(fù)過(guò)程，是怎樣恢復(fù)的?；謴?fù)線索是對(duì)二叉樹(shù)當(dāng)進(jìn)行了插入和刪除操作過(guò)程后，因?yàn)檫^(guò)程中有結(jié)點(diǎn)的變動(dòng)，而進(jìn)行的在操作結(jié)束以后對(duì)整個(gè)二叉樹(shù)的恢復(fù)線索，還是在實(shí)現(xiàn)插入和刪除的過(guò)程中就對(duì)操作的結(jié)點(diǎn)實(shí)現(xiàn)局部的恢復(fù)線索。從設(shè)計(jì)的目標(biāo)來(lái)說(shuō)應(yīng)該是要在刪除和插入的過(guò)程中實(shí)現(xiàn)對(duì)線索的恢復(fù)。而在線索二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)或刪除一個(gè)結(jié)點(diǎn)，一般情況下，這些操作有可能破壞原來(lái)已有的線索，因此，在修改指針時(shí)，還需要對(duì)線索做相應(yīng)的修改。概要設(shè)計(jì)首先建立二叉樹(shù)，然后對(duì)二叉樹(shù)進(jìn)行線索化。線索鏈表的結(jié)點(diǎn)結(jié)構(gòu)

線索鏈表中的結(jié)點(diǎn)結(jié)構(gòu)為：………. 中序線索二叉樹(shù)詳細(xì)設(shè)計(jì)#include"stdio.h"#include"malloc.h"#definemaxsize20//規(guī)定樹(shù)中結(jié)點(diǎn)的最大數(shù)目typedefstructnode{//定義數(shù)據(jù)結(jié)構(gòu) intltag,rtag;//表示child域指示該結(jié)點(diǎn)是否孩子 chardata;//記錄結(jié)點(diǎn)的數(shù)據(jù) structnode*lchild,*rchild;//記錄左右孩子的指針}Bithptr;Bithptr*Q[maxsize];//建隊(duì)，保存已輸入的結(jié)點(diǎn)的地址Bithptr*CreatTree(){//建樹(shù)函數(shù)，返回根指針 charch; intfront,rear; Bithptr*T,*s; T=NULL; front=1;rear=0;//置空二叉樹(shù)printf("***********************************\n");printf("**\n");printf("*課程設(shè)計(jì)題目：線索二叉樹(shù)的運(yùn)算。*\n");printf("**\n");printf("***********************************\n"); printf("創(chuàng)建二叉樹(shù)，請(qǐng)依次輸入，@表示虛結(jié)點(diǎn)，以#結(jié)束\n"); ch=getchar();//輸入第一個(gè)字符 while(ch!='#')//判斷是否為結(jié)束字符 { s=NULL; if(ch!='@')//判斷是否為虛結(jié)點(diǎn) { s=(Bithptr*)malloc(sizeof(Bithptr)); s->data=ch; s->lchild=NULL; s->rchild=NULL; s->rtag=0; s->ltag=0; } rear++; Q[rear]=s;//將結(jié)點(diǎn)地址加入隊(duì)列中 if(rear==1)T=s;//輸入為第一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn) else { if(s!=NULL&&Q[front]!=NULL)//孩子和雙親結(jié)點(diǎn)均不是虛結(jié)點(diǎn) 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)//中序線索化算法，函數(shù)實(shí)現(xiàn){ Bithptr*p; p=root;if(p){ PreThread(p->lchild);//線索化左子樹(shù) if(pre&&pre->rtag==1)pre->rchild=p;//前驅(qū)結(jié)點(diǎn)后繼線索化if(p->lchild==NULL) { p->ltag=1; p->lchild=pre; } if(p->rchild==NULL)//后繼結(jié)點(diǎn)前驅(qū)線索化 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);//如果是第一個(gè)結(jié)點(diǎn) if(f->ltag==1&&f->lchild!=NULL)printf("%c→【%c】",f->lchild->data,f->data);//如果此結(jié)點(diǎn)有前驅(qū)就輸出前驅(qū)和此結(jié)點(diǎn) if(f->ltag==1&&f->rtag==1&&f->rchild!=NULL)printf("→%c",f->rchild->data);//如果此結(jié)點(diǎn)有前驅(qū)也有后繼，就輸出后繼 elseif(f->rtag==1&&f->rchild!=NULL)printf("【%c】→%c",f->data,f->rchild->data);//如果沒(méi)有前驅(qū)，就輸出此結(jié)點(diǎn)和后繼 printf("\n"); if(f->ltag!=1)PrintIndex(f->lchild); if(f->rtag!=1)PrintIndex(f->rchild); }} Bithptr*SearchChild(Bithptr*point,charfindnode)//查找孩子結(jié)點(diǎn)函數(shù){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)//查找父親結(jié)點(diǎn)函數(shù){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("請(qǐng)輸入要插入的結(jié)點(diǎn)的信息:");scanf("%c",&c); scanf("%c",&c);p1=(Bithptr*)malloc(sizeof(Bithptr));//插入的結(jié)點(diǎn)信息 p1->data=c; p1->lchild=NULL; p1->rchild=NULL; p1->rtag=0; p1->ltag=0; printf("輸入查找的結(jié)點(diǎn)信息:");scanf("%c",&ch); scanf("%c",&ch); child=SearchChild(root,ch);//查孩子結(jié)點(diǎn)的地址 if(child==NULL){ printf("沒(méi)有找到結(jié)點(diǎn)\n"); system("pause"); return; } elseprintf("發(fā)現(xiàn)結(jié)點(diǎn)%c\n",child->data); if(child->ltag==0)//當(dāng)孩子結(jié)點(diǎn)有左孩子的時(shí)候 { p2=child; child=child->lchild; while(child->rchild&&child->rtag==0)//找到左子樹(shù)下，最右結(jié)點(diǎn) child=child->rchild; p1->rchild=child->rchild;//后繼化 p1->rtag=1; child->rtag=0; child->rchild=p1;//連接 p1->lchild=child;//前驅(qū)化 p1->ltag=1; } else//當(dāng)孩子結(jié)點(diǎn)沒(méi)有左孩子的時(shí)候 { p1->lchild=child->lchild;//前驅(qū)化 child->ltag=0; p1->ltag=1; child->lchild=p1; p1->rchild=child; p1->rtag=1; } printf("\n\t插入結(jié)點(diǎn)操作已經(jīng)完成，并同時(shí)完成了線索化的恢復(fù)\n");}Bithptr*DeleteNode(Bithptr*t){ Bithptr*child,*pre,*s,*q; charch; printf("輸入查找的結(jié)點(diǎn)信息:");ch=getchar(); ch=getchar(); child=SearchChild(t,ch);//查找該結(jié)點(diǎn)的孩子結(jié)點(diǎn) printf("發(fā)現(xiàn)結(jié)點(diǎn):%c\n",child->data); printf("ltag=%d,rtag=%d\n",child->ltag,child->rtag); if(NULL==child) { printf("沒(méi)有找到結(jié)點(diǎn):"); returnt; } if(child!=t) { pre=SearchPre(t,child); printf("發(fā)現(xiàn)結(jié)點(diǎn):%c\n",pre->data); } else//當(dāng)是頭結(jié)點(diǎn)的時(shí)候 if(child->ltag==1&&child->rtag==1)//沒(méi)有左右孩子 t=NULL; elseif(t->ltag==1&&t->rtag!=1)//有右孩子沒(méi)有左孩子 { t=child->rchild; child->rchild->lchild=NULL; free(child); returnt; }else if(t->ltag!=1&&t->rtag==1)//有左孩子沒(méi)有右孩子 { 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)//查找孩子左子樹(shù)的最右下結(jié)點(diǎn) s=s->rchild; q=child->rchild; while(q->lchild&&q->ltag!=1)//查找孩子右子樹(shù)的最左下結(jié)點(diǎn) q=q->lchild; s->rchild=child->rchild;//連接 s->rtag=0; q->lchild=s; free(child); returnt; } if(child==pre->lchild||child==pre)//是父親結(jié)點(diǎn)的左孩子 { if(1==child->ltag&&1==child->rtag)//孩子結(jié)點(diǎn)無(wú)左右 { 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)//孩子結(jié)點(diǎn)有左無(wú)右 { pre->lchild=child->lchild; s=child->lchild; while(s->rchild)//查找左子樹(shù)的最右下結(jié)點(diǎn) s=s->rchild; s->rchild=child->rchild; free(child); } elseif(1==child->ltag&&1!=child->rtag)//孩子結(jié)點(diǎn)有右無(wú)左 { 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)//孩子結(jié)點(diǎn)左右都有 { pre->lchild=child->lchild; s=child->rchild; while(s->lchild&&s->ltag!=1)//找到右子樹(shù)的最左下結(jié)點(diǎn) s=s->lchild; q=child->lchild; while(q->rchild&&q->rtag!=1)//找到左子樹(shù)下最右下結(jié)點(diǎn) q=q->rchild; q->rchild=child->rchild;//將孩子結(jié)點(diǎn)的右子樹(shù)接到左子樹(shù)下最右下結(jié)點(diǎn) q->rtag=0; s->lchild=q; free(child); } }else{if(child==pre->rchild)//是父親結(jié)點(diǎn)的右孩子 { if(1==child->ltag&&1==child->rtag)//孩子結(jié)點(diǎn)無(wú)左右 { 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)//孩子結(jié)點(diǎn)有左無(wú)右 { 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)//孩子結(jié)點(diǎn)有右無(wú)左 { 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)//孩子結(jié)點(diǎn)左右都有 { pre->rchild=child->rchild; s=child->rchild; while(s->lchild&&s->ltag!=1)//找到右子樹(shù)的最左下結(jié)點(diǎn) s=s->lchild; q=child->lchild; while(q->rchild&&q->rtag!=1)//找到左子樹(shù)下最右下結(jié)點(diǎn) q