《二叉樹的應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)樣本.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《二叉樹的應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)樣本.doc（22頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、信息科學(xué)與技術(shù)學(xué)院數(shù)據(jù)構(gòu)造課程設(shè)計(jì)報(bào)告題目名稱：二叉樹應(yīng)用專業(yè)班級：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)生姓名：陳 杰學(xué)生學(xué)號：指引教師：高 攀完畢日期：-04目 錄1、課程設(shè)計(jì)目、課程設(shè)計(jì)題目、題目規(guī)定21.1課程設(shè)計(jì)目31.2課程設(shè)計(jì)題目31.3題目規(guī)定32課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告內(nèi)容:43課程設(shè)計(jì)原程序代碼:44運(yùn)營成果165. 課程設(shè)計(jì)總結(jié)216參照書目221課程設(shè)計(jì)目1.1課程設(shè)計(jì)目:通過此前學(xué)習(xí)以及查看有關(guān)資料,按著題目規(guī)定編寫程序,進(jìn)一步加強(qiáng)對編程訓(xùn)練,使得自己掌握某些將課本知識轉(zhuǎn)化為實(shí)際應(yīng)用當(dāng)中.在整個(gè)程序中,重要應(yīng)用是鏈表,但是也運(yùn)用了類.通過兩種辦法解決既有問題.1.2課程設(shè)計(jì)題目：二叉樹應(yīng)用1.3

2、題目規(guī)定:1. 建立二叉樹二叉鏈表存儲算法2. 二叉樹先序遍歷，中序遍歷和后序遍歷輸出3. 非遞歸先序遍歷，中序遍歷4. 二叉樹層次遍歷5. 判斷此二叉樹與否是完全二叉樹6. 二叉樹左右孩子互換2課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告內(nèi)容:7. 通過遞歸對二叉樹進(jìn)行遍歷。二叉樹非遞歸遍歷重要采用運(yùn)用隊(duì)進(jìn)行遍歷。此后判斷此二叉樹與否是完全二叉樹也才采用隊(duì)，而二叉樹左右孩子互換則采用是一種簡樸遞歸。3課程設(shè)計(jì)原程序代碼:#includeusing namespace std;#define MAXSIZE 100int sign=0;void menu();/typedef struct BiTNodechar dat

3、a;BiTNode *left_child,*right_child;BiTNode,*BiTree;int CreateBiTree(BiTree &T)/創(chuàng)立二叉樹 char ch; coutch; if(ch=#) T=NULL; else if(!(T=new BiTNode) coutdata=ch; CreateBiTree(T-left_child);/create leftchild CreateBiTree(T-right_child)； /create rightchild return 1;/判斷此樹與否是完全二叉樹int LevelOrder1(BiTree &T)Bi

4、Tree stackMAXSIZE;BiTreep;int front,rear;front=-1,rear=0;stackrear=T;while(rear!=front)front+;p=stackfront;if(p-left_child=NULL)&(p-right_child)sign=1;if(p-left_child)rear+;stackrear=p-left_child;if(p-right_child)rear+;stackrear=p-right_child;return 1;void Output(BiTree &T) /輸出二叉樹if(!T) cout空樹!n;ret

5、urn ; /空樹coutdataleft_child) Output(T-left_child)；/輸出左子樹if(T-right_child)Output(T-right_child);/輸出右子樹int Depth(BiTree &T) /求樹深int i,j;if(!T) return 0;i = Depth(T-left_child);j = Depth(T-right_child);return (ij?i:j) + 1;int Node(BiTree &T)/求結(jié)點(diǎn)數(shù)if(!T) return 0;return 1+Node(T-left_child)+Node(T-right_

6、child);int Leaf(BiTree &T) /求葉子結(jié)點(diǎn)if(!T) return 0;if(!T-left_child&!T-right_child) return 1;/僅有根結(jié)點(diǎn)return Leaf(T-left_child)+Leaf(T-right_child);/返回葉子結(jié)點(diǎn)數(shù)目void PreOrder(BiTree &T) /先序遍歷算法 DLRif(!T) return ；/遞歸調(diào)用結(jié)束條件coutdataleft_child);/先序遞歸遍歷T左子樹PreOrder(T-right_child);/先序遞歸遍歷T右子樹void InOrder(BiTree &T

7、)/中序遍歷算法 LDRif(!T) return ;InOrder(T-left_child);coutdataright_child);void PostOrder(BiTree &T)/后序遍歷算法 LRDif(!T) return ;PostOrder(T-left_child);PostOrder(T-right_child);coutdata ;/非遞歸先序遍歷int NRPreOrder(BiTree &T)BiTree stack100,p;int top;if(T=NULL)return 1;top=-1;p=T;while(!(p=NULL&top=-1)while(p!=

8、NULL)coutdata ;if(top100-1)top+;stacktop=p;else cout棧溢出left_child;if(top=-1)return 1;elsep=stacktop;top-;p=p-right_child; return 1;/非遞歸中序遍歷int NRInOrder(BiTree &T)BiTree stack100,p;int top;if(T=NULL)return 1;top=-1;p=T;while(!(p=NULL&top=-1)while(p!=NULL)if(top100-1)top+;stacktop=p;else cout棧溢出left_

9、child;if(top=-1)return 1;elsep=stacktop;coutdataright_child;return 1;/層次遍歷void LevelOrder(BiTree &T)BiTree queue100;int front,rear;if(T=NULL)return;front=-1;rear=0;queuerear=T;while(front!=rear)front+;coutdataleft_child!=NULL)rear+;queuerear=queuefront-left_child;if(queuefront-right_child!=NULL)rear

10、+;queuerear=queuefront-right_child;/*左右子樹互換*/*將結(jié)點(diǎn)左右子樹互換*/*BiTNode *swap(BiTNode &T) BiTNode *t,*t1,*t2；if(T=NULL) t=NULL；else t=(BiTNode *)malloc(sizeof(BiTNode)；t-data=T-data；t1=swap(T-left_child)；t2=swap(T-right_child)；t-left_child=t2；t-right_child=t1； return(t)； void print(BiTNode &T) if(T!=NULL)

11、 printf(%c,T-data)； if(T-left_child!=NULL|T-right_child!=NULL) printf()； print(b-left_child)； if(b-right_child!=NULL)printf(，)； print(b-right_child)； printf()； */int PreOrderTraverse(BiTree T) if(!T)return 0;BiTree t;if (T-left_child|T-right_child) t=T-left_child;T-left_child=T-right_child;T-right_child=t;PreOrderTraverse(T-left_child);PreOrderTraverse(T-right_child);return 0;/菜單void menu() cout*