數據結構課程設計報告---二叉排序樹實現集合的運算

1、<p>　　數據結構課程設計報告</p><p>　　設計題目 二叉排序樹實現集合的運算 </p><p>　　班 級 信息管理1班 </p><p>　　學 號 &

2、lt;/p><p><b>　　引言</b></p><p>　　數據結構是研究與數據之間的關系，我們稱這一關系為數據的邏輯結構，簡稱數據結構。當數據的邏輯結構確定以后，數據在物理空間中的存儲方式，稱為數據的存儲結構。相同的邏輯結構可以具有不同的存儲結構，因而有不同的算法。本次課程設計程序中的數據采用“樹形結構”作為其數據結構。而二叉排序樹又是一種特殊的二叉樹。本課程設中

3、的二叉排序樹是用來實現集合中的運算功能，一共要實現五項集合的基本的功能。它們分別是集合的元素判定，子集判定，交，并，差運算。實現這五項基本功能的目的是為了鞏固和運用理論知識、鍛煉實踐能力、構件合理知識結構和提高程序設計能力。</p><p><b>　　正文</b></p><p><b>　　1 需求分析</b></p><

4、p>　　1.1課程設計題目、任務及要求</p><p>　?。?） 用二叉排序樹實現集合的元素判定，子集判定，集合的交，并，差的運算； </p><p>　　（2） 集合的元素限整數；</p><p>　?。?） 程序運行時要先顯示題目，班級，學號，姓名，完成時間等信息。</p><p>　　1.2 課程設計思想</p>

5、<p>　　a.用二叉排序樹建立集合，然后用二叉排序樹的算法實現集合的元素判定，子集判定，集合的交并差的運算；可見，要想完成集合的這些算法，最主要運用到了二叉排序樹里面的查找算法，然后將數組與二叉排序樹結合起來，來實現這些算法。</p><p>　　b.查找函數采用遞歸的方式進行查找；</p><p>　　對二叉排序樹進行中序遍歷采用遞歸函數的方式：在根結點不為空的情況下，先

6、訪問左子樹，再訪問根結點，最后訪問右子樹。由于二叉排序樹自身的性質，左子樹小于根結點，而根結點小于右子樹，所以中序遍歷的結果是遞增的。</p><p><b>　　2 概要設計</b></p><p>　　2.1 對二叉排序樹的理解</p><p>　　二叉排序樹是一種動態(tài)數表。</p><p>　　二叉排序樹的定義：二

7、叉排序樹或者是一棵空樹，或者是一棵具有如下性質的二叉樹：</p><p>　?。ǎ保┟總€結點都有一個作為搜索依據的關鍵碼（key），所有結點的關鍵碼互不相同；</p><p>　?。ǎ玻┤羲淖笞訕浞强眨瑒t左子樹上所有結點的值均小于根結點的值；</p><p>　?。ǎ常┤羲挠易訕浞强?，則右子樹上所有結點的值均大于根結點的值；</p><p&g

8、t;　　(4) 左、右子樹本身又各是一棵；</p><p>　　（5）左、右子樹本身又各是一棵二叉排序樹。</p><p>　　2.2 建立二叉排序樹（二叉鏈表做存儲結構）</p><p>　　從空的二叉排序樹開始，經過一系列的查找插入操作以后，生成一棵二叉排序樹。</p><p>　　根據二叉排序樹的定義，建立一棵二叉排序樹的過程是按照待

9、排序序列元素的先后次序，不斷動態(tài)生成二叉樹的結點，逐個插入到二叉樹中。其過程可以描述為：</p><p>　　BSTree createBST(int *iArr)//建立集合二叉排序樹</p><p><b>　　{ </b></p><p>　　BSTree t=NULL; //根結點</p><p>　　KeyTy

10、pe key;</p><p><b>　　int i=0;</b></p><p>　　if(!*iArr)</p><p><b>　　{</b></p><p><b>　　cin>>key;</b></p><p>　　while(k

11、ey!=-1 && ++i<MaxElement) //輸入-1或輸入到最大個數止</p><p><b>　　{</b></p><p>　　(*iArr)++;iArr[*iArr] = key; //集合元素先在數組中存放</p><p><b>　　cin>>key;</b><

12、;/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=1;i<=*iArr;i++) //由數組形式 生成 二叉排序樹狀集合形式</p><p><b>　　{</b></p><p>　　in

13、sertBST(t,iArr[i]);</p><p><b>　　}</b></p><p><b>　　return t;</b></p><p><b>　　}</b></p><p>　　左、右子樹的插入方式與二叉排序樹的插入方式相同。</p><p

14、>　　不斷調用上述的插入過程，直到所有待排序序列均排入后，就形成一棵二叉排序樹。</p><p>　　由此可見，建立二叉排序樹就是多次調用二叉排序樹的插入算法。</p><p>　　2.3二叉排序樹的生成過程</p><p>　　二叉排序樹的生成，采用遞歸方式的邊查找邊插入的方式。如圖：</p><p>　　2.4中序遍歷二叉排序樹(中

15、序輸出集合，按從小到大的順序)</p><p>　　中序遍歷二叉樹算法的框架是：</p><p>　　若二叉樹為空，則空操作；否則</p><p><b>　　中序遍歷左子樹；</b></p><p><b>　　訪問根結點；</b></p><p><b>　　中

16、序遍歷右子樹。</b></p><p>　　中序遍歷二叉樹也采用遞歸函數的方式，先訪問左子樹，然后訪問根結點，最后訪問右子樹，直至所有的結點都被訪問完畢。</p><p><b>　　代碼如下：</b></p><p>　　void inorder_btree(BSTree root)// 中序遍歷打印二叉排序樹 </p>

17、;<p><b>　　{</b></p><p>　　BSTree p=root;</p><p>　　if(p!=NULL){</p><p>　　inorder_btree(p->left );</p><p>　　cout<<" "<<p->k

18、ey<<" ";</p><p>　　inorder_btree(p->right );</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　?。?詳細設計和實現</b></p&g

19、t;<p>　　3.1主要功能模塊設計</p><p><b>　　1.元素判定：</b></p><p>　　用查找的方法實現元素判定；</p><p>　　BSTree searchBST(BSTree t,KeyType key) </p><p><b>　　{ </b><

20、;/p><p>　　if(!t || key==t->key) return t; </p><p>　　if(key<t->key)</p><p>　　return searchBST(t->left,key);</p><p><b>　　else</b></p><p>

21、;　　return searchBST(t->right,key);</p><p><b>　　}</b></p><p>　　改為返回指針，未找到時返回空指針 找到時返回所在位置，先判是不是空指針，非空了再判是不是相等了。</p><p><b>　　2.子集判定：</b></p><p>

22、;　　不懂怎么一個一個的來訪問樹結點，只好使個偷懶的方法啦，轉成數組，再遍歷數組，老師，別介意哦；</p><p>　　只要在另一個集合中找到有沒有與這個集合相等的元素就ok了。函數如下：</p><p>　　int beyong(BSTree m,BSTree n) </p><p><b>　　{</b></p><p&

23、gt;　　int i,Array[MaxElement]={0}</p><p>　　inorder_btree2Arr(n,Array);</p><p>　　for(i=1;i<=*Array;i++)</p><p>　　if(!searchBST(m,Array[i])) return 0;</p><p><b>　

24、　return 1;</b></p><p><b>　　}</b></p><p>　　3.求并集：A+B=C</p><p>　　中序遍歷兩個集合，先把A集合賦給C，然后把集合B的元素插入到C中就行了。</p><p>　　void combineTree(BSTree A,BSTree B,BSTree

25、 &C)</p><p><b>　　{</b></p><p>　　int i,Array[MaxElement]={0};</p><p>　　inorder_btree2Arr(A,Array);</p><p>　　C = createBST(Array);</p><p>　　A

26、rray[0]=0;</p><p>　　inorder_btree2Arr(B,Array);</p><p>　　for(i=1; i<=*Array; i++) insertBST(C,Array[i]);</p><p><b>　　}</b></p><p>　　4.交集：A∩B=C</p>

27、<p>　　用查找的方法在B中查找A中的每一個元素，把查找到得元素構成一個新的新的集合C。</p><p>　　void joinTree(BSTree A,BSTree B,BSTree &C) </p><p><b>　　{</b></p><p>　　int i,Array[MaxElement]={0},Array

28、1[MaxElement]={0};</p><p>　　inorder_btree2Arr(B,Array);</p><p>　　for(i=1;i<=*Array;i++)</p><p>　　if(searchBST(A,Array[i])){Array1[0]++; Array1[Array1[0]] = Array[i];}//求相交的所有元素&l

29、t;/p><p>　　if(Array1[0]) C = createBST(Array1); //結果不空時 再組一個集合</p><p>　　else C=NULL;</p><p><b>　　}</b></p><p>　　5.求差集：A-B=C</p><p>　　中序遍歷A中的元素，在B中

30、查找到這些元素，求出所有不屬于B中的元素，在創(chuàng)建一顆二叉排序樹集合C，把這些有元素放入到C中即可。</p><p>　　void differencedTree(BSTree A,BSTree B,BSTree &C) </p><p><b>　　{</b></p><p>　　int i,Array[MaxElement]={0},

31、Array1[MaxElement]={0};</p><p>　　inorder_btree2Arr(A,Array);</p><p>　　for(i=1;i<=*Array;i++)</p><p>　　if(!searchBST(B,Array[i])){Array1[0]++; Array1[Array1[0]] = Array[i];}</p

32、><p>　　if(Array1[0]) C = createBST(Array1); //結果不空時 再組一個集合</p><p>　　else C=NULL;</p><p><b>　　}</b></p><p><b>　　3.2主程序設計</b></p><p>　　根

33、據題目要求，先輸出題目，班級，姓名，日期等等；</p><p>　　然后實現題目的所要的一系列函數，調用著希望函數，實現所要求的集合的功能；</p><p>　　寫了一個while循環(huán)，能夠使程序反復執(zhí)行下去。</p><p><b>　　4 程序調試及操作</b></p><p>　　經過幾天的反復調試和修改后，程序得

34、以正常的運行，并實現所要求的函數的功能。</p><p><b>　　程序運行結果如下：</b></p><p>　　姓名，題目等的顯示:</p><p>　　集合的輸入與中序遍歷輸出： </p><p><b>　　元素判定：</b></p><p>　　子集判定，交，并差

35、的運算：</p><p><b>　　三．體會與總結</b></p><p>　　這次課程設計使我對數據結構認識深刻了許多，其中最深刻的是我理解了二叉排序樹的含義和操作，同時也加深了對二叉樹的理解。本課程設計運用了二叉排序樹的創(chuàng)建、中序遍歷、查找的功能。在進行搜索時，可以采用更好的搜索結構即動態(tài)搜索結構。在此次課設中，我遇到最大的一個問題是如何創(chuàng)建二叉排序樹（還要結合

36、不能提的要求來建立）以及怎樣把集合與二叉排序樹里聯系起來實現集合的一系列運算。通過查找資料，請教同學和老師，終于把它解決了。通過這一周課設，我已經學會用順序表和二叉鏈表存儲結構實現對二叉排序樹的創(chuàng)建、中序遍歷、查找、刪除等操作。</p><p>　　但我同時也發(fā)現了自己許多不足之處。在這次可設中我同時用到了c語言和c++，雖說有點不倫不類，但這更鞏固了自己的C和C++的知識，呵呵，其實我知道這樣不好，算是對自己的

37、鼓勵吧。</p><p>　　首先，對數據結構的掌握不夠，雖然完成了課設，但是只用到了基本的結點及操作，在數據結構的選擇上避重就輕，覆蓋面較小，不能很好的體現各種數據結構的掌握度，同時也缺少了適當的鍛煉，在這方面還需要去提高。</p><p>　　其次，在程序整體的設計上還不夠完整，各模塊可以適當增加內容，界面還可以更加人性化，這樣整個程序才具有更強的美觀性與實用性。</p>

38、<p>　　總而言之，這次課程設計給了我很大啟發(fā)，我明白了，不管遇到什么困難，只</p><p>　　抓住根源，不氣餒，從不同方面，不同角度去攻破它，終究會成功，生活也是如此</p><p>　　總而言之，這次課程設計給了我很大啟發(fā)，我明白了，不管遇到什么問題，只要抓住根源，不氣餒，從不同方面去攻破它，終究會成功，生活也是如此，風雨之后總會見彩虹！</p><

39、;p><b>　　四．參考文獻</b></p><p>　　1.曲朝陽等.數據結構.中國電力出版社,2007</p><p>　　2.唐發(fā)根.數據結構教程（第二版）.北京航空航天大學出版社,2004</p><p>　　3.潭浩強.程序設計.北京：清華大學出版社，2000</p><p>　　4.嚴蔚敏，吳偉民.數

40、據結構.北京：清華大學出版,2001</p><p>　　5.殷人昆.數據結構.北京：清華大學出版社，2004</p><p>　　6.王曉東.數據結構與算法設計．電子工業(yè)出版社 2002</p><p>　　7.陳慧南．數據結構與算法 C++ 語言描述．高等教育出版社 2005</p><p>　　8.竇延平等.數據結構與算法 C++．上海