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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 設(shè)計(jì)題目：_樹(shù)與二叉樹(shù)的轉(zhuǎn)換_ 姓名：_李錦_ 學(xué)號(hào)：_211214011_ 專業(yè)：_物聯(lián)網(wǎng)工程_ 院系：_計(jì)算機(jī)科學(xué)與技術(shù)_ 班級(jí)：_1205_ 指導(dǎo)教師：_高秀梅_2014年 2 月 14 日 目 錄一、問(wèn)題描述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八、遇到的問(wèn)題及解決辦法10九、心得體會(huì)10一、問(wèn)題描述完成樹(shù)與二叉樹(shù)的轉(zhuǎn)換二、基本要求1、 樹(shù)采用雙親表示法2、 能夠?qū)?shù)轉(zhuǎn)換為二叉樹(shù)3、 對(duì)轉(zhuǎn)換的二叉樹(shù)進(jìn)行算法設(shè)計(jì)統(tǒng)計(jì)

2、人一結(jié)點(diǎn)的孩子數(shù)4、 利用轉(zhuǎn)換的二叉樹(shù)計(jì)算樹(shù)的高度三、概要設(shè)計(jì)操作集合：(1) CTreeNode *SearchCTree(CTreeNode *root ,char data) 查找樹(shù)結(jié)點(diǎn)(2) CTreeNode *CreateSTree() 生成樹(shù)(3) void preorderTree(CTreeNode *ctroot) 樹(shù)的遍歷(4) void PrintTree(CTreeNode *troot,int depth) 樹(shù)的輸出(5 void initQueueCTree(QueueCTree *&q) 初始化樹(shù)隊(duì)列(6) void initQueueBTree(Que

3、ueBTree *&q) 初始化二叉樹(shù)隊(duì)列（7）void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot) /樹(shù)轉(zhuǎn)化為二叉樹(shù)ctroot指向樹(shù)的根節(jié)點(diǎn)，btroot,指向二叉樹(shù)的根四、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)struct CTreeNode/樹(shù)節(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)的指針;/樹(shù)隊(duì)列結(jié)構(gòu)體類

4、型struct QueueCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/結(jié)構(gòu)體指針數(shù)組，存放節(jié)點(diǎn)的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear;/二叉樹(shù)隊(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、算法分析 將樹(shù)轉(zhuǎn)換成二叉樹(shù)的步驟是： （1）加線。就是在所有兄弟結(jié)點(diǎn)之間加一條連線；

5、 （2）抹線。就是對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn)，只保留他與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪除它與其它孩子結(jié)點(diǎn)之間的連線； （3）旋轉(zhuǎn)。就是以樹(shù)的根結(jié)點(diǎn)為軸心，將整棵樹(shù)順時(shí)針旋轉(zhuǎn)一定角度，使之結(jié)構(gòu)層次分明。2、算法實(shí)現(xiàn)void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)/樹(shù)轉(zhuǎn)化為二叉樹(shù)ctroot指向樹(shù)的根節(jié)點(diǎn)，btroot,指向二叉樹(shù)的跟 QueueCTree *VisitedCTreeNodes; QueueBTree *VisitedBTreeNodes;/輔助隊(duì)列 initQueueCTree(VisitedCTreeNodes); ini

6、tQueueBTree(VisitedBTreeNodes);/初始化隊(duì)列 CTreeNode *ctnode; BTreeNode *btnode,*p,*LastSibling; int i; btroot=new BTreeNode;/添加開(kāi)辟內(nèi)存空間語(yǔ)句 btroot->data=ctroot->data;/樹(shù)的根節(jié)點(diǎn)作為二叉樹(shù)的根節(jié)點(diǎn) btroot->lchild=btroot->rchild=NULL; addQueueCTree(VisitedCTreeNodes,ctroot);/樹(shù)的跟節(jié)點(diǎn)入隊(duì) addQueueBTree(VisitedBTreeNod

7、es,btroot);/二叉樹(shù)的跟節(jié)點(diǎn)入隊(duì) while(!QueueCTreeEmpty(VisitedCTreeNodes) ctnode=delQueueCTree(VisitedCTreeNodes);/樹(shù)節(jié)點(diǎn)出隊(duì) btnode=delQueueBTree(VisitedBTreeNodes);/二叉樹(shù)節(jié)點(diǎn)出隊(duì) for(i=0;i<DEGREE;i+)/訪問(wèn)節(jié)點(diǎn)所有的孩子節(jié)點(diǎn) if(ctnode->childreni=NULL)/孩子節(jié)點(diǎn)訪問(wèn)完畢 break; p=new BTreeNode;/分配二叉樹(shù)節(jié)點(diǎn) p->data=ctnode->childreni-&

8、gt;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);/樹(shù)節(jié)點(diǎn)進(jìn)隊(duì)列 addQueueBTree(VisitedBTreeNodes,p);/二叉樹(shù)節(jié)點(diǎn)進(jìn)門(mén)隊(duì)列 3、算法流程圖開(kāi)始主菜單輸入樹(shù)的節(jié)點(diǎn)數(shù)輸入信息生成樹(shù)輸入樹(shù)的節(jié)點(diǎn)數(shù)樹(shù)轉(zhuǎn)化為二叉樹(shù)樹(shù)的信息圖二叉樹(shù)的

9、信息圖樹(shù)的前序遍歷樹(shù)的結(jié)構(gòu)圖二叉樹(shù)的節(jié)點(diǎn)孩子數(shù)二叉樹(shù)的深度二叉樹(shù)的前序遍歷二叉樹(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'

10、) while(1) i=Treemenu(); switch(i) case '1':Tree=CreateSTree();break; case '2':PrintTree(Tree,10);cout<<"ntt按任意鍵返回.n" getch();break; case '3':preorderTree(Tree);cout<<"ntt按任意鍵返回.n" getch();break; case '4':goto p;break; if(n='2')

11、 TreeToBTree(Tree,BTree); while(1) j=Btreemenu(); switch(j) case '1':PrintIn(BTree,5);cout<<"ntt按任意鍵返回.n" getch();break; case '2':Preorder(BTree);cout<<"ntt按任意鍵返回.n" getch();break; case '3':cout<<FindDepth(BTree);cout<<"ntt按任意鍵

12、返回.n" getch();break; case '4':count(BTree);cout<<"ntt按任意鍵返回.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è)樹(shù)后，再將生成的樹(shù)轉(zhuǎn)化成二叉樹(shù)，然后輸出二叉樹(shù)的結(jié)構(gòu)圖,二叉樹(shù)的前序遍歷結(jié)果以及二叉樹(shù)的深度和節(jié)點(diǎn)孩子數(shù)八、遇到的問(wèn)題及解決辦法調(diào)試時(shí)遇到諸多問(wèn)題，其中最主要的問(wèn)題是死循環(huán)問(wèn)題，在非遞歸遍歷時(shí)，容易進(jìn)入死循環(huán)，經(jīng)過(guò)查找資料、分步調(diào)試最終找到循環(huán)結(jié)束條件，順利解決各個(gè)難題。九、心得體會(huì)通過(guò)本次課程設(shè)計(jì)，我發(fā)現(xiàn)，有關(guān)一個(gè)課題的所有知識(shí)不僅僅是在課本上，多查閱一些資料能夠更好的完成課題，這就需要一種能力，即自學(xué)能力。本次課程設(shè)計(jì)還讓我認(rèn)識(shí)到自己的缺點(diǎn)。本次選的課題