數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)樹與二叉樹的轉(zhuǎn)換.doc

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 設(shè)計(jì)題目：_樹與二叉樹的轉(zhuǎn)換_ 姓名：_李錦_ 學(xué)號(hào)：_211214011_ 專業(yè)：_物聯(lián)網(wǎng)工程_ 院系：_計(jì)算機(jī)科學(xué)與技術(shù)_ 班級(jí)：_1205_ 指導(dǎo)教師：_高秀梅_2014年 2 月 14 日 目 錄一、問題描述2二、基本要求2三、概要設(shè)計(jì)2四、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)2五、算法設(shè)計(jì)31、算法分析32、算法實(shí)現(xiàn)3六、程序測(cè)試與實(shí)現(xiàn)61、函數(shù)之間的調(diào)用關(guān)系62、主程序63、測(cè)試數(shù)據(jù)84、測(cè)試結(jié)果8七、調(diào)試分析10八、遇到的問題及解決辦法10九、心得體會(huì)10一、問題描述完成樹與二叉樹的轉(zhuǎn)換二、基本要求1、 樹采用雙親表示法2、 能夠?qū)滢D(zhuǎn)換為二叉樹3、 對(duì)轉(zhuǎn)換的二叉樹進(jìn)行算法設(shè)計(jì)統(tǒng)計(jì)人一結(jié)點(diǎn)的孩子數(shù)4、 利用轉(zhuǎn)換的二叉樹計(jì)算樹的高度三、概要設(shè)計(jì)操作集合：(1) CTreeNode *SearchCTree(CTreeNode *root ,char data) 查找樹結(jié)點(diǎn)(2) CTreeNode *CreateSTree() 生成樹(3) void preorderTree(CTreeNode *ctroot) 樹的遍歷(4) void PrintTree(CTreeNode *troot,int depth) 樹的輸出(5 void initQueueCTree(QueueCTree *&q) 初始化樹隊(duì)列(6) void initQueueBTree(QueueBTree *&q) 初始化二叉樹隊(duì)列（7）void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot) /樹轉(zhuǎn)化為二叉樹ctroot指向樹的根節(jié)點(diǎn)，btroot,指向二叉樹的根四、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)struct CTreeNode/樹節(jié)點(diǎn)的類型 char data;/數(shù)據(jù)域，采用char星 struct CTreeNode *childrenDEGREE;/指向孩子節(jié)點(diǎn)的指針域;struct BTreeNode char data;/數(shù)據(jù)域 BTreeNode *lchild,*rchild;/左右孩子節(jié)點(diǎn)的指針;/樹隊(duì)列結(jié)構(gòu)體類型struct QueueCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/結(jié)構(gòu)體指針數(shù)組，存放節(jié)點(diǎn)的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear;/二叉樹隊(duì)列結(jié)構(gòu)類型struct QueueBTree BTreeNode *BTreeArrayMAX_NODE_NUM;/結(jié)構(gòu)體指針數(shù)組，存放節(jié)點(diǎn)的地址 /struct nodeBTree *next; int BTreeFront,BTreeRear;五、算法設(shè)計(jì) 1、算法分析 將樹轉(zhuǎn)換成二叉樹的步驟是： （1）加線。就是在所有兄弟結(jié)點(diǎn)之間加一條連線； （2）抹線。就是對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留他與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪除它與其它孩子結(jié)點(diǎn)之間的連線； （3）旋轉(zhuǎn)。就是以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定角度，使之結(jié)構(gòu)層次分明。2、算法實(shí)現(xiàn)void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)/樹轉(zhuǎn)化為二叉樹ctroot指向樹的根節(jié)點(diǎn)，btroot,指向二叉樹的跟 QueueCTree *VisitedCTreeNodes; QueueBTree *VisitedBTreeNodes;/輔助隊(duì)列 initQueueCTree(VisitedCTreeNodes); initQueueBTree(VisitedBTreeNodes);/初始化隊(duì)列 CTreeNode *ctnode; BTreeNode *btnode,*p,*LastSibling; int i; btroot=new BTreeNode;/添加開辟內(nèi)存空間語句 btroot-data=ctroot-data;/樹的根節(jié)點(diǎn)作為二叉樹的根節(jié)點(diǎn) btroot-lchild=btroot-rchild=NULL; addQueueCTree(VisitedCTreeNodes,ctroot);/樹的跟節(jié)點(diǎn)入隊(duì) addQueueBTree(VisitedBTreeNodes,btroot);/二叉樹的跟節(jié)點(diǎn)入隊(duì) while(!QueueCTreeEmpty(VisitedCTreeNodes) ctnode=delQueueCTree(VisitedCTreeNodes);/樹節(jié)點(diǎn)出隊(duì) btnode=delQueueBTree(VisitedBTreeNodes);/二叉樹節(jié)點(diǎn)出隊(duì) for(i=0;ichildreni=NULL)/孩子節(jié)點(diǎn)訪問完畢 break; p=new BTreeNode;/分配二叉樹節(jié)點(diǎn) p-data=ctnode-childreni-data; p-lchild=p-rchild=NULL; if(i=0) btnode-lchild=p;/長(zhǎng)子，作為父節(jié)點(diǎn)的做孩子 else LastSibling-rchild=p;/作為上一個(gè)兄弟節(jié)點(diǎn)的右孩子 LastSibling=p; addQueueCTree(VisitedCTreeNodes,ctnode-childreni);/樹節(jié)點(diǎn)進(jìn)隊(duì)列 addQueueBTree(VisitedBTreeNodes,p);/二叉樹節(jié)點(diǎn)進(jìn)門隊(duì)列 3、算法流程圖開始主菜單輸入樹的節(jié)點(diǎn)數(shù)輸入信息生成樹輸入樹的節(jié)點(diǎn)數(shù)樹轉(zhuǎn)化為二叉樹樹的信息圖二叉樹的信息圖樹的前序遍歷樹的結(jié)構(gòu)圖二叉樹的節(jié)點(diǎn)孩子數(shù)二叉樹的深度二叉樹的前序遍歷二叉樹的結(jié)構(gòu)圖輸出結(jié)果退出程序六、程序測(cè)試與實(shí)現(xiàn)1、函數(shù)之間的調(diào)用關(guān)系Main()Menu()PrintTree(Tree,10)preorderTree(Tree)CTreeNode *Tree;TreeToBTree(Tree,BTree)Preorder(BTree)PrintIn(BTree,5)2、主程序 int main()CTreeNode *Tree; BTreeNode *BTree;int x=0; char n,i,j,k; while(1) p:n=menu(); if(n=1) while(1) i=Treemenu(); switch(i) case 1:Tree=CreateSTree();break; case 2:PrintTree(Tree,10);coutntt按任意鍵返回.n; getch();break; case 3:preorderTree(Tree);coutntt按任意鍵返回.n; getch();break; case 4:goto p;break; if(n=2) TreeToBTree(Tree,BTree); while(1) j=Btreemenu(); switch(j) case 1:PrintIn(BTree,5);coutntt按任意鍵返回.n; getch();break; case 2:Preorder(BTree);coutntt按任意鍵返回.n; getch();break; case 3:coutFindDepth(BTree);coutntt按任意鍵返回.n; getch();break; case 4:count(BTree);coutntt按任意鍵返回.n; getch();break; case 5:goto p;break; if(n=3) break; return 0;3、測(cè)試數(shù)據(jù)a b c d e 4、測(cè)試結(jié)果七、調(diào)試分析首先根據(jù)指令，輸入信息，生成一個(gè)樹后，再將生成的樹轉(zhuǎn)化成二叉樹，然后輸出二叉樹的結(jié)構(gòu)圖,二叉樹的前序遍歷結(jié)果以及二叉樹的深度和節(jié)點(diǎn)孩子數(shù)八、遇到的問題及解決辦法調(diào)試時(shí)遇到諸多問題，其中最主要的問題是死循環(huán)問題，在非遞歸遍歷時(shí)，容易進(jìn)入死循環(huán)，經(jīng)過查找資料、分步調(diào)試最終找到循環(huán)結(jié)束條件，順利解決各個(gè)難題。九、心得體會(huì)通過本次課程設(shè)計(jì)，我發(fā)現(xiàn)，有關(guān)一個(gè)課題的所有知識(shí)不僅僅是在課本上，多查閱一些資料能夠更好的完成課題，這就需要一種能力，即自學(xué)能力。本次課程設(shè)計(jì)還讓我認(rèn)識(shí)到自己的缺點(diǎn)。本次選的課題是二叉樹的遍歷，