數據結構與算法課程設計--線索二叉樹的基本操作

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：22 大?。?55.00KB 人氣指數：12 舉報 版權申訴

已閱讀1頁，還剩21頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數學與計算機學院　　課程設計說明書　　課程名稱: 數據結構與算法課程設計 　　課程代碼: 　　題目: 線索二

2、叉樹的基本操作 　　年級/專業(yè)/班: 2012級軟件工程4班 　　學生姓名: 吳海燕 　　學號: 　　開始

3、時間: 2013 年 12 月 18 日　　完成時間: 2013 年 12 月 28 日　　課程設計成績：　　指導教師簽名：年月日　　目錄

4、　　1 需求分析1　　1.1任務與分析1　　1.2測試數據2　　2 概要設計3　　2.1

5、模塊劃分3　　2.2模塊中的層次圖3　　3　詳細設計4　　3.1結構體設計4　　3.2創(chuàng)建二叉樹4　　3.3二叉樹線索化5　　3.4二叉

6、樹中插入結點6　　3.5刪除結點函數8　　3.6查找前驅后繼函數11　　4 調試分析12　　5　用戶使用說明12　　6　測試結果12</

7、p>　　6.1新建二叉樹12　　6.2中序遍歷13　　6.3查找前驅13　　6.4查找后繼14　　6.5刪除結點14　　6.6插入左孩子15　　6.

8、7插入右孩子15　　6.8退出16　　結論17　　致謝18　　參考文獻19&l

9、t;p>　　摘要 　　首先是對需求分析的簡要闡述，說明系統(tǒng)要完成的任務和相應的分析，并給出測試數據。其次是概要設計，說明模塊的劃分以及模塊間的層次關系，然后是詳細設計，描述實現(xiàn)概要設計中定義的基本功操作和所有數據類型，以及函數的功能及代碼實現(xiàn)。再次是對系統(tǒng)的調試分析說明，以及遇到的問題和解決問題的方法。然后是用戶使用說明書的闡述，然后是測試的數據

10、和結果的分析，最后是對本次課程設計的結論。　　關鍵詞：線索化,中序遍歷,插入，刪除，查找　　引言　　數據結構是計算機專業(yè)重要的專業(yè)基礎課程與核心課程之一，在計算機領域應用廣泛，計算機離不開數據結構。數據結構課程設計為了能使我們掌握所學習的知識并有應用到實際的設計中的能力，

11、對于掌握這門課程的學習方法有極大的意義。本課程設計的題目為“線索二叉樹的基本操作”，完成將二叉樹轉化成線索二叉樹，采用中序線索二叉樹的操作。本課程設計采用的編程環(huán)境為Microsoft Visual Studio 2008。　　1 需求分析 　　當用二叉鏈表作為二叉樹的存儲結構時，因為每個結點中只有指向其左、右兒子結

12、點的指針，所以從任一結點出發(fā)只能直接找到該結點的左、右兒子。在一般情況下靠它無法直接找到該結點在某種遍歷序下的前驅和后繼結點。如果在每個結點中增加指向其前驅和后繼結點的指針，將降低存儲空間的效率。　　我們可以證明：在n個結點的二叉鏈表中含有n+1個空指針。因為含n個結點的二叉鏈表中含有2n個指針，除了根結點，每個結點都有一個從父結點指向該結點的指針，因此一共使用了n-1個指針，所以在n個結點的二

13、叉鏈表中含有n+1個空指針。　　因此可以利用這些空指針，存放指向結點在某種遍歷次序下的前驅和后繼結點的指針。這種附加的指針稱為線索，加上了線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹(Threaded Binary Tree)。根據線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。　　1.1任

14、務與分析 　　任務：　　建立一棵二叉樹（用戶自行輸入二叉樹，用“#”表示空格，按回車鍵結束），將其線索化，并實現(xiàn)以下功能：　　1)遍歷二叉樹（本程序使用中序遍歷方法）　　2)在二叉樹中插入一個結點

15、;　　3)刪除二叉樹的某個結點　　4)查找某個結點的前驅　　5)查找某個結點的后繼　　分析：　　該任務是關于線索二叉樹的運算，其中的基本運算應基于二叉樹，但又有所不同，首先應了解的問題有：

16、　　1)線索二叉樹是如何建立的，是通過二叉樹來實現(xiàn)線索化，還是直接進行線索化的輸入。若由二叉樹建立而來，該二叉樹應如何輸入，對于具體的二叉樹應該使初使用者明白使用的格式。　　2)該程序重點內容是有關于二叉樹的插入、刪除和查找前驅后繼，在進行具體的操作時，規(guī)則是什么，依照什么原則。　　3)對于插入、刪除、查找前驅后繼等，其結果是否符合預訂

17、的目標，須由自己判定。　　1.2測試數據 　　測試數據：ABD#G###CE##F##　　圖1-1 測試數據　　2 概要設計 <

18、;p>　　2.1 模塊劃分　　二叉樹的建立函數：Creat(ThrNode<T> *bt)　　中序遍歷函數：void InOrder()　　中序線索化函數：void ThrBiTree(ThrNode<T>*bt)<

19、p>　　查找結點函數：ThrNode<T>*locate(ThrNode<T>*bt,T x)　　插入結點函數：void InsertLeft(ThrNode<T>*s,T x,T y)　　void InsertRight(ThrNode<T>*s,T x,T y)<p&

20、gt;　　刪除函數：void Delete(ThrNode<T>*child ,ThrNode<T>*F)　　查找結點的前驅、后繼函數：ThrNode<T>*Former(ThrNode<T>*p)　　ThrNode<T>*Next(ThrNode<T>*p)

21、　　2.2模塊中的層次圖　　圖2-1層次模塊圖　　3　詳細設計　　3.1結構體設計　　二叉樹的遍歷本質上是將一個復雜的非線性結構轉換為線性結

22、構，使每個結點都有了唯一前驅和后繼（第一個結點無前驅，最后一個結點無后繼）。對于二叉樹的一個結點，查找其左右子女是方便的，其前驅后繼只有在遍歷中得到。為了容易找到前驅和后繼，有兩種方法。一是在結點結構中增加向前和向后的指針，這種方法增加了存儲開銷，不可??；二是利用二叉樹的空鏈指針?，F(xiàn)將二叉樹的結點結構重新定義如下：　　struct ThrNode<

23、b>　　{　　T data;　　ThrNode<T> *lchild, *rchild;　　int ltag,rtag;　　};<

24、;p>　　其中：ltag=0 時 lchild指向左子女；　　ltag=1 時 lchild指向前驅； 　　rtag=0 時 rchild指向左子女； 　　rtag=1 時 rchild指向后繼； 　　以這種結點結構構成的二叉鏈表作為二叉樹的存儲結構，叫做線索鏈表

25、，指向前驅和后繼的指針叫線索，加上線索的二叉樹叫線索二叉樹，對二叉樹進行某種形式遍歷使其變?yōu)榫€索二叉樹的過程叫線索化。學習線索化時，有三點必須注意：一是何種“序”的線索化，是先序、中序還是后序；二是要“前驅”線索化、“后繼”線索化還是“全”線索化（前驅后繼都要）；三是只有空指針處才能加線索。　　3.2創(chuàng)建二叉樹

26、采用遞歸算法實現(xiàn)二叉樹的建立，按照某種次序依次輸入二叉樹中結點，用“#”表示結束標志。　　template<class T>　　ThrNode<T>*MyTree<T>::Creat(ThrNode<T> *bt) //建立一棵線索二叉樹　　{&

27、lt;/b>　　char ch;　　cout<<"請輸入一個結點：";　　cin>>ch;　　if(ch=='#') bt=NUL

28、L; //建立一棵空樹　　else　　{　　bt=new ThrNode<T>;　　bt->data=ch; //生成一個結點<p&

29、gt;　　bt->ltag=0; //左標志置為　　bt->rtag=0; //右標志置為　　bt->lchild=Creat(bt->lchild); //遞歸建立左子樹　　bt->rchild=Creat(bt->rchild); //遞歸建立右子樹

30、　　}　　return bt;　　}　　3.3二叉樹線索化　　按照一定的順序來進行線索化。要實現(xiàn)線索化，就要知道結

31、點*pre是結點*p的前驅，而*p是*pre的后繼。這樣，當遍歷到結點*p時，可以進行，若*p有空指針域，則將相應的標志置1；若*p的左線索標志已經建立（p->ltag==1）,則可使其前驅線索化，令p->lchild=pre;若*pre的右線索標志已經建立（pre->rtag==1），則可使其后繼化，令pre->rchild=p;　　template<class

32、T> //中序線索化鏈表　　void MyTree<T>::ThrBiTree(ThrNode<T> *bt)　　{　　if(bt==NULL)　　return;&

33、lt;/p>　　ThrBiTree(bt->lchild);　　if(bt->lchild==NULL) //對bt的左指針進行處理　　{　　bt->ltag=1;　　bt->lc

34、hild=pre; //設置pre的前驅線索　　}　　if(bt->rchild==NULL) //對bt的右指針進行處理　　bt->rtag=1;　　if(pre!=NULL&&pre->rta

35、g==1) //設置pre的后繼線索　　pre->rchild=bt;　　pre=bt;　　ThrBiTree(bt->rchild);　　}

36、　　3.4二叉樹中插入結點　　在樹中插入一個結點，就必須要以一定的規(guī)則來進行插入。首先要找到待插入結點的父結點，然后選擇是左孩子還是右孩子插入，再看要插入的位置是否已經有其他結點，若有，則將要插入的結點作為該結點的前驅插入樹中，若沒有則直接插入。　　template<class T> //插入左孩子

37、;　　void MyTree<T>::InsertLeft(ThrNode<T>*s,T x,T y)　　{　　ThrNode<T> *newL,*t;//newL是待插入結點,*t是*s的前驅結點　　s=locate(s,x);</

38、p>　　if(s==0)　　{　　cout<<"插入出錯！"<<endl;　　return;<p&

39、gt;　　}　　newL=new ThrNode<T>;　　newL->data=y;　　newL->lchild=NULL;　　newL->rchild=NULL;<p&g

40、t;　　if(s->ltag==1)　　{　　t=s->lchild; //記住s的前驅結點，作為newL的前驅　　newL->lchild=t; //將待插入結點前驅化　　newL->ltag=1;&l

41、t;/p>　　s->lchild=newL; //將待插入結點插入，作為s的左孩子　　s->ltag=0;　　newL->rchild=s; //將插入結點后繼化　　newL->rtag=1;

42、　　}　　else　　{　　for(t=s->lchild;t->rtag==0;)// 確定*s的前驅結點　　t=t->rchild;// *s的前驅*t是

43、*s左孩子的最右下方的結點　　t->rchild=newL;// 后繼化　　newL->ltag=0;　　newL->lchild=s->lchild;//將插入結點前驅化　　}<

44、p>　　s->ltag=0;　　s->lchild=newL;// 將待插入結點插入，作為s的左孩子　　newL->rtag=1;　　newL->rchild=s;// 將插入結點后繼化　　}</p

45、>　　template<class T> //插入右孩子　　void MyTree<T>::InsertRight(ThrNode<T>*s,T x,T y)　　{　　ThrNode<T> *n

46、ewR,*t;//newR是待插入結點,*t是*s的后繼結點　　s=locate(s,x);　　if(s==0)　　{　　cout<<"插入出錯！";</p

47、>　　return;　　}　　newR=new ThrNode<T>;　　newR->data=y;　　newR->lchild=NULL;&l

48、t;/p>　　newR->rchild=NULL;　　if(s->rtag==1)　　{　　t=s->rchild; //記住s的后繼結點，作為newR的后繼　　newR->

49、rchild=t; //將待插入結點后繼化　　newR->rtag=1;　　s->rchild=newR; //將待插入結點插入，作為s的右孩子　　s->rtag=0;　　newR->lchild=s; //將插入點前驅化</

50、p>　　newR->ltag=1;　　}　　else　　{　　for(t=s->rchild;t->lt

51、ag==0;)// 確定*s的后繼結點　　t=t->lchild;// *s的后繼*t是*s右孩子的最左下方的結點　　t->lchild=newR;//前驅化　　newR->rtag=0;　　newR->rchild=s->rchild;//

52、 s原來的后繼作為插入點的右孩子　　　}　　s->rtag=0;　　s->rchild=newR;// 將待插入結點插入，作為s的右孩子　　newR->ltag=1;　　ne

53、wR->lchild=s;// 插入點前驅化　　　}　　3.5刪除結點函數　　要在樹中刪除一個結點，也要考慮不同的情況。在刪除結點前要先找到該結點和它的父結點，然后再進行刪除操作。<b

54、>　　刪除的具體情況：　　1).當結點是父親結點的左孩子時 　　若孩子結點沒有左右孩子：則直接刪除； 　　若孩子結點有左孩子沒右孩子：則將孩子結點的左孩子給父親結點的左孩子； 　　若孩子結點有右孩子沒左孩子：則將孩子

55、結點的右孩子給父親結點的左孩子；4.若孩子結點左右孩子都有：將左孩子上提，孩子結點的左子樹的右子樹接到孩子結點的右子樹的最左下結點的左子樹，再將孩子結點的右子樹接到孩子結點左子樹的右子樹。 　　2).當結點是父親結點的右孩子: 　　1.若孩子結點沒有左右孩子：則直接刪除； 　　2.若

56、孩子結點有左孩子沒右孩子：則將孩子結點的左孩子給父親結點的右孩子；　　3.若孩子結點有右孩子沒左孩子：則將孩子結點的右孩子給父親結點的右孩子；　　4.若孩子結點左右孩子都有：將右孩子上提，將孩子結點的右子樹的左子樹接到孩子結點的左子樹的最右下結點的右子樹，再將孩子結點的左子樹接到孩子結點右子樹的左子樹。　　tem

57、plate<class T>//刪除結點　　void MyTree<T>::Delete(ThrNode<T>*child ,ThrNode<T>*F)//child為待刪除的結點，F(xiàn)是child的父結點　　{　　ThrNode

58、<T>*s;　　s=0;　　if(child==F->lchild||child==F)//是父親結點的左孩子　　{　　if(child->ltag==1&&

59、;child->rtag==1)//孩子結點左右為空　　{　　F->lchild=child->lchild;//child結點后繼指向F，只要保存前驅　　F->ltag=1;　　}</

60、b>　　else if(child->ltag==0&&child->rtag==1)//孩子結點有左孩子無右孩子　　{　　F->lchild=child->lchild;//把child左孩子向上提,即刪除child</p

61、>　　s=child->lchild;　　while(s->rchild)//查找child左孩子最右下結點　　s=s->rchild;　　s->rchild=child->rchild;//后繼化

62、;　　}　　else if(child->ltag==1&&child->rtag==0)//孩子結點有右孩子無左孩子　　{　　F->lchild=child->rchild;//把右孩子上提，即刪除child<

63、;/p>　　s=child->rchild;　　while(s->lchild)//查找child右孩子的最左下結點　　s=s->lchild;　　s->lchild=child->lchild;//前驅化<

64、b>　　}　　else if(child->ltag==0&&child->rtag==0)//孩子結點左右孩子都有　　{　　ThrNode<T>*q;　　F->

65、lchild=child->lchild;//將child左孩子上提　　s=child->rchild;　　while(s->lchild)//查找child右孩子的最左下結點　　s=s->lchild;　　s->lchild=child-&

66、gt;lchild->rchild;//若child->lchild右子樹非空，把child左孩子的右子樹接到右子樹的最左下結點　　if(child->lchild->rtag==0)//child->lchild右子樹非空　　s->ltag=0;　　q=child->l

67、child;　　while(q->rchild!=NULL)　　q=q->rchild;　　q->rchild=s;//把q的后繼指到s上　　child->lchild->rchild=child->rchild;//設置child左孩

68、子的右子樹　　child->lchild->rtag=0; 　　}　　}　　if(child==F->rchild||child==F)//是父親結點的右孩子

69、;　　{　　if(child->ltag==1&&child->rtag==1)//孩子結點沒有左右孩子　　{　　F->rchild=child->rchild;//child

70、的后繼為空　　F->rtag=1;　　}　　else if(child->ltag==0&&child->rtag==1)//孩子結點有左孩子，無右孩子　　{&l

71、t;/p>　　F->rchild=child->lchild;//將孩子結點的右孩子向上提　　s=child->lchild;　　while(s->rchild)//查找孩子結點左子樹的最右結點　　s=s->rchild;<p

72、>　　s->rchild=child->rchild;//后繼化　　}　　else if(child->ltag==1&&child->rtag==0)//孩子結點有右孩子無左孩子　　{

73、　　F->rchild=child->rchild;//將孩子結點的右孩子向上提　　s=child->rchild;　　while(s->lchild)//查找孩子結點右子樹的最左結點　　s=s->lchild;<

74、;p>　　s->lchild=F;//前驅化　　}　　else if(child->ltag==0&&child->rtag==0)//孩子結點既有左孩子又有右孩子　　{&l

75、t;p>　　ThrNode<T>*q;　　F->rchild=child->rchild;//將child右孩子上提　　s=child->lchild;　　while(s->rchild)//查找child左孩子的最右下結點　　s

76、=s->rchild;　　s->rchild=child->rchild->lchild;//若child->rchild右子樹非空，把child右孩子的左子樹接到左子樹的最右下結點　　if(child->rchild->ltag==0)//child->rchild的左子樹非空&l

77、t;p>　　s->rtag=0;　　q=child->rchild;　　while(q->lchild!=NULL)　　q=q->lchild;　　q->lchild=s;//把q的后繼指到s上

78、　　child->rchild->lchild=child->lchild;//設置child右孩子的左子樹　　child->rchild->ltag=0; 　　}　　}<p&

79、gt;　　} 　　3.6查找前驅后繼函數　　前驅和后繼就是某個結點左右指針指向的結點，查找前驅和后繼與二叉樹線索化得次序有關。　　template<class T>　　ThrNode<T>*MyTre

80、e<T>::Former(ThrNode<T>*p)　　{　　ThrNode<T> *q;//p為待查找結點，q為p的前驅　　if(p==0)return 0;　　q=0;<

81、/b>　　if(p->ltag==1)　　q=p->lchild; //左標志為，可直接得到前驅結點　　else　　{　　q=p-&

82、gt;lchild; //工作指針q指向結點p的左孩子　　while(q->rtag==0)　　q=q->rchild; //查找最右下結點　　}　　return q;</

83、p>　　}　　template<class T>　　ThrNode<T>*MyTree<T>::Next(ThrNode<T>*p)　　{

84、　　ThrNode<T> *q;//p為待查找結點，q為p的后繼　　if(p==0) return 0;　　q=0;　　if(p->rtag==1)　　q=p->rchild; //右標

85、志為，可直接得到后繼結點　　else　　{　　q=p->rchild; //工作指針q指向結點p的右孩子　　while(q->ltag==0)<p&g

86、t;　　q=q->lchild; //查找最左下結點　　}　　return q;　　}　　4 調試分析</

87、p>　　在上面給出測試的所有數據，按照上面的數據錄入即可。　　問題：在測試過程中沒有給測試者提供相關的錄入信息要求，導致錄入要求不合格，程序不能正常運行。　　解決方法：經過添加錄入信息提示可解決這個問題。　　5　用戶使用說明

88、　　直接按照菜單上面的提示從鍵盤上錄入數據即可，不需要過多的操作。該軟件操作界面簡潔美觀，操作簡單，適合用戶使用。　　6　測試結果　　6.1新建二叉樹　　圖6-1 構建二叉樹&l

89、t;b>　　6.2中序遍歷　　圖6-2中序遍歷　　6.3查找前驅　　圖6-3 查找指定結點的前驅　　6.4查找后繼

90、;　　圖6-4 查找指定結點的后繼　　6.5刪除結點　　圖6-5 刪除一個結點　　6.6插入左孩子　　圖6-6 在左子樹插入一個結點

91、;　　6.7插入右孩子　　圖6-7 在右子樹插入一個結點　　6.8退出　　圖6-8 退出系統(tǒng)　　結論 </p

92、>　　本次課程設計“線索二叉樹的基本操作”按照任務書相應的要求成功的完成了任務，由于本課程設計涉及中序的線索化以及相應的相關插入刪除等操作，因此對算法的設計以及相關函數的調用要求很高，需要通過反復的查看相關書籍才能完成。　　當我開始編寫這個題目的代碼的時候，我覺得難度相當的大。成天的抱怨我怎么選這么難的題目。在我寫完所有代碼的時候，我發(fā)現(xiàn)問題太多了。最開始連一棵樹都不

93、能構造出來程序就停止工作，然后經過一歩一步的調試，終于改對了，卻發(fā)現(xiàn)每個功能函數都不能實現(xiàn)，都存在各種各樣的問題。很多時候不知道怎么改，而且老師同學一時半會兒也講不清楚，因為他們不知道我的程序具體是怎樣寫的。只有幫我調試，然后慢慢糾錯。即使這樣，好多問題依然沒有得到解決。頓時，心情變得極為糟糕，曾有過放棄的念頭。但是，看見別的同學都能耐心的做，而且我害怕掛科，所以我只能繼續(xù)耐心的做下去。還好皇天不負苦心人，終于讓我的付出有了收獲。<

94、;/p>　　我覺得編程邏輯思維很重要，在實現(xiàn)每一個功能的時候，要先想清楚具體怎么做，然后再編寫代碼。在編程的時候應該每編寫出一個功能，要待其實現(xiàn)后再去編寫下一個功能。不能把所有功能函數全部寫出來再來慢慢改錯、糾正，這樣會浪費更多的時間。　　通過這次課程設計，我學會了自己主動去學習一些東西，而且也漸漸明白了數據結構這門課的實用性，雖然我覺得有的地方很難，需要向老師同學請

95、教，但也慢慢對軟件工程產生了興趣。　　致謝 　　在這次課程設計過程中，首先感謝輔導老師對我的指導；同時也感謝耐心幫助我的同學。我也感謝自己，感謝自己沒有放棄，感謝中堅持到了最后；感謝這次數據結構與算法課程設計，我學到了很多，感謝這次實訓。　　參考文獻 &

96、lt;/b>　　[1] 嚴蔚敏，吳偉民.數據結構.清華大學出版社出版。 　　[2] 嚴蔚敏，吳偉民. 數據結構題集(C語言版) .清華大學出版社.2003年5月。　　[3]唐策善，李龍澎.數據結構(作C語言描述) .高等教育出版社.2001年9月　　[4] 朱戰(zhàn)立

97、.數據結構(C++語言描述)（第二版本）.高等出版社出版.2004年4月。　　[5]胡學鋼.數據結構(C語言版) .高等教育出版社.2004年8月。　　[6]陳明編著.數據結構.北京：清華大學出版社，2005年。　　[7]王紅梅，胡明，王濤編著（C++版）(第2版).清華大學出版社.2011年6月</p&g

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數據結構與算法課程設計--線索二叉樹的基本操作

文檔簡介

溫馨提示

最新文檔

評論

數據結構與算法課程設計--線索二叉樹的基本操作

文檔簡介

溫馨提示

最新文檔

評論

免費下載