《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計-樹與二叉樹轉(zhuǎn)換的實現(xiàn).doc

河南工程學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計成果報告樹與二叉樹轉(zhuǎn)換的實現(xiàn)學(xué)生學(xué)號： 學(xué)生姓名： 學(xué) 院： 計算機學(xué)院 專業(yè)班級： 軟件工程 專業(yè)課程： 數(shù)據(jù)結(jié)構(gòu)與算法 指導(dǎo)教師： 2014 年 12 月 29 日題 目樹與二叉樹轉(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分）嚴格按照規(guī)范要求完成課程設(shè)計報告源代碼（5分）按照規(guī)范要求完成課程設(shè)計源代碼的排版總 評 成 績指導(dǎo)教師評語： 日期： 年 月 日目 錄目 錄31 課程設(shè)計目標與任務(wù)11.1 課程設(shè)計題目11.2 課程設(shè)計目的及基本要求12 分析與設(shè)計22.1 題目需求分析22.2 存儲結(jié)構(gòu)設(shè)計24 測試114.1 測試數(shù)據(jù)114.2 測試結(jié)果分析12參考資料141 課程設(shè)計目標與任務(wù)1.1 課程設(shè)計題目 設(shè)計樹與二叉樹轉(zhuǎn)換的相關(guān)函數(shù)庫，以便在程序設(shè)計中調(diào)用，要求：（1）實現(xiàn)樹與二叉樹的轉(zhuǎn)換；（2）最好能借助語言環(huán)境實現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖形方式顯示出來，將復(fù)雜的運行過程以動態(tài)方式顯示出來；（3）給出若干例程，演示通過調(diào)用自己所縮寫程序來實現(xiàn)相關(guān)問題的求解。1.2 課程設(shè)計目的及基本要求 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計是計算機軟件工程專業(yè)實踐性環(huán)節(jié)之一，是學(xué)習完數(shù)據(jù)結(jié)構(gòu)課程后進行的一次全面的綜合練習。其目的就是要達到理論與實際應(yīng)用相結(jié)合，是學(xué)生能夠根據(jù)數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，并培養(yǎng)良好的程序設(shè)計技能。2 分析與設(shè)計2.1 題目需求分析樹結(jié)構(gòu)的建立是在數(shù)據(jù)邏輯結(jié)構(gòu)基礎(chǔ)上的數(shù)據(jù)類型，二叉樹則是樹結(jié)構(gòu)中最常見和使用最多的類型。通過對二叉樹的操作，可以實現(xiàn)多種數(shù)據(jù)操作，如排序、查找等。一個好的二叉樹遍歷算法應(yīng)包含以下功能：1） 以遞歸和和非遞歸方法建立二叉樹或完全二叉樹；2） 實現(xiàn)二叉樹的前序遍歷、中序遍歷、后序遍歷；3） 每種遍歷算法皆以遞歸和非遞歸方法實現(xiàn)；2.2 存儲結(jié)構(gòu)設(shè)計引入頭文件：#include#include#include設(shè)置常量：#difineMAX_TREE_SIZE一般樹的存儲結(jié)構(gòu)有以下幾種：雙親節(jié)點，孩子結(jié)點，孩子兄弟結(jié)點。本實驗運用到的是雙親結(jié)點和孩子兄弟結(jié)點。具體存儲結(jié)構(gòu)如下：/*樹的雙親表示結(jié)點結(jié)構(gòu)定義*/TypedefstructInt data;Int parent; /雙親位置域PTNode;/*雙親表示法樹結(jié)構(gòu)*/TypedefstructPTNode nodeMAX_TREE_SIZE;Int count; /根的位置和結(jié)點個數(shù)PTree；/*樹的孩子兄弟表示結(jié)點結(jié)構(gòu)定義*/Typedefstruct node Int data;Struct node*firstchild;Struct node*rightsib;BTNode;*BTree;2.3 算法描述首先建立頭結(jié)點，并保存數(shù)據(jù)，然后根據(jù)遞歸方法，分別建立其左右孩子結(jié)點，且左右孩子結(jié)點的指針域指向空。以遞歸方法建立二叉樹，每次建立一個結(jié)點后，將其左右孩子指針域置空，成為葉子結(jié)點。然后通過前序遍歷、中序遍歷、后序遍歷實現(xiàn)數(shù)據(jù)最優(yōu)，方便數(shù)據(jù)的使用。2.4 程序流程圖流程圖如下：圖2.4-1流程圖3 程序清單#include using namespace std; #define m 3 typedef char ElemType; typedef struct Node ElemType data; struct Node* childm; Node,*Tree; typedef struct BiTNode ElemType data; struct BiTNode*lchild,*rchild; BiTNode,*BiTree; typedef struct stack /棧結(jié)構(gòu)定義 BiTree data100; /data 元素類型為 指針 int top; /棧頂指針 seqstack; / 按前序遍歷 創(chuàng)建一棵度數(shù)為3的樹的遞歸算法 void createtree(Tree &p) int i; char ch; if(ch=getchar()=#) p=NULL; /建立一棵空樹 else p=(Tree)malloc(sizeof(Node); /用new 怎么建立 p-data=ch; for(i=0;ichildi); BiTree TreetoBiTree(Tree &p) int i; if(p=NULL) return NULL; BiTNode* q=(BiTNode*)malloc(sizeof(ElemType) ;/創(chuàng)建根節(jié)點 - q-data =p-data; q-lchild=NULL; q-rchild=NULL; if(p-child0!=NULL) q-lchild=TreetoBiTree(p-child0);/把樹的第一個孩子賦給二叉樹的左孩子 BiTNode* r=q-lchild; if(p-child1!=NULL) for(i=1;ichildi!=NULL) r-rchild=TreetoBiTree(p-child i); r=r-rchild; else return q; else if(p-child2!=NULL) r-rchild=TreetoBiTree(p-child 2); r=r-rchild; else return q; else if(p-child1!=NULL) q-lchild=TreetoBiTree(p-child1);/把樹的第二個孩子賦給二叉樹的左孩子 BiTNode* r=q-lchild; if(p-child2!=NULL) r-rchild=TreetoBiTree(p-child 2); else return q; else if(p-child2!=NULL) q-lchild=TreetoBiTree(p-child1);/把樹的第三個孩子賦給二叉樹的左孩子 return q; Tree BiTreetoTree(BiTree &q) int i; if(q=NULL)return NULL; Node* p=(Node*)malloc(sizeof(ElemType); p-data=q-data;/根賦值 for(i=0;ichildi=NULL; if(q-lchild!=NULL) p-child0=BiTreetoTree(q-lchild); BiTNode* r=q-lchild ; for(i=1;irchild!=NULL) p-childi=BiTreetoTree(r-rchild ); r=r-rchild ; return p; void push(seqstack* s,BiTree p) /進棧 s-data+s-top=p; BiTree pop(seqstack* s) /出棧 if(s-top!=-1) /非遞歸遍歷中，top初始值為-1 s-top-; return (s-datas-top+1); else return NULL; void PreOrderPrint(BiTree &q) if(q!=NULL) printf(%c,q-data); PreOrderPrint(q-lchild); PreOrderPrint(q-rchild); /二叉樹中序遍歷 非遞歸 算法 void inorder1(BiTree p) seqstack s; s.top=-1; while(p!=NULL)|(s.top!=-1) while(p) push(&s,p); p=p-lchild; /子樹根結(jié)點全部進棧 if(s.top!=-1) p=pop(&s); printf(%c,p-data); /輸出根結(jié)點，其實也就是左孩子或右孩子(沒有孩子的根結(jié)點是它父親的左或右孩子） p=p-rchild; /進入右孩子訪問 /樹的前序遍歷遞歸算法 void preorder(Tree p) /P為指向樹根的指針 int i; if(p!=NULL) /樹不為空 printf(%c,p-data); /輸出根節(jié)點的值 for(i=0;ichildi); /樹的后序遍歷的遞歸算法 void postorder(Tree p) int i; if(p!=NULL) for(i=0;ichildi); printf(%c,p-data); /輸出根節(jié)點的值 /樹的層次遍歷 void level(Tree t) Tree queue20; /存放等待訪問的節(jié)點隊列,每個元素都是指針型 int f=0,r=0,i; /f,r 分別是隊頭,隊尾指針 Tree p; queue0=t; while(fdata); /訪問隊頭元素 for(i=0;ichildi) +r; queuer=p-childi; void main() printf(tt*n); printf(tt 樹轉(zhuǎn)化為二叉樹 n); printf(tt*n); Tree T; Tree T1; BiTree p; printf(=輸入要創(chuàng)建的樹=:n); createtree(T);/創(chuàng)建 一棵樹 printf(n樹的先序遍歷:); preorder(T); printf(n樹的后序遍歷:); postorder(T); printf(n樹的層序遍歷:); level(T); printf(n); printf(n=樹轉(zhuǎn)換為二叉樹=n); p=TreetoBiTree(T); printf(n遍歷二叉樹:); PreOrderPrint(p); 4 測試4.1 測試數(shù)據(jù)圖4.1-1開始界面圖4.1-2選擇功能界面圖4.1-3二叉樹信息界面4.2 測試結(jié)果分析輸入創(chuàng)建的樹之后，會先后得到樹的先序遍歷、中序遍歷、后序遍歷，最后得到樹轉(zhuǎn)換為二叉樹的形式，生成遍歷二叉樹。 5 總結(jié)這次實訓(xùn)讓我體會到深刻理解數(shù)據(jù)結(jié)構(gòu)的重要性。只有真正理解這樣定義數(shù)據(jù)類型的好處，才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。了解典型數(shù)據(jù)結(jié)構(gòu)的性質(zhì)是非常有用的，它往往是編寫程序的關(guān)鍵。同時我發(fā)現(xiàn)還有許多關(guān)于C+的一些比較具體的東西還不太懂，比方說指針。相信在越來越多練習中，自己的編程能力會不斷提高。參考資料(1)嚴蔚敏 吳偉民 編數(shù)據(jù)結(jié)構(gòu)( C語言版) 清華大學(xué)出版社(2)嚴蔚敏 編數(shù)據(jù)結(jié)構(gòu)習題集清華大學(xué)出版社#include using namespace std; #define m 3 typedef char ElemType; typedef struct Node ElemType data; struct Node* childm; Node,*Tree; typedef struct BiTNode ElemType data; struct BiTNode*lchild,*rchild; BiTNode,*BiTree; typedef struct stack /棧結(jié)構(gòu)定義 BiTree data100; /data 元素類型為 指針 int top; /棧頂指針 seqstack; / 按前序遍歷 創(chuàng)建一棵度數(shù)為3的樹的遞歸算法 void createtree(Tree &p) int i; char ch; if(ch=getchar()=#) p=NULL; /建立一棵空樹 else p=(Tree)malloc(sizeof(Node); /用new 怎么建立 p-data=ch; for(i=0;ichildi); BiTree TreetoBiTree(Tree &p) int i; if(p=NULL) return NULL; BiTNode* q=(BiTNode*)malloc(sizeof(ElemType) ;/創(chuàng)建根節(jié)點 - q-data =p-data; q-lchild=NULL; q-rchild=NULL; if(p-child0!=NULL) q-lchild=TreetoBiTree(p-child0);/把樹的第一個孩子賦給二叉樹的左孩子 BiTNode* r=q-lchild; if(p-child1!=NULL) for(i=1;ichildi!=NULL) r-rchild=TreetoBiTree(p-child i); r=r-rchild; else return q; else if(p-child2!=NULL) r-rchild=TreetoBiTree(p-child 2); r=r-rchild; else return q; else if(p-child1!=NULL) q-lchild=TreetoBiTree(p-child1);/把樹的第二個孩子賦給二叉樹的左孩子 BiTNode* r=q-lchild; if(p-child2!=NULL) r-rchild=TreetoBiTree(p-child 2); else return q; else if(p-child2!=NULL) q-lchild=TreetoBiTree(p-child1);/把樹的第三個孩子賦給二叉樹的左孩子 return q; Tree BiTreetoTree(BiTree &q) int i; if(q=NULL)return NULL; Node* p=(Node*)malloc(sizeof(ElemType); p-data=q-data;/根賦值 for(i=0;ichildi=NULL; if(q-lchild!=NULL) p-child0=BiTreetoTree(q-lchild); BiTNode* r=q-lchild; for(i=1;irchild!=NULL) p-childi=BiTreetoTree(r-rchild ); r=r-rchild ; return p; void push(seqstack* s,BiTree p) /進棧 s-data+s-top=p; BiTree pop(seqstack* s) /出棧 if(s-top!=-1) /非遞歸遍歷中，top初始值為-1 s-top-; return (s-datas-top+1); else return NULL; void PreOrderPrint(BiTree &q) if(q!=NULL) printf(%c,q-data); PreOrderPrint(q-lchild); PreOrderPrint(q-rchild); /二叉樹中序遍歷 非遞歸 算法 void inorder1(BiTree p) seqstack s; s.top=-1; while(p!=NULL)|(s.top!=-1) while(p) push(&s,p); p=p-lchild; /子樹根結(jié)點全部進棧 if(s.top!=-1) p=pop(&s); printf(%c,p-data); /輸出根結(jié)點，其實也就是左孩子或右孩子(沒有孩子的根結(jié)點是它父親的左或右孩子） p=p-rchild; /