版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、<p> 課 程 設(shè) 計(jì) 報(bào) 告</p><p> 課程設(shè)計(jì)名稱:數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</p><p> 課程設(shè)計(jì)題目:二叉平衡樹的實(shí)現(xiàn)</p><p> 院(系):計(jì)算機(jī)學(xué)院</p><p> 專 業(yè):計(jì)算機(jī)科學(xué)與技術(shù)</p><p><b> 班 級(jí): </b>&
2、lt;/p><p><b> 學(xué) 號(hào):</b></p><p><b> 姓 名: </b></p><p><b> 指導(dǎo)教師: </b></p><p><b> 目 錄</b></p><p><b
3、> 1 需求分析1</b></p><p> 1.1 課程設(shè)計(jì)內(nèi)容和要求1</p><p> 1.2 算法描述1</p><p> 1.2.1存儲(chǔ)結(jié)構(gòu)1</p><p> 1.2.2 二叉排序樹和二叉平衡樹1</p><p> 1.2.3 層次遍歷二叉樹1</p>
4、;<p><b> 2 系統(tǒng)設(shè)計(jì)2</b></p><p> 2.1 總體方案設(shè)計(jì)2</p><p> 2.2 函數(shù)設(shè)計(jì)2</p><p> 2.3 關(guān)鍵流程4</p><p> 2.3.1 系統(tǒng)主流程4</p><p> 2.3.2 reat()創(chuàng)建鏈表函數(shù)
5、流程5</p><p> 2.3.3 travel()層次遍歷函數(shù)流程6</p><p> 2.3.4 B1()求左右孩子深度函數(shù)流程7</p><p> 2.3.5 B2()求節(jié)點(diǎn)平衡度函數(shù)流程8</p><p> 2.3.6 kind()判斷節(jié)點(diǎn)不平衡的類型函數(shù)流程9</p><p> 2.3.
6、7 deal()轉(zhuǎn)化成平衡樹類型函數(shù)流程10</p><p> 3 調(diào)試分析11</p><p><b> 參考文獻(xiàn)14</b></p><p><b> 附 錄15</b></p><p><b> 1 需求分析</b></p><
7、p> 1.1 課程設(shè)計(jì)內(nèi)容和要求</p><p><b> 內(nèi)容:</b></p><p> 從鍵盤輸入多組數(shù)據(jù),生成相應(yīng)的二叉排序樹并將各二叉排序樹轉(zhuǎn)換為二叉平衡樹,比較二叉排序樹和二叉平衡樹的平均比較長(zhǎng)度,并將文件保存到文件中。</p><p><b> 要求:</b></p><p
8、> 1.二叉排序樹和二叉平衡樹的存儲(chǔ)結(jié)構(gòu)自定;</p><p> 2.輸入數(shù)據(jù)要考慮多種情況,有代表性;</p><p> 3.給出動(dòng)態(tài)顯示過(guò)程(選作);</p><p><b> 1.2 算法描述</b></p><p><b> 1.2.1存儲(chǔ)結(jié)構(gòu)</b></p>
9、<p> 二叉排序樹是采用二叉鏈表建立,左孩子存放比父親節(jié)點(diǎn)小的數(shù),右孩子存放比父親節(jié)點(diǎn)大的數(shù)。二叉排序樹向二叉平衡樹轉(zhuǎn)化時(shí)用隊(duì)列來(lái)存儲(chǔ)每一個(gè)節(jié)點(diǎn),然后層次遍歷時(shí)也是用到隊(duì)列,然后輸出隊(duì)列就為層次遍歷的結(jié)果。</p><p> 1.2.2 二叉排序樹和二叉平衡樹</p><p> 用戶輸入數(shù)據(jù),程序會(huì)按照層次遍歷的結(jié)果建立二叉排序樹,比根節(jié)點(diǎn)小的數(shù)放在做孩子節(jié)點(diǎn)中,比根節(jié)點(diǎn)
10、大的數(shù)據(jù)放入右孩子節(jié)點(diǎn)。二叉平衡樹建立時(shí),需要判斷每個(gè)節(jié)點(diǎn)的平衡度,即左孩子的深度減去右孩子的深度的值的絕對(duì)值小于等于1,如果大于1,則該節(jié)點(diǎn)出現(xiàn)不平衡,從該節(jié)點(diǎn)開始調(diào)整成平衡。</p><p> 1.2.3 層次遍歷二叉樹</p><p> 從根節(jié)點(diǎn)出發(fā),輸出結(jié)點(diǎn)信息到隊(duì)列中,然后依次遍歷結(jié)點(diǎn)的左右孩子,每輸出一結(jié)點(diǎn)信息,,將其存儲(chǔ)在隊(duì)列中, 遍歷完結(jié)點(diǎn)后,隊(duì)列元素出隊(duì).循環(huán)執(zhí)行該過(guò)
11、程,當(dāng)隊(duì)列為空時(shí),函數(shù)執(zhí)行結(jié)束。將結(jié)果再保存到文件中。</p><p><b> 2 系統(tǒng)設(shè)計(jì)</b></p><p> 2.1 總體方案設(shè)計(jì)</p><p> 系統(tǒng)的總體設(shè)計(jì)方案是:首先由用戶輸入數(shù)據(jù),然后進(jìn)入二叉排序函數(shù)對(duì)數(shù)據(jù)進(jìn)行排序,排完序后對(duì)每一個(gè)節(jié)點(diǎn)求深度,然后判斷出不平衡的節(jié)點(diǎn),調(diào)用平衡函數(shù)把不平衡的節(jié)點(diǎn)調(diào)整成平衡的節(jié)點(diǎn),直
12、到循環(huán)結(jié)束,二叉平衡樹也就轉(zhuǎn)換完成。然后再層次遍歷二叉平衡樹,輸出結(jié)果并保存到文件中。</p><p><b> 2.2 函數(shù)設(shè)計(jì)</b></p><p> ﹙1﹚本系統(tǒng)所設(shè)計(jì)的函數(shù)見表2.1。</p><p><b> 表2.1 函數(shù)列表</b></p><p> ﹙2﹚本系統(tǒng)函數(shù)的調(diào)用關(guān)
13、系見圖2.1。</p><p> 圖2.1 調(diào)用關(guān)系圖</p><p><b> 2.3 關(guān)鍵流程</b></p><p> 2.3.1 系統(tǒng)主流程</p><p> (1)主函數(shù)的簡(jiǎn)單描述:</p><p> 本函數(shù)的具體功能是:該函數(shù)是系統(tǒng)執(zhí)行的必須函數(shù),本函數(shù)包含其他各個(gè)子函數(shù),經(jīng)
14、過(guò)調(diào)用,實(shí)現(xiàn)二叉排序樹,并把二叉排序樹轉(zhuǎn)化成二叉平衡樹。</p><p> ?。?)主函數(shù)的流程圖</p><p> 本函數(shù)的具體流程見圖2.2。</p><p> 圖2.2 主函數(shù)的流程圖</p><p> 2.3.2 reat()創(chuàng)建鏈表函數(shù)流程</p><p> (1)創(chuàng)建鏈表函數(shù)的簡(jiǎn)單描述:</p
15、><p> 本函數(shù)的具體功能是:根據(jù)用戶輸入的數(shù)據(jù)創(chuàng)建二叉排序樹。</p><p> (2)創(chuàng)建鏈表函數(shù)的流程圖</p><p> 本函數(shù)的具體流程見圖2.3。流程圖中變量i,k為控制循環(huán)的整型變量;n為要輸入的數(shù)據(jù)的個(gè)數(shù);D[100]為存儲(chǔ)輸入的數(shù)據(jù)。</p><p><b> N</b></p>&
16、lt;p><b> Y</b></p><p> 圖2.3 creat()函數(shù)的流程圖</p><p> 2.4.3 travel()層次遍歷函數(shù)流程</p><p> (1)層次遍歷函數(shù)的簡(jiǎn)單描述:</p><p> 本函數(shù)的具體功能:層次遍歷二叉樹,把遍歷的數(shù)據(jù)存儲(chǔ)到鏈表中。</p>&
17、lt;p> (2)層次遍歷函數(shù)的流程圖</p><p> 本函數(shù)的具體流程見圖2.4。</p><p><b> N</b></p><p><b> Y</b></p><p><b> N </b></p><p><b>
18、 Y</b></p><p><b> N</b></p><p> Y N</p><p><b> Y</b></p><p> 圖2.4 travel()函數(shù)的流程圖</p><p> 2.4.4 B1()求左右孩子深度函數(shù)流程&
19、lt;/p><p> ?。?)求深度函數(shù)的簡(jiǎn)單描述:</p><p> 本函數(shù)的具體功能是:完成二叉排序樹的存儲(chǔ)</p><p> ?。?)求深度函數(shù)的流程圖</p><p> 本函數(shù)的具體流程見圖2.5。流程圖有變量n1,n2為標(biāo)記該節(jié)點(diǎn)的位置。</p><p> Y N</p>
20、<p><b> N</b></p><p><b> Y</b></p><p><b> N</b></p><p><b> Y</b></p><p> 圖2.5 B1()函數(shù)的流程圖</p><p>
21、; 2.4.5 B2()求節(jié)點(diǎn)平衡度函數(shù)流程</p><p> ?。?)求節(jié)點(diǎn)平衡度函數(shù)的簡(jiǎn)單描述:</p><p> 本函數(shù)的具體功能是:計(jì)算出每一個(gè)節(jié)點(diǎn)的不平衡度,為轉(zhuǎn)化成二叉平衡樹做鋪墊。</p><p> 2)求節(jié)點(diǎn)平衡度函數(shù)的流程圖</p><p> 本函數(shù)的具體流程見圖2.6。</p><p>&l
22、t;b> N</b></p><p><b> Y</b></p><p> 圖2.6 B2()函數(shù)的流程圖</p><p> 2.4.6 kind()判斷節(jié)點(diǎn)不平衡的類型函數(shù)流程</p><p> 判斷節(jié)點(diǎn)不平衡的類型函數(shù)的簡(jiǎn)單描述:</p><p> 本函數(shù)的具體
23、功能是:判斷出每一個(gè)節(jié)點(diǎn)是RR 、RL、 LR 、LL中的哪種。</p><p> ?。?)判斷節(jié)點(diǎn)不平衡的類型函數(shù)的流程圖</p><p> 本函數(shù)的具體流程見圖2.7。流程圖有變量k為標(biāo)記該節(jié)點(diǎn)是第幾種不平衡類型。</p><p> 2 3 4 1</p><p> 圖2
24、.7 kind()函數(shù)的流程圖</p><p> 2.4.7 deal()轉(zhuǎn)化成平衡樹類型函數(shù)流程</p><p> (1)轉(zhuǎn)化成平衡樹類型函數(shù)的簡(jiǎn)單描述:</p><p> 本函數(shù)的具體功能是:從不平衡的節(jié)點(diǎn)開始,把節(jié)點(diǎn)轉(zhuǎn)化平衡。</p><p> (2)轉(zhuǎn)化成平衡樹類型函數(shù)的流程圖</p><p> 本函
25、數(shù)的具體流程見圖2.8。流程圖有變量k為標(biāo)記該節(jié)點(diǎn)是第幾種不平衡類型,i為循環(huán)變量,j為判斷節(jié)點(diǎn)是否存在。</p><p><b> N</b></p><p><b> Y</b></p><p><b> N</b></p><p><b> Y</
26、b></p><p> 圖2.8 deal()函數(shù)的流程圖</p><p><b> 3 調(diào)試分析</b></p><p><b> (1) 問(wèn)題1</b></p><p> 問(wèn)題描述:輸入數(shù)據(jù)后,輸出的二叉樹層次遍歷不準(zhǔn)確。</p><p> 問(wèn)題分析:d
27、eal函數(shù)編譯錯(cuò)誤,搞錯(cuò)了LL與LR類型。</p><p> 解決方法:進(jìn)入單部調(diào)試函數(shù),跟蹤每個(gè)參數(shù),一點(diǎn)一點(diǎn)找到問(wèn)題所在 并改正。</p><p><b> (2) 問(wèn)題2</b></p><p> 問(wèn)題描述: 無(wú)法將數(shù)據(jù)保存到文件中。</p><p> 問(wèn)題分析:可能是文件讀
28、寫錯(cuò)誤或者隊(duì)列應(yīng)用錯(cuò)誤</p><p> 解決方法:檢查文件的讀寫,設(shè)置一個(gè)新的參數(shù)將樹中的值傳給它,用它完成文件的保存。</p><p> 4 測(cè)試及運(yùn)行結(jié)果</p><p> 進(jìn)入操作界面如圖4.1所示。</p><p> 圖4.1 操作界面結(jié)果</p><p> (2)輸入多組數(shù)據(jù)的具體的測(cè)試結(jié)果如圖
29、4.2所示。</p><p> 圖4.2 多組數(shù)據(jù)測(cè)試結(jié)果</p><p> ?。?)經(jīng)層次遍歷后的平衡二叉樹輸出數(shù)據(jù)的具體的測(cè)試結(jié)果如圖4.3所示。</p><p> 圖4.3 輸出數(shù)據(jù)測(cè)試結(jié)果</p><p> 測(cè)試結(jié)果保存到到D盤的二叉平衡樹的文件中如圖4.4所示。</p><p> 圖4.4保存到文件中
30、</p><p><b> 參考文獻(xiàn)</b></p><p> [1] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版).北京:清華大學(xué)出版社,2007 </p><p> [2] 譚浩強(qiáng).C程序設(shè)計(jì)(第三版).清華大學(xué)出版社,2009</p><p> [3] 高一凡. 數(shù)據(jù)結(jié)構(gòu)算法分析.清華大學(xué)出版社,2008</
31、p><p> [4] 張長(zhǎng)海.C程序設(shè)計(jì).高等教育出版社,20004 </p><p> [5] 王裕明.數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì).清華大學(xué)出版社,2010</p><p> [6] 王曙燕 曹錳. C語(yǔ)言程序設(shè)計(jì). 科學(xué)出版社,2005</p><p><b> 附 錄</b></p><p>
32、;<b> 源程序清單:</b></p><p> #include<stdio.h></p><p> #include<stdlib.h></p><p> typedef struct BF</p><p><b> {</b></p><
33、p><b> int data;</b></p><p> int parent;</p><p><b> int left;</b></p><p> int right;</p><p><b> int bf;</b></p><p&
34、gt;<b> }BF;</b></p><p> typedef struct Bitree</p><p><b> {</b></p><p><b> int data;</b></p><p> struct Bitree *right;</p>
35、<p> struct Bitree *left;</p><p><b> }Bitree;</b></p><p> typedef struct</p><p><b> {</b></p><p> Bitree *base;</p><p>
36、<b> int top;</b></p><p> int bottom;</p><p><b> int size;</b></p><p><b> }queue;</b></p><p> BF c[100];</p><p> v
37、oid inistall(queue &q)</p><p><b> {</b></p><p> q.base=(Bitree *)malloc(sizeof(Bitree)*100);</p><p> q.top=q.bottom=0;</p><p> q.size=100;</p>
38、<p><b> }</b></p><p> void push(Bitree t,queue &q)</p><p><b> {</b></p><p> if(q.top==100)</p><p> printf("queue full\n&quo
39、t;);</p><p> q.base[q.top++]=t; </p><p><b> }</b></p><p> int empty(queue q)</p><p><b> {</b></p><p&g
40、t; if(q.top==q.bottom)</p><p><b> return 1;</b></p><p><b> else </b></p><p><b> return 0;</b></p><p><b> }</b></
41、p><p> void pop(Bitree *&temp,queue &q)</p><p><b> {</b></p><p> if(q.top==q.bottom)</p><p> printf("queue null\n");</p><p>
42、<b> else </b></p><p> temp=&(q.base[q.bottom++]);</p><p><b> }</b></p><p> queue travel(Bitree *t)</p><p><b> {</b></p&g
43、t;<p><b> queue q;</b></p><p> Bitree *temp;</p><p> inistall(q);</p><p> push(*t,q); </p><p> while(!empty(q))</p><p><b&g
44、t; {</b></p><p> pop(temp,q);</p><p> printf("%d ",temp->data);</p><p> if(temp->left)</p><p> push(*temp->left,q);</p><p>
45、if(temp->right)</p><p> push(*temp->right,q);</p><p><b> }</b></p><p><b> return q;</b></p><p><b> }</b></p><p&
46、gt; int Deep(Bitree *T)</p><p><b> {</b></p><p> int k,left,right;</p><p> if(!T)k=0;</p><p><b> else</b></p><p><b> {&
47、lt;/b></p><p> right=Deep(T->right);</p><p> left=Deep(T->left);</p><p> if(right>left)</p><p> k=1+right;</p><p><b> else </b>
48、;</p><p><b> k=1+left;</b></p><p><b> }</b></p><p><b> return k;</b></p><p><b> }</b></p><p> int loca
49、te(int n)</p><p><b> {</b></p><p><b> int i;</b></p><p> for(i=0;i<100;i++)</p><p> if(c[i].data==n)</p><p><b> retur
50、n i;</b></p><p><b> }</b></p><p> void B1(Bitree *T)</p><p><b> {</b></p><p> Bitree *p,*q;</p><p> int n1,n2;</p>
51、<p> if(T) </p><p><b> {</b></p><p><b> p=T;</b></p><p> q=p->left;</p><p> n1=locate(p->data);</p&g
52、t;<p> if(q!=NULL)</p><p> {n2=locate(q->data);</p><p> c[n1].left=n2;</p><p> c[n2].parent=n1;</p><p><b> }</b></p><p><b>
53、; else</b></p><p><b> {</b></p><p> c[n1].left=-1;</p><p><b> }</b></p><p> q=p->right;</p><p> n1=locate(p->data
54、);</p><p> if(q!=NULL)</p><p> {n2=locate(q->data);</p><p> c[n1].right=n2;</p><p> c[n2].parent=n1;</p><p><b> }</b></p><p&
55、gt;<b> else</b></p><p><b> {</b></p><p> c[n1].right=-1;</p><p><b> }</b></p><p> B1(T->left);</p><p> B1(T-&g
56、t;right);</p><p><b> }</b></p><p><b> }</b></p><p> void B2(Bitree *T)</p><p><b> {</b></p><p> int n,left,right;&
57、lt;/p><p><b> if(T)</b></p><p><b> {</b></p><p> left=Deep(T->left);</p><p> right=Deep(T->right);</p><p> n=locate(T->d
58、ata);</p><p> c[n].bf=left-right;</p><p> B2(T->left);</p><p> B2(T->right);</p><p><b> }</b></p><p><b> }</b></p>
59、<p> void B(Bitree *T)</p><p><b> {</b></p><p><b> int i;</b></p><p> for(i=0;i<100;i++)</p><p> c[i].parent=c[i].left=c[i].right
60、=-1;</p><p><b> B1(T);</b></p><p><b> B2(T);</b></p><p><b> }</b></p><p> void inistall(int a[],int n)</p><p><b
61、> {</b></p><p><b> int i;</b></p><p> for(i=0;i<n;i++)</p><p><b> {</b></p><p> c[i].data=a[i];</p><p> c[i].left
62、=c[i].right=c[i].parent=-1;</p><p> c[i].bf=0;</p><p><b> }</b></p><p><b> }</b></p><p> void find(Bitree *T,int data,Bitree *&p)</p&
63、gt;<p><b> {</b></p><p><b> if(T)</b></p><p><b> {</b></p><p> if(T->data==data)</p><p><b> p=T;</b></
64、p><p> find(T->left,data,p);</p><p> find(T->right,data,p);</p><p><b> }</b></p><p><b> }</b></p><p> int hunt(Bitree *p,Bi
65、tree *q)</p><p><b> {</b></p><p><b> if(p)</b></p><p><b> {</b></p><p> if(p->data==q->data)</p><p><b>
66、 return 1;</b></p><p><b> else </b></p><p><b> {</b></p><p> if(hunt(p->left,q))</p><p><b> return 1;</b></p>&
67、lt;p><b> else</b></p><p> return hunt(p->right,q);</p><p><b> }</b></p><p><b> }</b></p><p> else return 0;</p>&l
68、t;p><b> }</b></p><p> int kind(Bitree *p,Bitree *q)</p><p><b> {</b></p><p> Bitree *r,*s;</p><p><b> int k;</b></p>
69、<p> if(p->right!=NULL)</p><p><b> {</b></p><p> r=p->right;</p><p> s=r->right;</p><p> if((s!=NULL)&&(hunt(s,q)))</p>&l
70、t;p><b> k=2;//RR</b></p><p> s=r->left;</p><p> if((s!=NULL)&&(hunt(s,q)))</p><p><b> k=3;//RL</b></p><p><b> }</b&g
71、t;</p><p> if(p->left!=NULL)</p><p><b> {</b></p><p> r=p->left;</p><p> s=r->right;</p><p> if((s!=NULL)&&(hunt(s,q)))&l
72、t;/p><p><b> k=4;//LR</b></p><p> s=r->left;</p><p> if((s!=NULL)&&(hunt(s,q)))</p><p><b> k=1;//LL</b></p><p><b>
73、; }</b></p><p><b> return k;</b></p><p><b> }</b></p><p> int pos(Bitree *r,Bitree *q)</p><p><b> {</b></p><p&
74、gt;<b> int k;</b></p><p> if(r->left==q)k=2;</p><p> if(r->right==q)k=1;</p><p><b> return k;</b></p><p><b> }</b></p&
75、gt;<p> void deal(Bitree *&T,int data)</p><p><b> {</b></p><p> int i,k=0,j,e;</p><p> Bitree *p,*q,*r,*temp;</p><p> i=locate(data);</p&
76、gt;<p> while(c[i].bf<2&&c[i].bf>-2&&i!=-1)</p><p> i=c[i].parent;</p><p> if((c[i].bf>1||c[i].bf<-1)&&(i!=-1))</p><p><b> {<
77、/b></p><p> find(T,c[i].data,p);</p><p> j=c[i].parent;</p><p> find(T,data,q);</p><p> if(j!=-1)//r存在</p><p> { find(T,c[j].data,r);</p>
78、<p> e=pos(r,p);//e:1為p是r的右孩子 2為p是r的左孩子</p><p> k=kind(p,q);//1:LL 2:RR 3:RL 4:LR</p><p> if(e==1)//p是r的右孩子</p><p><b> {</b></p><p><b> swit
79、ch(k)</b></p><p><b> {</b></p><p> case 1:r->right=p->left;</p><p> p->left=r->right->right;</p><p> r->right->right=p;</p
80、><p><b> break;</b></p><p> case 2:r->right=p->right;</p><p> p->right=r->right->left;</p><p> r->right->left=p;</p><p>&
81、lt;b> break;</b></p><p> case 3:temp=p->right->left;</p><p> p->right->left=temp->right;</p><p> temp->right=p->right;</p><p> p->
82、right=temp;</p><p> p->right=temp->left;</p><p> temp->left=p;</p><p> r->right=temp;</p><p><b> break;</b></p><p> case 4:tem
83、p=p->left->right;</p><p> p->left->right=temp->left;</p><p> temp->left=p->left;</p><p> p->left=temp;</p><p> p->left=temp->right;<
84、;/p><p> temp->right=p;</p><p> r->right=temp;</p><p><b> break;</b></p><p> default:break;</p><p><b> }</b></p><
85、;p><b> }</b></p><p> if(e==2)//p是r的左孩子</p><p><b> { </b></p><p><b> switch(k)</b></p><p><b> {</b></p>&l
86、t;p> case 1:r->left=p->left;</p><p> p->left=r->left->right;</p><p> r->left->right=p;</p><p><b> break;</b></p><p> case 2:r-&
87、gt;left=p->right;</p><p> p->right=r->left->left;</p><p> r->left->left=p;</p><p><b> break;</b></p><p> case 3:temp=p->right->l
88、eft;</p><p> p->right->left=temp->right;</p><p> temp->right=p->right;</p><p> p->right=temp;</p><p> p->right=temp->left;</p><p&
89、gt; temp->left=p;</p><p> r->left=temp;</p><p><b> break;</b></p><p> case 4:temp=p->left->right;</p><p> p->left->right=temp->lef
90、t;</p><p> temp->left=p->left;</p><p> p->left=temp;</p><p> p->left=temp->right;</p><p> temp->right=p;</p><p> r->left=temp;<
91、;/p><p><b> break;</b></p><p> default:break;</p><p><b> }</b></p><p><b> }</b></p><p><b> B(T);</b></
92、p><p><b> }</b></p><p> else//A為頭結(jié)點(diǎn)</p><p><b> { </b></p><p> k=kind(p,q);//1:LL 2:RR 3:RL 4:LR</p><p><b> switch(k)<
93、/b></p><p><b> {</b></p><p> case 1:T=p->left;</p><p> p->left=T->right;</p><p> T->right=p;</p><p><b> break;</b&
94、gt;</p><p> case 2:T=p->right;</p><p> p->right=T->left;</p><p> T->left=p;</p><p><b> break;</b></p><p> case 3:temp=p->ri
95、ght->left;</p><p> p->right->left=temp->right;</p><p> temp->right=p->right;</p><p> p->right=temp;</p><p> p->right=temp->left;</p>
96、;<p> temp->left=p;</p><p><b> T=temp;</b></p><p><b> break;</b></p><p> case 4:temp=p->left->right;</p><p> p->left->
97、;right=temp->left;</p><p> temp->left=p->left;</p><p> p->left=temp;</p><p> p->left=temp->right;</p><p> temp->right=p;</p><p>&l
98、t;b> T=temp;</b></p><p><b> break;</b></p><p> default:break;</p><p><b> }</b></p><p><b> B(T);</b></p><p&g
99、t;<b> }</b></p><p><b> }</b></p><p><b> }</b></p><p> void creat(Bitree *&T)</p><p><b> {</b></p><p&
100、gt; int i,k,D[1000],n,j;</p><p> Bitree *p,*q,*R,*S,*G;</p><p> printf("\t請(qǐng)輸入數(shù)據(jù)個(gè)數(shù):");</p><p> scanf("%d",&n);</p><p> getchar();</p>
101、<p> for(i=0;i<n;i++)</p><p><b> {</b></p><p> printf("\t第%d個(gè)數(shù)據(jù):",i+1);</p><p> scanf("%d",&D[i]);</p><p><b> }&
102、lt;/b></p><p> inistall(D,n);</p><p> for(i=0;i<n;i++)</p><p><b> {</b></p><p><b> if(i==0)</b></p><p><b> {</b
103、></p><p> p=q=T=(Bitree *)malloc(sizeof(Bitree));</p><p> p->data=D[i];</p><p> p->left=p->right=NULL;</p><p><b> B(T);</b></p><p
104、><b> continue;</b></p><p><b> }</b></p><p> q=(Bitree *)malloc(sizeof(Bitree));</p><p> q->data=D[i];</p><p> q->left=q->right=
105、NULL;</p><p><b> p=T;</b></p><p> while(p!=NULL)</p><p><b> {</b></p><p><b> G=p;</b></p><p> if(D[i]>p->dat
106、a)</p><p> p=p->right;</p><p><b> else</b></p><p> p=p->left;</p><p><b> }</b></p><p> if(D[i]>G->data)</p>
107、<p> G->right=q;</p><p><b> else</b></p><p> G->left=q;</p><p><b> B(T);</b></p><p> deal(T,D[i]);</p><p><b>
108、; }//for</b></p><p><b> }</b></p><p> void WritetoText(Bitree *t) /*將所有記錄寫入文件*/ </p><p><b> { </b></p><p> FILE *fp; /*定義文件指針*/</
109、p><p> Bitree *temp;</p><p><b> queue q;</b></p><p><b> int s;</b></p><p> inistall(q);</p><p> push(*t,q); </p><p>
110、 fp=fopen("d:\\二叉平衡樹.txt","w"); /*打開文件*/ </p><p> while(!empty(q))</p><p><b> {</b></p><p> pop(temp,q);</p><p> printf("%d &q
111、uot;,temp->data);</p><p> s=temp->data;</p><p> fprintf(fp,"%d\n",s);</p><p> if(temp->left)</p><p> push(*temp->left,q);</p><p>
112、 if(temp->right)</p><p> push(*temp->right,q);</p><p><b> }</b></p><p> fclose(fp); /*關(guān)閉文件*/</p><p> printf("\n\t\t\tSuccessed!\n"); /*
113、返回成功信息*/ </p><p><b> } </b></p><p> void show()</p><p><b> {</b></p><p> printf("\t**************************************************\n
114、");</p><p> printf("\n");</p><p> printf("\t\t\t請(qǐng)二叉平衡樹的實(shí)現(xiàn)\n");</p><p> printf("\n");</p><p> printf("\t*********************
115、*****************************\n");</p><p> printf("\t注:請(qǐng)輸入任意不重復(fù)的數(shù)字,本程序會(huì)先轉(zhuǎn)換為二叉排序樹\n");</p><p> printf("\t 再轉(zhuǎn)化為二叉平衡樹經(jīng)層次遍歷輸出并保存到D盤的文件中\(zhòng)n");</p><p><b&g
116、t; }</b></p><p> void main()</p><p><b> {</b></p><p> Bitree *T;</p><p><b> queue qq;</b></p><p><b> show();</
117、b></p><p> loop:creat(T);</p><p> printf("\t生成的平衡二叉樹為:");</p><p> travel(T);</p><p> WritetoText(T);</p><p> goto loop;</p><p&
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----二叉樹平衡的判定
- 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)--二叉排序樹調(diào)整為平衡二叉樹
- 二叉樹數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---二叉排序樹和平衡二叉樹的判別
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--二叉排序樹的實(shí)現(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-二叉排序樹的實(shí)現(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--二叉排序樹
- 《數(shù)據(jù)結(jié)構(gòu)遍歷二叉樹》課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----二叉樹的應(yīng)用
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--二叉樹的遍歷
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---二叉樹的操作
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---計(jì)算二叉樹高度
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--二叉樹及應(yīng)用
- 數(shù)據(jù)結(jié)構(gòu)二叉排序樹課程設(shè)計(jì)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---線索二叉樹
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--二叉樹的相關(guān)操作
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--二叉樹的算法
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-二叉樹的基本操作
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)之二叉樹的遍歷
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)之-樹與二叉樹的轉(zhuǎn)換
評(píng)論
0/150
提交評(píng)論