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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 設(shè)計題目：_樹與二叉樹的轉(zhuǎn)換_ 姓名：_李錦_ 學(xué)號：_211214011_ 專業(yè)：_物聯(lián)網(wǎng)工程_ 院系：_計算機(jī)科學(xué)與技術(shù)_ 班級：_1205_ 指導(dǎo)教師：_高秀梅_2014年 2 月 14 日 目 錄一、問題描述2二、基本要求2三、概要設(shè)計2四、數(shù)據(jù)結(jié)構(gòu)設(shè)計2五、算法設(shè)計31、算法分析32、算法實現(xiàn)3六、程序測試與實現(xiàn)61、函數(shù)之間的調(diào)用關(guān)系62、主程序63、測試數(shù)據(jù)84、測試結(jié)果8七、調(diào)試分析10八、遇到的問題及解決辦法10九、心得體會10一、問題描述完成樹與二叉樹的轉(zhuǎn)換二、基本要求1、 樹采用雙親表示法2、 能夠?qū)滢D(zhuǎn)換為二叉樹3、 對轉(zhuǎn)換的二叉樹進(jìn)行算法設(shè)計統(tǒng)計

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

3、ueBTree *&q) 初始化二叉樹隊列（7）void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot) /樹轉(zhuǎn)化為二叉樹ctroot指向樹的根節(jié)點，btroot,指向二叉樹的根四、數(shù)據(jù)結(jié)構(gòu)設(shè)計struct CTreeNode/樹節(jié)點的類型 char data;/數(shù)據(jù)域，采用char星 struct CTreeNode *childrenDEGREE;/指向孩子節(jié)點的指針域;struct BTreeNode char data;/數(shù)據(jù)域 BTreeNode *lchild,*rchild;/左右孩子節(jié)點的指針;/樹隊列結(jié)構(gòu)體類

4、型struct QueueCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/結(jié)構(gòu)體指針數(shù)組，存放節(jié)點的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear;/二叉樹隊列結(jié)構(gòu)類型struct QueueBTree BTreeNode *BTreeArrayMAX_NODE_NUM;/結(jié)構(gòu)體指針數(shù)組，存放節(jié)點的地址 /struct nodeBTree *next; int BTreeFront,BTreeRear;五、算法設(shè)計 1、算法分析 將樹轉(zhuǎn)換成二叉樹的步驟是： （1）加線。就是在所有兄弟結(jié)點之間加一條連線；

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

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

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

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

9、信息圖樹的前序遍歷樹的結(jié)構(gòu)圖二叉樹的節(jié)點孩子數(shù)二叉樹的深度二叉樹的前序遍歷二叉樹的結(jié)構(gòu)圖輸出結(jié)果退出程序六、程序測試與實現(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、測試數(shù)據(jù)a b c d e 4、測試結(jié)果七、調(diào)試分析首先根據(jù)指令，輸入信息，生成一個樹后，再將生成的樹轉(zhuǎn)化成二叉樹，然后輸出二叉樹的結(jié)構(gòu)圖,二叉樹的前序遍歷結(jié)果以及二叉樹的深度和節(jié)點孩子數(shù)八、遇到的問題及解決辦法調(diào)試時遇到諸多問題，其中最主要的問題是死循環(huán)問題，在非遞歸遍歷時，容易進(jìn)入死循環(huán)，經(jīng)過查找資料、分步調(diào)試最終找到循環(huán)結(jié)束條件，順利解決各個難題。九、心得體會通過本次課程設(shè)計，我發(fā)現(xiàn)，有關(guān)一個課題的所有知識不僅僅是在課本上，多查閱一些資料能夠更好的完成課題，這就需要一種能力，即自學(xué)能力。本次課程設(shè)計還讓我認(rèn)識到自己的缺點。本次選的課題