樹與二叉樹轉(zhuǎn)換實現(xiàn)12

1、河南工程學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計成果報告樹與二叉樹轉(zhuǎn)換實現(xiàn)2014年12月29日把一般樹轉(zhuǎn)換為二叉樹后:e、C: JlSOFTCTuTanbint ep. exo創(chuàng)立的樹具體情況如下： 序號結(jié)點雙親 TOC o 1-5 h z 01-1213142-1-1一股樹轉(zhuǎn)換成二叉樹后的情況：1324* 副菜單 * *9返回主菜單繼續(xù)操作*今退出不呈序 * *圖2. 5. 5樹與二叉樹的轉(zhuǎn)換界面3程序清單ttinclude ttinclude include #define MaxSize 100typedef char ElemType;typedef struct bnode 二叉樹定義 (Ele

2、mType data;struct bnode *lchild;struct bnode *rchild;7 bTNode, bTree;void insertBTNode(bTNode *&b, char *str) 由 str 串創(chuàng)立二叉鏈 bTNode *StMaxSize, *p=NULL;int top=-l, k,j=0;char ch;b=NULL;建立的二叉樹初始時為空ch=strj; while (ch!=0)/str未掃描完時循環(huán)switch(ch)case ( : top+;St top =p;k=l; break;為左結(jié)點case ) :top-;break;case

3、,:k=2; break;為右結(jié)點default:p=(bTNode *)malloc(sizeof(bTNode);p-data=ch;p-lchild=p-rchild=NULL;if (b=NULL)p指向二叉樹根結(jié)點b=p；else已建立二叉樹根結(jié)點switch(k) (case 1:St top-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;void preOrder(bTNode *T)if(T!=NULL)(printf (%c , T-data);preOrder(T-lchild);preOrder(T-rchiI

4、d);樹的相關(guān)操作/*樹的雙親表示結(jié)點結(jié)構(gòu)定義*/typedef structint data;int parent;雙親位置域PTNode;/*雙親表示法樹結(jié)構(gòu)*/typedef structPTNode nodeMaxSize;int count;根的位置和節(jié)點個數(shù)PTree;/*樹的孩子兄弟表示結(jié)點結(jié)構(gòu)定義*/ typedef struct nodeint data;struct node irstchild;struct node *nextchild;BTNode, *BTree;初始化樹(雙親表示法) void init_ptree(PTree *tree) tree-count=

5、-l;初始化樹結(jié)點(孩子兄弟表示法)BTNode GetTreeNode(int x)BTNode t;t.data=x;t. firstchild=t. nextchild=NULL;return t;/樹的前序遍歷10void preorder (BTNode *T)if(T!=NULL)printf (%d , T-data);preorder (T-firstchild);preorder (T-nextchiId);樹后序遍歷(遞歸)void inoeder(BTNode *T)if(T!=NULL)inoeder(T-firstchild);printf (/z%d , T-dat

6、a);inoeder (T-nextchiId);)水平輸出二叉樹void PrintBTree(BTNode *root, int level)int i;if (root!=NULL)PrintBTree (root-nextchild, level+1);for (i=l;idata);11PrintBTree(root-firstchild, level+1);輸出樹void printptree(PTree tree)int i;printf C序號 結(jié)點雙親n)；for (i=0;i=tree. count;i+)printf(%8d%8d%8d, i, tree, nodei.

7、data, tree, nodei. parent); printf (n);)/*用雙親表示法創(chuàng)立樹*/PTree CreatTree(PTree T)int i=l;int fa, ch;PTNode p;printf (請依次輸入各節(jié)點(以數(shù)據(jù)域0結(jié)束)：);for (i=l;ch!=-l;i+)scanf (d, %d，&fa, &ch);12 printf (n);p. data=ch;p.parent=fa;T.count+;T.nodeT. count, data = p. data;T.nodeT. count. parent 二 p. parent;printf (n);pr

8、intf (創(chuàng)立的樹如下：n);print_ptree(T);return T;/* 一般樹轉(zhuǎn)換成二叉樹*/ BTNode *change(PTree T) int i,j=0;BTNode pMaxSize;BTNode *a, *b, *c, *Tree;a= (BTNode *)malloc(sizeof(BTNode);b= (BTNode *)malloc(sizeof(BTNode);c-(BTNode *)malloc(sizeof(BTNode);Tree= (BTNode *)malloc(sizeof(BTNode);for (i=0;iT. count;i+) pi=Ge

9、tTreeNode(T. nodei. data);for (i=l;idata)j+；b二&pj;if(!(b-firstchild)b-firstchild=a;c=a;)elsec-nextchild=a;c=a;)Tree=&p0;return Tree;/*主菜單*/void Menu ()(printf (nnnn);printf (，z 主菜單printf (*選項【1】*printf (*選項【2】*nnn);創(chuàng)立一棵樹nn);樹的前序遍歷nn);14printf(*選項【3】*樹的后序遍歷nn)；printf(*選項【4】*建立一個指定的二叉樹nn);printf(*選項【0

10、】*退出程序nn)；printf ( =nz/);printf (請輸入執(zhí)行的指令:)；void Menu2 ()printf C*選項【5】* 返回主菜單 n);printf (/z*選項【0】*退出程序n);/*主函數(shù)*/void main ()int i=0, cl, c2;PTree T;BTNode *Tree;bTNode *b;init_ptree(&T);loop:Menu ();scanf(d，&cl);switch (cl)case 1:printf(輸入結(jié)點方式:雙親，數(shù)據(jù)域n)；T=CreatTree(T);15Tree=change(T);4測試測試數(shù)據(jù)建立一棵樹：輸

11、入指令1。輸入結(jié)點的方式：雙親數(shù)據(jù)（整形），節(jié)點數(shù)據(jù) （整形）以-1,-1結(jié)束。-1, 1 1,2 -1, -14. 2測試結(jié)果分析對于測試結(jié)果（詳見2.5）,比擬符合實驗預(yù)期效果，能夠進行樹與二叉樹 的轉(zhuǎn)換，而且能夠輸出樹的先序遍歷，后序遍歷。唯一美中缺乏的是界面尚不美觀，有待優(yōu)化。5總結(jié)以前編程的時候，只是注重如何編寫函數(shù)能夠完成所需要的功能，似乎沒有 明確的戰(zhàn)術(shù)，只是憑意識和簡單的語句來堆砌出一段段程序。現(xiàn)在變成感覺完全 不同了。在編寫一個程序之前，自己能夠綜合考慮各種因素，首先選取自己需要 的數(shù)據(jù)結(jié)構(gòu)，是樹還是圖或是別的什么。然后再選定一種或幾種存儲結(jié)構(gòu)來具體 的決定后面的函數(shù)的主要風(fēng)

12、格。最后在編寫每一個函數(shù)之前，可以自習(xí)斟酌出對 挑選出最合適當(dāng)前狀況的算法。這樣，即使在完整的程序還沒有寫出來之前，自 己心中已經(jīng)有了明確的原圖了。這樣無形中就提高了自己編寫程序的質(zhì)量。另外，我還體會到深刻理解數(shù)據(jù)結(jié)構(gòu)的重要性。只有真正理解這樣定義數(shù)據(jù) 類型的好處，才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。了解典型數(shù)據(jù)結(jié)構(gòu)的性質(zhì)是非常有用 的，它往往是編寫程序的關(guān)鍵。這次試驗也讓我看到了自己的缺乏，還是不太用模版類。還有許多關(guān)于c 的一些比擬具體的東西還不太懂，比方說指針。這次實驗還讓我意識到只有不管 在機子上調(diào)試程序，自己的水平才能得到提高。我會繼續(xù)我的興趣編寫程序的，相信在越來越多的嘗試之后，自己會不斷進

13、16題目樹與二叉樹轉(zhuǎn)換實現(xiàn)考核工程考核內(nèi)容得分平時考核（30分）出勤情況、態(tài)度、效率；知識掌握情況、 基本操作技能、知識應(yīng)用能力、獲取知識能力系統(tǒng)設(shè)計（20分）分析系統(tǒng)的功能模塊編程調(diào)試（20分）實現(xiàn)系統(tǒng)的各個功能模塊，并完成調(diào)試回答下列問題（15分）回答老師針對課程設(shè)計提出的問題課程設(shè)計報告撰 寫（10分）嚴(yán)格按照規(guī)范要求完成課程設(shè)計報告源代碼（5分）按照規(guī)范要求完成課程設(shè)計源代碼的排 版總評成績指導(dǎo)教師評語：日期：年 月日參考文獻1譚浩強.C語言程序設(shè)計（第四版）.清華大學(xué)出版社嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社3譚浩強.C+面向?qū)ο蟪绦蛟O(shè)計.清華大學(xué)出版社4馮舜璽.數(shù)據(jù)結(jié)構(gòu)與算

14、法分析:C語言描述（第二版）.機械工業(yè)出版社5嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)習(xí)題冊（C語言版）.清華大學(xué)出版社1718 TOC o 1-5 h z 1課程設(shè)計目標(biāo)與任務(wù)1課程設(shè)計任務(wù)1 HYPERLINK l bookmark14 o Current Document 課程設(shè)計目標(biāo)及要求12.1題目需求分析2 HYPERLINK l bookmark19 o Current Document 2. 2存儲結(jié)構(gòu)設(shè)計2 HYPERLINK l bookmark21 o Current Document 2. 3算法描述3 HYPERLINK l bookmark23 o Current Document 2.4

15、程序流程圖4 HYPERLINK l bookmark25 o Current Document 2.5測試程序說明5 HYPERLINK l bookmark0 o Current Document 3程序清單94測試164.1測試數(shù)據(jù)16 HYPERLINK l bookmark5 o Current Document 4. 2測試結(jié)果分析16 HYPERLINK l bookmark7 o Current Document 5總結(jié)16 HYPERLINK l bookmark9 o Current Document 參考文獻171課程設(shè)計目標(biāo)與任務(wù)課程設(shè)計任務(wù)1、設(shè)計樹與二叉樹轉(zhuǎn)換的相關(guān)

16、函數(shù)庫，以便在程序設(shè)計中調(diào)用，要求：(1)實現(xiàn)樹與二叉樹的轉(zhuǎn)換；(2)最好能借助語言環(huán)境實現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖 形方式顯示出來，將復(fù)雜的運行過程以動態(tài)方式顯示出來；(3)給出假設(shè)干例程，演示通過調(diào)用自己所縮寫程序來實現(xiàn)相關(guān)問題的求解。1.2課程設(shè)計目標(biāo)及要求數(shù)據(jù)結(jié)構(gòu)課程設(shè)計是計算機科學(xué)與技術(shù)專業(yè)集中實踐性環(huán)節(jié)之一， 是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程后進行的一次全面的綜合練習(xí)。其目的就是要到達(dá) 理論與實際應(yīng)用相結(jié)合，使學(xué)生能夠根據(jù)數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的 方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，并培養(yǎng)良好的程 序設(shè)計技能。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計是在學(xué)完數(shù)據(jù)結(jié)構(gòu)課程之后的實踐教學(xué)

17、環(huán)節(jié)。該實踐教學(xué) 是軟件設(shè)計的綜合訓(xùn)練,包括問題分析，總體結(jié)構(gòu)設(shè)計用戶界面設(shè)計，程序設(shè)計 基本技能和技巧。要求學(xué)生在設(shè)計中逐步提高程序設(shè)計能力培養(yǎng)科學(xué)的軟件工作 方法學(xué)生通過數(shù)據(jù)結(jié)構(gòu)課程設(shè)計各方面得到鍛煉：(1)能根據(jù)實際問題的具體情況結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算 法，正確分析出數(shù)據(jù)的邏輯結(jié)構(gòu)，合理地選擇相應(yīng)的存儲結(jié)構(gòu)，并能設(shè)計出解決 問題的有效算法；(2)通過上機實習(xí)，驗證自己設(shè)計的算法的正確性，學(xué)會有效利用基本調(diào)試 方法，迅速找出程序代碼中的錯誤并且修改；(3)培養(yǎng)算法分析能力，分析所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度，進一步提高程序設(shè)計水平;2分析與設(shè)計1題目需求分析本程序的功能是

18、對任意二叉樹進行與樹的轉(zhuǎn)換。本程序要求用戶以字符輸 入，假設(shè)要實現(xiàn)終端結(jié)點，最后以回車鍵建入數(shù)據(jù)。本程序的結(jié)果將依次打印出遞歸前序遍歷和后序遍歷，用棧實現(xiàn)非遞歸的前序和中序遍歷和后序遍歷，和線 索化層序遍歷，輸入樹及樹傳換成二叉樹。2存儲結(jié)構(gòu)設(shè)計引入頭文件：ttinclude ttinclude ttinclude 設(shè)置常量：define MAX_TREE_SIZE 100一般樹的存儲結(jié)構(gòu)有以下幾種：雙親結(jié)點，孩子結(jié)點，孩子兄弟結(jié)點。本實驗運用到的是雙親結(jié)點和孩子兄弟結(jié)點。具體存儲結(jié)構(gòu)如下：/*樹的雙親表示結(jié)點結(jié)構(gòu)定義*/typedef structint data;int parent; 雙

19、親位置域PTNode;/*雙親表示法樹結(jié)構(gòu)*/typedef structPTNode nodeMAX_TREE_SIZE;int count;/根的位置和節(jié)點個數(shù)PTree;/*樹的孩子兄弟表示結(jié)點結(jié)構(gòu)定義*/typedef struct nodeint data;struct node irstchild;struct node *rightsib; BTNode, *BTree;.3算法描述一般樹的存儲結(jié)構(gòu)有以下幾種：雙親結(jié)點，孩子結(jié)點，孩子兄弟結(jié)點。本實 驗運用到的是雙親結(jié)點和孩子兄弟結(jié)點。輸入一個二叉樹的先序序列，構(gòu)造這棵二叉樹。為了保證唯一地構(gòu)造出所 希望的二叉樹，在鍵入這棵樹的先

20、序序列時，需要在所有空二叉樹的位置上填補 一個特殊的字符，比方，在算法中，需要對每個輸入的字符進行判斷，如 果對應(yīng)的字符是那么在相應(yīng)的位置上構(gòu)造一棵空二叉樹；否那么，創(chuàng)立一個新 結(jié)點。整個算法結(jié)構(gòu)以先序遍歷遞歸算法為基礎(chǔ)，二叉樹中結(jié)點之間的指針連接 是通過指針參數(shù)在遞歸調(diào)用返回時完成。計算一棵二叉樹的葉子結(jié)點數(shù)目這個操作可以使用三種遍歷順序中的任何一種，只是需要將訪問操作變成 判斷該結(jié)點是否為葉子結(jié)點，如果是葉子結(jié)點將累加器加1即可。下面這個算法 是利用中序遍歷實現(xiàn)的。首先要知道 樹（森林）轉(zhuǎn)換成二叉樹的方法。一般是把樹（森林）當(dāng)前結(jié)點的 的孩子當(dāng)成左子樹（或右子樹），層層轉(zhuǎn)換而得到一個新的二

21、叉樹。根據(jù)樹（森林） 轉(zhuǎn)換二叉樹的方法，逆向回去，就可以得到二叉樹轉(zhuǎn)換樹的算法。/*樹的雙親表示結(jié)點結(jié)構(gòu)定義*/typedef structint data;int parent; 雙親位置域PTNode;/ *雙親表示法樹結(jié)構(gòu)*/typedef structPTNode nodeMAX_TREE_SIZE;int count;根的位置和節(jié)點個3數(shù)PTree;2. 4程序流程圖編譯運行，進入主菜單項選擇擇界面，選擇1創(chuàng)立二叉樹，按格式輸入各個節(jié)點。 此時可以選擇2輸出各個節(jié)點情況，亦可以選擇3輸出前序遍歷結(jié)果，選擇4 輸出后序遍歷結(jié)果，亦或是選擇5調(diào)用Transform。將二叉樹轉(zhuǎn)換為樹，繼而根 據(jù)提示輸入置頂功能進行樹的遍歷輸出功能，最后選擇0退出程序圖2. 4程序流程圖5測試程序說明 ialx程序開始:有 C:JISOFTCTuYanbinvrtcBp. exe單一二二二二二Z=二=ZZZT二二二二*輸入1以雙親法創(chuàng)立一棵一般樹*a*輸入2樹的前序遍歷（遞歸）*輸入3樹的后序遍歷（遞歸）*輸入4樹的前序遍歷（非遞歸）*輸入5樹的后序遍歷（非遞歸）*輸入6層次序的非遞扇遍歷* 輸入 0退出程序