數據結構課程設計----二叉樹平衡的判定

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

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

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

文檔簡介

1、　　數據結構與算法　　課程設計報告　　課程設計題目：二叉樹平衡的判定 　　專業(yè)班級：信息與計算科學1001班

2、 　　一、摘要：　　基于我們對C語言和數據結構的學習我們有能力編寫處理一些比較基本而又簡單的問題。在我們此題我們的目標就是任意給出一個二叉樹我們判斷是否為平衡的二叉樹。　　我們在學習計算機語言類的知識時當然要注重理論知識的學習，但是我們要明確我們學習

3、的是計算機語言，由于課程的性質就決定了我們必須將我們在課本中學到的知識在計算機上運行并且自己能編寫一些比較簡單的程序，這才是我們學習計算機語言的最終目的而不是滿足于理解一個理論會算一個題。因而我們將要抓住這樣一個鍛煉的機會　　所謂平衡二叉樹，它或者是一顆空樹或者是具有下列性質的二叉樹：它的左右子樹都是平衡二叉樹，且左右子樹的深度之差得絕對值不超過1。

4、在我們這個判定任意給定的二叉樹的題中。我們處理這道題的主要的思路是：首先按先序和中序或者按中序和后序的方式將我們所要判斷的二叉樹輸入進入，目的是要得到一個明確的二叉樹的結構準確的判斷二叉樹是否平衡。在我們判斷二叉樹的平衡中我們將分別考慮二叉樹左右子樹的是不是為平衡二叉樹，依次得到左右子樹的深度，判斷左右子樹的平衡性。　　在我們的設計思路中我們將用到不同的樹的遍歷方式。&l

5、t;p>　　二、問題重敘：　　平衡二叉樹的判斷，設計要求給定一個先序或者后序的遍歷結果，判斷其是否為二叉樹。　　問題分析：　　在處理二叉樹平衡的判斷的問題中。我們需要將分別考慮二叉樹的左右子樹的平衡問題只要左右子樹確定為平衡二叉樹，

6、而且左右子樹的深度的絕對值之差不大于1，那么我們得到的就是一顆平衡的二叉樹。　　我們將先通過前序和中序或者中序和后序將所要判斷的二叉樹輸入。建立一個明確的二叉樹在此基礎上判斷二叉樹是否為平衡二叉樹。　　我們先建立一個二叉樹并用前序和中序或者中序和后序遍歷的方式將我們輸入的樹的元素輸入得到一個明確的樹的結構。<

7、;b>　　三、流程圖如下：　　四、模塊分析：　　1、定義一個結構體存儲各節(jié)點的信息，并且用遞歸的方法存儲左右子樹的信息　　typedef struct BINTREE　　{

8、;　　char chData;　　struct BINTREE * pbLChild;　　struct BINTREE * pbRChild;　　} BinTree, * pBinTree;　　2、分別得到樹的深度以及左右子

9、樹的深度　　int BT_GetTreeDepth( pBinTree pbTree )　　{　　//存儲樹總的深度　　int iDepthTotal = 0;<p&

10、gt;　　//存儲左子樹的深度　　int iDepthLeft = 0;　　//存儲右子樹的深度　　int iDepthRight = 0;　　if ( pbTree == NULL )　　{

11、　　iDepthTotal = 0;　　}　　else　　{　　// 左孩子的深度<

12、p>　　iDepthLeft = BT_GetTreeDepth( pbTree->pbLChild );　　// 右孩子的深度　　iDepthRight = BT_GetTreeDepth( pbTree->pbRChild );　　// 去左右孩子深度的最大值，1代表著根節(jié)點 </p

13、>　　iDepthTotal = 1 + ( iDepthLeft > iDepthRight ? iDepthLeft : iDepthRight );　　}　　return iDepthTotal;　　}</b&g

14、t;　　3、判斷左右子樹是不是為平衡二叉樹　　bool BT_IsBalanceTree( pBinTree pbTree )　　{　　//如果樹不是空的

15、　　if( pbTree != NULL )　　{　　//存儲左孩子的深度　　int iLeftDepth = 0;　　//存儲右孩子的深度　　int iRightDepth = 0;<

16、/p>　　//得到左孩子的深度　　iLeftDepth = BT_GetTreeDepth( pbTree->pbLChild );　　//得到右孩子的深度　　iRightDepth = BT_GetTreeDepth( pbTree->pbRChild );</p&

17、gt;　　//判斷樹是不是平衡二叉樹平衡二叉樹的左右孩子的深度絕對值只差不大于　　if (( iLeftDepth - iRightDepth >= -1 ) && ( iLeftDepth - iRightDepth <= 1 ))　　{

18、　　// 判斷左子樹是不是平衡的　　BT_IsBalanceTree( pbTree->pbLChild );　　//判斷右子樹是不是平衡的　　BT_IsBalanceTree( pbTree->pbRChild );

19、}　　else　　{　　return false;　　}　　}</b&g

20、t;　　else　　{　　return false;　　}　　return true;<

21、;p>　　}　　4、輸入各節(jié)點元素　　bool BT_PreInToTree( pBinTree & pbTree, char * szInOrder, char * szPreOrder, int iInLeft, int iInRight, int iPreLe

22、ft, int iPreRight )　　BT_PreInToTree( pbTree->pbLChild, szInOrder, szPreOrder, iInLeft, iCurPos - 1, iPreLeft + 1, iPreLeft + iLegnthLeft );　　5、前序遍歷二叉樹</p

23、>　　void BT_PreOrder( pBinTree pbTree ) 　　{ 　　if ( pbTree != NULL )　　{　　// The preord

24、er traversal is, root, left child, right child　　printf( "%c ", pbTree->chData ); 　　BT_PreOrder ( pbTree->pbLChild );　　BT_PreOrder ( pbTree-&g

25、t;pbRChild );　　} 　　}　　6、后序遍歷二叉樹　　void BT_PostOrder( pBinTree pbTree )

26、;　　{ 　　if ( pbTree != NULL )　　{　　// The postorder traversal is, left child, right child, root<

27、;p>　　BT_PostOrder ( pbTree->pbLChild ) ;　　BT_PostOrder ( pbTree->pbRChild ) ; 　　printf( "%c ", pbTree->chData );　　}

28、　　}　　7、主函數　　void main()　　{　　char szPre [100] = "&quo

29、t;;　　char szMid [100] = "";　　char szPost [100] = "";　　pBinTree pbPreInTree;　　pBinTree pbPostInTree;<

30、;p>　?。?）選用前序和后序的輸出方式，并判斷是不是平衡二叉樹　　printf("請輸入前序序列:\n");　　scanf("%s",&szPre);　　printf( "請輸入中序序列:\n");

31、;　　scanf("%s",&szMid);　　bool bCorrect = BT_PreInToTree( pbPreInTree, szMid, szPre, 0, strlen(szMid)-1, 0, strlen(szPre)-1 );　　if ( bCorrect )

32、{printf("該樹的后序序列為：\n");　　BT_PostOrder( pbPreInTree );　　if ( BT_IsBalanceTree( pbPreInTree ))　　{printf("該樹是平衡二叉樹");&l

33、t;b>　　}　　else　　{printf("這個不是平衡二叉樹");　　}　　}&l

34、t;p>　　else　　{printf("不要亂輸，前序與中序不匹配");　　}　　}　　break;</b

35、>　　(2)選用中序和后序輸入方式，并判斷是不是平衡二叉樹　　{printf("請輸入中序序列:\n");　　scanf("%s",&szMid) ;　　printf("請輸入后序序列:\n");&

36、lt;/p>　　scanf("%s",&szPost);　　bool bCorrect = BT_InPostToTree( pbPostInTree, szMid, szPost, 0, strlen(szMid)-1, 0, strlen(szPost)-1 );　　if ( bCorrect

37、)　　{printf( "該樹的前序序列為：\n");　　BT_PreOrder( pbPostInTree );　　if ( BT_IsBalanceTree( pbPostInTree ))　　{printf("該樹是平衡二叉樹"

38、;); 　　}　　else　　{printf("這個不是平衡二叉樹");　　}<b&g

39、t;　　}　　else　　{printf("不要亂輸，中序與后序不匹配");　　}　　}<

40、;p>　　break;　　default:　　{printf("不要亂選，不支持其他模式");　　}　　}<

41、/b>　　}　　五、算法實現效果圖：　　選用輸入方式：　　中序　　后序輸入

42、;　　得到結果　　5、輸入的中序和后序不匹配　　6、得到正確的結果　　六、總結：　　在此次課程設計過程中我們成功的利

43、用樹的遍歷以及二叉樹成立的條件判斷了隨意的二叉樹是為平衡二叉樹。　　其實在于計算機語言這類課程看重的就是上機的實際操作，不滿足于基本理論的學習。上機操作才能讓我們更加好的掌握我們所要學習的計算機語言知識。　　我們在此次程序設計中首先分析問題所要的關鍵然后找到題目所涉及的知識點，了解知識的結構在此基礎上選用正確的方法畫出我們解決問題的流程圖。接著我們在流程

44、圖的基礎上編寫代碼將我們所要實現的目的在計算機上實現。　　我們在解決我們問題的過程中通過前序和中序或者中序和后序的方式將樹輸入，再將其以后序或者前序的方式將其輸出。在判斷是不是為平衡二叉樹時我們分別檢索左右子樹的深度判斷左右子樹是不是平衡二叉樹，并且比較左右子樹的深度，看看它們之間的絕對值之差是不是小于1的。最終得到我們所輸入的二叉樹是不是平衡二叉樹。在我們輸入的過程中為了得到正確的結構，我們所

45、輸入的前序和中序必須是匹配的或者中序和后序是匹配的，只有這樣才能得到一個明確的樹的結構。　　七、心得體會：　　我們的專業(yè)決定了我們跟計算機結緣，這樣我們也就與計算機語言結緣啦。我們將會在以后的學習生涯中不斷學習計算機語言的知識。因而我們要懂得學習計算機語言的正確的方法這是才能事半功倍。<

46、p>　　上機編程看起來是件很單調很無聊的事情，但是只要我們能夠沉下心來，認真的處理自己需要解決的問題就能從這其中得到無窮的樂趣?。?lt;/p>　　八、參考文獻：　　劉玉龍數據結構與算法實用教程電子工業(yè)出版社　　譚浩強 C語言程序設計清華大學出版社

47、　　嚴蔚敏數據結構清華大學出版社　　九、附錄　　源程序如下：　　#include<stdio.h>　　#include<malloc.h> &

48、lt;/p>　　#include<string.h> 　　typedef struct BINTREE　　{　　char chData;　　struct BINTREE * pbLChil

49、d;　　struct BINTREE * pbRChild;　　} BinTree, * pBinTree;　　int BT_GetTreeDepth( pBinTree pbTree )　　{

50、;　　//存儲樹總的深度　　int iDepthTotal = 0;　　//存儲左子樹的深度　　int iDepthLeft = 0;　　//存儲右子樹的深度　　int iDepthRight

51、 = 0;　　if ( pbTree == NULL )　　{　　iDepthTotal = 0;　　}　　else

52、　　{　　// Depth of left child 左孩子的深度　　iDepthLeft = BT_GetTreeDepth( pbTree->pbLChild );　　// Depth of right child 右

53、孩子的深度　　iDepthRight = BT_GetTreeDepth( pbTree->pbRChild );　　// Get the max depth of left and right child, 1 means root node 去左右孩子深度的最大值，1代表著根節(jié)點 　　iDepthTot

54、al = 1 + ( iDepthLeft > iDepthRight ? iDepthLeft : iDepthRight );　　}　　return iDepthTotal;　　}　　b

55、ool BT_IsBalanceTree( pBinTree pbTree )　　{　　// If tree is not empty 如果樹不是空的　　if( pbTree != NULL )　　{</b

56、>　　// Store the left child depth 存儲左孩子的深度　　int iLeftDepth = 0;　　// Store the right child depth 存儲右孩子的深度　　int iRightDepth = 0;&

57、lt;/p>　　// Get the left child depth 得到左孩子的深度　　iLeftDepth = BT_GetTreeDepth( pbTree->pbLChild );　　// Get the right child depth 得到右孩子的深度&l

58、t;p>　　iRightDepth = BT_GetTreeDepth( pbTree->pbRChild );　　// Judge the tree is balance tree or not 判斷樹是不是平衡二叉樹平衡二叉樹的左右孩子的深度絕對值只差不大于1　　// The balance tree is the abstrac

59、t of left child depth reduce right child depth is equal or less than 1　　if (( iLeftDepth - iRightDepth >= -1 ) && ( iLeftDepth - iRightDepth <= 1 ))　　{<

60、/b>　　// Judge the left child is balance too 判斷左子樹是不是平衡的　　BT_IsBalanceTree( pbTree->pbLChild );　　// Judge the right child is balance too 判斷右子樹是不是平衡的<

61、;/p>　　BT_IsBalanceTree( pbTree->pbRChild );　　}　　else　　{　　retur

62、n false;　　}　　}　　else　　{　　return false;&

63、lt;/p>　　}　　return true;　　}　　bool BT_PreInToTree( pBinTree & pbTree, char * szInOrder, char * szPreOrd

64、er, int iInLeft, int iInRight, int iPreLeft, int iPreRight )　　{　　// Create node 創(chuàng)建一個節(jié)點　　pbTree = new BinTree;

65、　pbTree->chData = szPreOrder[iPreLeft];　　pbTree->pbLChild= pbTree->pbRChild = NULL;　　// Store current position 　　int iCurPos = iInLeft;

66、　　// Find the node the same as pre order 找到先前已經訪問的節(jié)點　　while (( iCurPos <= iInRight ) && ( szInOrder[iCurPos] != szPreOrder[iPreLeft] ))　　{</b&

67、gt;　　iCurPos ++;　　}　　// If the current position is greater than the right border, return false　　if ( iCurPos > iIn

68、Right )　　{　　return false;　　}　　int iLegnthLeft = iCurPos - iInLeft;　　// If cur

69、rent position is greater than left, generate left child　　if ( iCurPos > iInLeft )　　{　　BT_PreInToTree( pbTree->pbLChild, szInOrder, s

70、zPreOrder, iInLeft, iCurPos - 1, iPreLeft + 1, iPreLeft + iLegnthLeft );　　}　　// if current position is less than right, generate right child<p&g

71、t;　　if ( iCurPos < iInRight )　　{　　BT_PreInToTree( pbTree->pbRChild, szInOrder, szPreOrder, iCurPos + 1, iInRight, iPreLeft + iLegnthLeft + 1, iPreRight )

72、;　　}　　return true;　　}　　bool BT_InPostToTree( pBinTree & pbTree, char * szInOrder, char * szPos

73、tOrder, int iInLeft, int iInRight, int iPostLeft, int iPostRight )　　{　　// Create node　　pbTree = new BinTree;　　pbTre

74、e->chData = szPostOrder[iPostRight];　　pbTree->pbLChild = pbTree->pbRChild = NULL;　　// Store current position　　int iCurPos = iInLeft;<

75、p>　　// Find the node the same as post order　　while ( iCurPos <= iInRight && szInOrder[ iCurPos ] != szPostOrder[ iPostRight ])　　{<

76、p>　　iCurPos++;　　}　　// If the current position is greater than the right border, return false　　if ( iCurPos > iInRight )

77、　　{　　return false;　　}　　int iLengthLeft = iCurPos - iInLeft;　　// If the current position i

78、s greater than the left border, generate the left child　　if ( iCurPos > iInLeft )　　{　　BT_InPostToTree( pbTree->pbLChild, szInOrder,

79、szPostOrder, iInLeft, iCurPos - 1, iPostLeft, iPostLeft + iLengthLeft - 1);　　}　　// If the current position is less than the right border, generate the right ch

80、ild　　if ( iCurPos < iInRight )　　{　　BT_InPostToTree( pbTree->pbRChild, szInOrder, szPostOrder, iCurPos + 1, iInRight, iPostLeft + iLe

81、ngthLeft, iPostRight - 1);　　}　　return true;　　}　　void BT_PreOrder( pBinTree pbTree ) &l

82、t;p>　　{ 　　if ( pbTree != NULL )　　{　　// The preorder traversal is, root, left child, right child

83、　　printf( "%c ", pbTree->chData ); 　　BT_PreOrder ( pbTree->pbLChild );　　BT_PreOrder ( pbTree->pbRChild );　　}

84、　　}　　void BT_PostOrder( pBinTree pbTree ) 　　{ 　　if ( pbTree != NULL )　　{</b

85、>　　// The postorder traversal is, left child, right child, root　　BT_PostOrder ( pbTree->pbLChild ) ;　　BT_PostOrder ( pbTree->pbRChild ) ;

86、　　printf( "%c ", pbTree->chData );　　} 　　}　　void main()　　{</b&g

87、t;　　char szPre [100] = "";　　char szMid [100] = "";　　char szPost [100] = "";　　pBinTree pbPreInTree;</

88、p>　　pBinTree pbPostInTree;　　int iMode = 0;　　printf("請選擇生成二叉樹規(guī)則：前序和中序(0)，后序和中序(1)\n");　　scanf("%d",&iMode);

89、　　switch ( iMode )　　{　　case 0:　　{　　printf("請輸入前序序列:\n");<

90、;/p>　　scanf("%s",&szPre);　　printf( "請輸入中序序列:\n");　　scanf("%s",&szMid);　　bool bCorrect = BT_PreInToTree( p

91、bPreInTree, szMid, szPre, 0, strlen(szMid)-1, 0, strlen(szPre)-1 );　　if ( bCorrect )　　{printf("該樹的后序序列為：\n");　　BT_PostOrder( pbPreInTree );</p&g

92、t;　　if ( BT_IsBalanceTree( pbPreInTree ))　　{printf("該樹是平衡二叉樹");　　}　　else　　{pr

93、intf("這個不是平衡二叉樹");　　}　　}　　else　　{printf("不要亂輸，前序與中序不匹配");&l

94、t;/p>　　}　　}　　break;　　case 1:　　{printf("請輸

95、入中序序列:\n");　　scanf("%s",&szMid) ;　　printf("請輸入后序序列:\n");　　scanf("%s",&szPost);　　bool bCorrect

96、 = BT_InPostToTree( pbPostInTree, szMid, szPost, 0, strlen(szMid)-1, 0, strlen(szPost)-1 );　　if ( bCorrect )　　{printf( "該樹的前序序列為：\n");　　BT_PreOrder

97、( pbPostInTree );　　if ( BT_IsBalanceTree( pbPostInTree ))　　{printf("該樹是平衡二叉樹"); 　　}　　else</b&

98、gt;　　{printf("這個不是平衡二叉樹");　　}　　}　　else　　{printf(

99、"不要亂輸，中序與后序不匹配");　　}　　}　　break;　　default:

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

溫馨提示

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

數據結構課程設計----二叉樹平衡的判定

文檔簡介

溫馨提示

最新文檔

評論

數據結構課程設計----二叉樹平衡的判定

文檔簡介

溫馨提示

最新文檔

評論

免費下載