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

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