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

數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計成果報告樹與二叉樹轉(zhuǎn)換的實現(xiàn)學生學號： 學生姓名： 學 院： 計算機學院 專業(yè)班級： 軟件工程1341 專業(yè)課程： 數(shù)據(jù)結(jié)構(gòu)與算法 指導教師： 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è)計源代碼的排版總 評 成 績指導教師評語： 日期： 年 月 日目 錄1 課程設(shè)計目標與任務(wù)11.1 課程設(shè)計目標11.2 課程設(shè)計任務(wù)12 分析與設(shè)計22.1 題目需求分析22.2 存儲結(jié)構(gòu)設(shè)計22.3 算法描述32.4 程序流程圖42.5 測試程序說明63 程序清單104 測試164.1 測試數(shù)據(jù)164.2 測試結(jié)果分析165 總結(jié)18參考文獻19附 錄201 課程設(shè)計目標與任務(wù)1.1 課程設(shè)計目標數(shù)據(jù)結(jié)構(gòu)課程設(shè)計是在學完數(shù)據(jù)結(jié)構(gòu)課程之后的實踐教學環(huán)節(jié)。該實踐教學是軟件設(shè)計的綜合訓練,包括問題分析，總體結(jié)構(gòu)設(shè)計用戶界面設(shè)計，程序設(shè)計基本技能和技巧。要在設(shè)計中逐步提高程序設(shè)計能力培養(yǎng)科學的軟件工作方法學生通過數(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）通過上機實習,驗證自己設(shè)計的算法的正確性，學會有效利用基本調(diào)試方法，迅速找出程序代碼中的錯誤并且修改；（3）培養(yǎng)算法分析能力，分析所設(shè)計算法的時間復雜度和空間復雜度，進一步提高程序設(shè)計水平；（4）盡可能借助語言環(huán)境實現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖形方式顯示出來，將復雜的運行過程以動態(tài)方式顯示出來，獲得算法的直觀感受。1.2 課程設(shè)計任務(wù)設(shè)計樹與二叉樹轉(zhuǎn)換的相關(guān)函數(shù)庫，以便在程序設(shè)計中調(diào)用，要求：（1）實現(xiàn)樹與二叉樹的轉(zhuǎn)換；（2）最好能借助語言環(huán)境實現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖形方式顯示出來，將復雜的運行過程以動態(tài)方式顯示出來；（3）給出若干例程，演示通過調(diào)用自己所縮寫程序來實現(xiàn)相關(guān)問題的求解。2 分析與設(shè)計2.1 題目需求分析本程序的主要功能是進行樹與二叉樹的轉(zhuǎn)換，其中包含樹的結(jié)構(gòu)體的建立，樹隊列的結(jié)構(gòu)體的建立，以及對樹與二叉樹的遍歷，其中包含遞歸算法的使用，還有樹隊列和二叉樹隊列的初始化、判斷是否為空、入隊和出隊等操作，其中隊列能為二叉樹遍歷提供先進先出的訪問條件。2.2 存儲結(jié)構(gòu)設(shè)計樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)樹的元素之間是一對多的層次關(guān)系，常用的有三種存儲結(jié)構(gòu)，分別是：雙親表示法，孩子鏈表表示法，孩子兄弟表示法。實現(xiàn)：每個結(jié)點含兩個域：數(shù)據(jù)域：存放結(jié)點本身信息。雙親域：指示本結(jié)點的雙親結(jié)點在數(shù)組中位置。本程序的存儲結(jié)構(gòu)為雙親表示法和兄弟表示法，具體如下： typedef struct st1/樹結(jié)點的類型 char data;/數(shù)據(jù)域，采用char struct st1 *childrenDEGREE;/指向孩子結(jié)點的指針域CTreeNode;typedef struct st2 char data;/數(shù)據(jù)域 struct st2 *lchild,*rchild;/左右孩子結(jié)點的指針BTreeNode;存儲結(jié)構(gòu)圖如圖2-1。2-1存儲結(jié)構(gòu)圖2.3 算法描述將樹轉(zhuǎn)換成二叉樹：加線：在兄弟之間加一連線。抹線：對每個結(jié)點，除了其左孩子外，去除其與其余孩子之間的關(guān)系。旋轉(zhuǎn)：以樹的根結(jié)點為軸心，將整樹順時針轉(zhuǎn)45。具體如圖2-2所示。圖2-2 樹轉(zhuǎn)化為二叉樹將二叉樹轉(zhuǎn)換成樹： 加線：若p結(jié)點是雙親結(jié)點的左孩子，則將p的右孩子，右孩子的右孩子沿分支找到的所有右孩子，都與p的雙親用線連起來 。 抹線：抹掉原二叉樹中雙親與右孩子之間的連線。 調(diào)整：將結(jié)點按層次排列，形成樹結(jié)構(gòu)。具體如圖2-3所示。圖2-3 二叉樹轉(zhuǎn)化為樹2.4 程序流程圖設(shè)計程序的第一步是創(chuàng)建樹，即數(shù)的結(jié)構(gòu)體的建立，然后采用遞歸法法進行樹的先序遍歷，先遍歷根結(jié)點，輸入樹的結(jié)點數(shù)量，孩子結(jié)點及其父親結(jié)點的數(shù)據(jù)，建立數(shù)隊列、二叉樹隊列。采用結(jié)構(gòu)體指針數(shù)組，存放結(jié)點的地址，完成樹與二叉樹隊列的初始化、入隊、判空、出隊等操作。具體流程如下圖2-4。開始創(chuàng)建樹建立數(shù)隊列、二叉樹隊列樹的遍歷樹、二叉樹隊列出隊樹、二叉樹隊列是否為空初始化數(shù)隊列二叉樹隊列數(shù)對列、二叉樹隊列入隊輸入樹結(jié)點數(shù)據(jù)樹轉(zhuǎn)化為二叉樹二叉樹遍歷主函數(shù)輸出轉(zhuǎn)換成二叉樹后的遍歷結(jié)果結(jié)束2-4 程序流程圖2.5 主要程序說明（1）存儲結(jié)構(gòu)：typedef struct st1/樹結(jié)點的類型 char data;/數(shù)據(jù)域，采用char星 struct st1 *childrenDEGREE;/指向孩子結(jié)點的指針域CTreeNode;typedef struct st2 char data;/數(shù)據(jù)域 struct st2 *lchild,*rchild;/左右孩子結(jié)點的指針BTreeNode;（2）設(shè)計程序使之能夠進行樹的先序遍歷，采用遞歸算法。具體設(shè)計代碼如下：void preorderTree(CTreeNode *ctroot)/遍歷每個節(jié)點的操作就是輸出該結(jié)點的data域 CTreeNode *ctchild; int i; coutdata ;/先遍歷根結(jié)點 for(i=0;ichildreni; if(ctchild=NULL) break;/孩子結(jié)點遍歷結(jié)束，退出 else preorderTree(ctchild);/遞歸先序遍歷 （3）設(shè)計程序使之能夠進行二叉樹樹的先序遍歷，運用遞歸調(diào)用。具體設(shè)計代碼如下：void Preorder(BTreeNode *T) if(T) coutdatalchild); Preorder(T-rchild); （4）設(shè)計程序?qū)滢D(zhuǎn)化為二叉樹，這是程序能否完成的關(guān)鍵，也是主要的程序段，具體設(shè)計代碼如下：void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)/樹轉(zhuǎn)化為二叉樹ctroot指向樹的根結(jié)點，btroot,指向二叉樹的根。 QueueCTree *VisitedCTreeNodes; QueueBTree *VisitedBTreeNodes;/輔助隊列 initQueueCTree(VisitedCTreeNodes); initQueueBTree(VisitedBTreeNodes);/初始化隊列 CTreeNode *ctnode; BTreeNode *btnode,*p,*LastSibling; int i; btroot=(BTreeNode *)malloc(sizeof(BTreeNode);/添加開辟內(nèi)存空間語句 btroot-data=ctroot-data;/樹的根節(jié)點作為二叉樹的根結(jié)點 btroot-lchild=btroot-rchild=NULL; addQueueCTree(VisitedCTreeNodes,ctroot);/樹的跟結(jié)點入隊 addQueueBTree(VisitedBTreeNodes,btroot);/二叉樹的跟結(jié)點入隊 while(!QueueCTreeEmpty(VisitedCTreeNodes) ctnode=delQueueCTree(VisitedCTreeNodes);/樹結(jié)點出隊 btnode=delQueueBTree(VisitedBTreeNodes);/二叉樹節(jié)點出隊 for(i=0;ichildreni=NULL)/孩子結(jié)點訪問完畢 break; p=(BTreeNode *)malloc(sizeof(BTreeNode);/分配二叉樹結(jié)點 p-data=ctnode-childreni-data; p-lchild=p-rchild=NULL; if(i=0) btnode-lchild=p;/長子，作為父結(jié)點的做孩子 else LastSibling-rchild=p;/作為上一個兄弟結(jié)點的右孩子 LastSibling=p; addQueueCTree(VisitedCTreeNodes,ctnode-childreni);/樹節(jié)點進隊列 addQueueBTree(VisitedBTreeNodes,p);/二叉樹節(jié)點進門隊列 3 程序清單#includeusing namespace std;#include#define DEGREE 5 /樹的高度#define NULL 0#define QUEUESIZE 10#define MAX_NODE_NUM 100typedef struct st1/樹結(jié)點的類型 char data;/數(shù)據(jù)域，采用char星 struct st1 *childrenDEGREE;/指向孩子結(jié)點的指針域CTreeNode;typedef struct st2 char data;/數(shù)據(jù)域 struct st2 *lchild,*rchild;/左右孩子結(jié)點的指針BTreeNode;CTreeNode *SearchCTree(CTreeNode *root ,char data) int i; CTreeNode *returnNode; if(root-data=data) return root; else for(i=0;ichildreni=NULL) return NULL; else returnNode=SearchCTree(root-childreni,data);/遞歸查找 if(returnNode!=NULL) return returnNode; CTreeNode *CreateSTree() int i,j,k; char data, parent; CTreeNode *root,*parentNode,*node; coutj; if(j=0) return NULL;/空樹，結(jié)束函數(shù) coutdata; fflush(stdin); root=(CTreeNode *)malloc(sizeof(CTreeNode); root-data=data; for(i=0;ichildreni=NULL; for(i=2;i=j;i+)/依次輸入每個結(jié)點的信息 cout請輸入idataparent;/切記當以%c號格式輸入數(shù)據(jù)時候，不要輸入空格 fflush(stdin); node=(CTreeNode *)malloc(sizeof(CTreeNode); node-data=data; for(k=0;kchildrenk=NULL; /printf(驗證parent=%cn,parent); parentNode=SearchCTree(root,parent);/查找指定數(shù)據(jù)的結(jié)點 for(k=0;kchildrenk=NULL) parentNode-childrenk=node; break; return root;void preorderTree(CTreeNode *ctroot)/遍歷每個節(jié)點的操作就是輸出該結(jié)點的data域 CTreeNode *ctchild; int i; coutdata ;/先遍歷根結(jié)點 for(i=0;ichildreni; if(ctchild=NULL) break;/孩子結(jié)點遍歷結(jié)束，退出 else preorderTree(ctchild);/遞歸先序遍歷 /樹隊列結(jié)構(gòu)體類型typedef struct nodeCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/結(jié)構(gòu)體指針數(shù)組，存放結(jié)點的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear;QueueCTree;/二叉樹隊列結(jié)構(gòu)類型typedef struct nodeBTree BTreeNode *BTreeArrayMAX_NODE_NUM;/結(jié)構(gòu)體指針數(shù)組，存放結(jié)點的地址 /struct nodeBTree *next; int BTreeFront,BTreeRear;QueueBTree;/初始化樹隊列void initQueueCTree(QueueCTree *&q) q=(QueueCTree *)malloc(sizeof(QueueCTree); q-CTreeFront=q-CTreeRear=0;/初始化二叉樹隊列void initQueueBTree(QueueBTree *&q) q=(QueueBTree *)malloc(sizeof(QueueBTree); q-BTreeFront=q-BTreeRear=0;/樹隊列元素入隊int addQueueCTree(QueueCTree *&q,CTreeNode *ctroot) if(q-CTreeRear+1)%MAX_NODE_NUM=q-CTreeFront)/隊滿 return 0; q-CTreeRear=(q-CTreeRear+1)%MAX_NODE_NUM; q-CTreeArrayq-CTreeRear=ctroot; return 1;/入隊列/二叉樹隊列元素入隊int addQueueBTree(QueueBTree *&q,BTreeNode *btroot) if(q-BTreeRear+1)%MAX_NODE_NUM=q-BTreeFront)/隊滿 return 0; q-BTreeRear=(q-BTreeRear+1)%MAX_NODE_NUM; q-BTreeArrayq-BTreeRear=btroot; return 1;/入隊列/樹的隊列判空int QueueCTreeEmpty(QueueCTree *q) return(q-CTreeFront=q-CTreeRear);/二叉樹隊列判空int QueueBTreeEmpty(QueueBTree *q) return(q-BTreeFront=q-BTreeRear);/樹隊列元素出隊CTreeNode *delQueueCTree(QueueCTree *&q) CTreeNode *ctroot; if(q-CTreeFront=q-CTreeRear)/隊空 return NULL;/返回空指針 q-CTreeFront=(q-CTreeFront+1)%MAX_NODE_NUM; ctroot=q-CTreeArrayq-CTreeFront; return ctroot;/返回結(jié)點/二叉樹隊列元素出隊BTreeNode *delQueueBTree(QueueBTree *&q) BTreeNode *btroot; if(q-BTreeFront=q-BTreeRear)/隊空 return NULL;/返回空指針 q-BTreeFront=(q-BTreeFront+1)%MAX_NODE_NUM; btroot=q-BTreeArrayq-BTreeFront; return btroot;/返回節(jié)點void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)/樹轉(zhuǎn)化為二叉樹ctroot指向樹的根結(jié)點，btroot,指向二叉樹的跟 QueueCTree *VisitedCTreeNodes; QueueBTree *VisitedBTreeNodes;/輔助隊列 initQueueCTree(VisitedCTreeNodes); initQueueBTree(VisitedBTreeNodes);/初始化隊列 CTreeNode *ctnode; BTreeNode *btnode,*p,*LastSibling; int i; btroot=(BTreeNode *)malloc(sizeof(BTreeNode);/添加開辟內(nèi)存空間語句 btroot-data=ctroot-data;/樹的根節(jié)點作為二叉樹的根結(jié)點 btroot-lchild=btroot-rchild=NULL; addQueueCTree(VisitedCTreeNodes,ctroot);/樹的跟結(jié)點入隊 addQueueBTree(VisitedBTreeNodes,btroot);/二叉樹的跟結(jié)點入隊 while(!QueueCTreeEmpty(VisitedCTreeNodes) ctnode=delQueueCTree(VisitedCTreeNodes);/樹結(jié)點出隊 btnode=delQueueBTree(VisitedBTreeNodes);/二叉樹節(jié)點出隊 for(i=0;ichildreni=NULL)/孩子結(jié)點訪問完畢 break; p=(BTreeNode *)malloc(sizeof(BTreeNode);/分配二叉樹結(jié)點 p-data=ctnode-childreni-data; p-lchild=p-rchild=NULL; if(i=0) btnode-lchild=p;/長子，作為父結(jié)點的做孩子 else LastSibling-rchild=p;/作為上一個兄弟結(jié)點的右孩子 LastSibling=p; addQueueCTree(VisitedCTreeNodes,ctnode-childreni);/樹節(jié)點進隊列 addQueueBTree(VisitedBTreeNodes,p);/二叉樹節(jié)點進門隊列 void Preorder(BTreeNode *T) if(T) coutdatalchild); Preorder(T-rchild); int main() CTreeNode *Tree; BTreeNode *BTree; cout創(chuàng)建一棵樹; Tree=CreateSTree(); cout樹的先序遍歷結(jié)果為:; preorderTree(Tree); coutnendl; TreeToBTree(Tree,BTree); cout轉(zhuǎn)換后的二叉樹，先序遍歷的結(jié)果為:endl; Preorder(BTree); coutnendl; return 0;4 測試4.1 測試數(shù)據(jù)根據(jù)樹與二叉樹的的轉(zhuǎn)換，創(chuàng)建一個樹，輸入樹的結(jié)點的數(shù)目7，然后輸入樹根結(jié)點的數(shù)據(jù)a，再依次輸入各個孩子結(jié)點的數(shù)據(jù)以及父親結(jié)點的數(shù)據(jù)ba,ca,da,eb,fc,gc，即可推出樹的結(jié)構(gòu)圖如圖4-1。abdcgfe圖4-1樹的結(jié)構(gòu)圖4.2 測試結(jié)果分析 （1） 根據(jù)顯示，輸入樹的結(jié)點數(shù)量，然后根據(jù)提示依次輸入根節(jié)點數(shù)據(jù)和各個孩子結(jié)點的數(shù)據(jù)以及父親結(jié)點的數(shù)據(jù)，即可得到如圖4-2所示。圖4-2 輸入結(jié)果圖（2）輸入數(shù)據(jù)后，就能得到樹的先序遍歷結(jié)果和二叉樹的先序遍歷結(jié)果，如圖4-3所示。 圖4-3 測試結(jié)果圖5 總結(jié)通過這次課程設(shè)計，使我對樹和二叉樹有了更深的了解和認識，極大地提高了自己的動手能力，尤其是在數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計與實現(xiàn)方面得到了訓練，加深對數(shù)據(jù)結(jié)構(gòu)基本內(nèi)容的理解和應(yīng)用。通過自己動手設(shè)計，也發(fā)現(xiàn)了一些在課堂上容易疏漏的地方，注意到很多應(yīng)該注意的細節(jié)，在專業(yè)知識方面有了很大的提高。但自己在程序設(shè)計方面還存在很大不足，今后還需要更加努力。參考文獻1朱福喜.Java語言程序設(shè)計（第二版）.科學出版社2陳國君等.Java程序設(shè)計基礎(chǔ)（第二版）.清華大學出版社3譚浩強著.C+語言設(shè)計題解與上機指導清華大學出版社4譚浩強著.C+面向?qū)ο蟪绦蛟O(shè)計 清華大學出版社#includeusing namespace std;#include#define DEGREE 5 /樹的高度#define NULL 0#define QUEUESIZE 10#define MAX_NODE_NUM 100typedef struct st1/樹結(jié)點的類型 char data;/數(shù)據(jù)域，采用char星 struct st1 *childrenDEGREE;/指向孩子結(jié)點的指針域CTreeNode;typedef struct st2 char data;/數(shù)據(jù)域 struct st2 *lchild,*rchild;/左右孩子結(jié)點的指針BTreeNode;CTreeNode *SearchCTree(CTreeNode *root ,char data) int i; CTreeNode *returnNode; if(root-data=data) return root; else for(i=0;ichildreni=NULL) return NULL; else returnNode=SearchCTree(root-childreni,data);/遞歸查找 if(returnNode!=NULL) return returnNode; CTreeNode *CreateSTree() int i,j,k; char data, parent; CTreeNode *root,*parentNode,*node; coutj; if(j=0) return NULL;/空樹，結(jié)束函數(shù) coutdata; fflush(stdin); root=(CTreeNode *)malloc(sizeof(CTreeNode); root-data=data; for(i=0;ichildreni=NULL; for(i=2;i=j;i+)/依次輸入每個結(jié)點的信息 cout請輸入idataparent;/切記當以%c號格式輸入數(shù)據(jù)時候，不要輸入空格 fflush(stdin); node=(CTreeNode *)malloc(sizeof(CTreeNode); node-data=data; for(k=0;kchildrenk=NULL; /printf(驗證parent=%cn,parent); parentNode=SearchCTree(root,parent);/查找指定數(shù)據(jù)的結(jié)點 for(k=0;kchildrenk=NULL) parentNode-childrenk=node; break; return root;void preorderTree(CTreeNode *ctroot)/遍歷每個節(jié)點的操作就是輸出該結(jié)點的data域 CTreeNode *ctchild; int i; coutdata ;/先遍歷根結(jié)點 for(i=0;ichildreni; if(ctchild=NULL) break;/孩子結(jié)點遍歷結(jié)束，退出 else preorderTree(ctchild);/遞歸先序遍歷 /樹隊列結(jié)構(gòu)體類型typedef struct nodeCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/結(jié)構(gòu)體指針數(shù)組，存放結(jié)點的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear;QueueCTree;/二叉樹隊列結(jié)構(gòu)類型typedef struct nodeBTree BTreeNode *BTreeArrayMAX_NODE_NUM;/結(jié)構(gòu)體指針數(shù)組，存放結(jié)點的地址 /struct nodeBTree *next; int BTreeFront,BTreeRear;QueueBTree;/初始化樹隊列void initQueueCTree(QueueCTree *&q) q=(QueueCTree *)malloc(sizeof(QueueCTree); q-CTreeFront=q-CTreeRear=0;/初始化二叉樹隊列void initQueueBTree(QueueBTree *&q) q=(QueueBTree *)malloc(sizeof(QueueBTree); q-BTreeFront=q-BTreeRear=0;/樹隊列元素入隊int addQueueCTree(QueueCTree *&q,CTreeNode *ctroot) if(q-CTreeRear+1)%MAX_NODE_NUM=q-CTreeFront)/隊滿 return 0; q-CTreeRear=(q-CTreeRear+1)%MAX_NODE_NUM; q-CTreeArrayq-CTreeRear=ctroot; return 1;/入隊列/二叉樹隊列元素入隊int addQueueBTree(QueueBTree *&q,BTreeNode *btroot) if(q-BTreeRear+1)%MAX_NODE_NUM=q-BTreeFront)/隊滿 return 0; q-BTreeRear=(q-BTreeRear+1)%MAX_NODE_NUM; q-BTreeArrayq-BTreeRear=btroot; return 1;/入隊列/樹的隊列判空int QueueCTreeEmpty(QueueCTree *q) return(q-CTreeFront=q-CTreeRear);/二叉樹隊列判空int QueueBTreeEmpty(QueueBTree *q) return(q-BTreeFront=q-BTreeRear);/樹隊列元素出隊CTreeNode *delQueueCTree(QueueCTree *&q) CTreeNode *ctroot; if(q-CTreeFront=q-CTreeRear)/隊空 return NULL;/返回空指針 q-CTreeFront=(q-CTreeFront+1)%MAX_NODE_NUM; ctroot=q-CTreeArrayq-CTreeFront; return ctroot;/返回結(jié)點/二叉樹隊列元素出隊BTreeNode *delQueueBTree(QueueBTree *&q) BTreeNode *btroot; if(q-BTreeFront=q-BTreeRear)/隊空 return NULL;/返回空指針 q-BTreeFro