用遞歸和非遞歸算法實(shí)現(xiàn)二叉樹(shù)地三種遍歷

1、word數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報(bào)告三二叉樹(shù)的操作與應(yīng)用實(shí)驗(yàn)?zāi)康氖煜ざ骀湵泶鎯?chǔ)結(jié)構(gòu)的特征，掌握二叉樹(shù)遍歷操作與其應(yīng)用實(shí)驗(yàn)要求題目說(shuō)明：以下題目中一為全體必做，二三任選其一完成 （一）從鍵盤(pán)輸入二叉樹(shù)的擴(kuò)展先序遍歷序列，建立二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu);（二）分別用遞歸和非遞歸算法實(shí)現(xiàn)二叉樹(shù)的三種遍歷;（三）模擬 WindowsXP資源管理器中的目錄管理方式,模擬實(shí)際創(chuàng)建目錄結(jié)構(gòu)，并以二 叉鏈表形式存儲(chǔ)，按照凹入表形式打印目錄結(jié)構(gòu)以擴(kuò)展先序遍歷序列輸入建立 二叉鏈表結(jié)構(gòu)，如如下圖所示：（根本要求：限定目錄名為單字符；擴(kuò)展：允許目 錄名是多字符組合）1 / 20word.分工說(shuō)明一起編寫(xiě)、探討流程圖，根據(jù)

2、流程圖分工編寫(xiě)算法，共同討論修改，最后 上機(jī)調(diào)試修改。.概要設(shè)計(jì)實(shí)現(xiàn)算法，需要鏈表的抽象數(shù)據(jù)類型：ADT Binarytree 數(shù)據(jù)對(duì)象：D是具有一樣特性的數(shù)據(jù)元素的集合數(shù)據(jù)關(guān)系R假如D為空集，如此R為空集，稱binarytree 為空二叉樹(shù)；假如D不為空集，如此R為H, H是如下二元關(guān)系；(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root ,它在關(guān)系H下無(wú)前驅(qū)；假如 D root不為空，如此存在 D root =D1, Dr,且 DWDr 為空集；假如D1不為空，如止匕D1中存在唯一的元素x1, CH,且存 在D1上的關(guān)系H1是H的子集；假如Dr不為空集,如此Dr中存在唯 一的元素Xr, CH,

3、且存在Dr上的關(guān)系Hr為H的子集； H=,H1,Hr;(D1,H1)是一顆符合本定義的二叉樹(shù)，稱為根的左子樹(shù)，(Dr,Hr)是一顆符合本定義的二叉樹(shù)，稱為根的右子樹(shù)。根本操作：Creatbitree(&S , definition)初始條件：definition 給出二叉樹(shù)S的定義操作結(jié)果：按definition構(gòu)造二叉樹(shù)Scounter(T)2 / 20word初始條件：二叉樹(shù)T已經(jīng)存在操作結(jié)果：返回二叉樹(shù)的總的結(jié)點(diǎn)數(shù)onecount(T)初始條件：二叉樹(shù)T已經(jīng)存在操作結(jié)果：返回二叉樹(shù)單分支的節(jié)點(diǎn)數(shù)Clearbintree(S)初始條件：二叉樹(shù)S已經(jīng)存在操作結(jié)果：將二叉樹(shù)S清為空樹(shù)Bitre

4、eempty(S)初始條件：二叉樹(shù)S已經(jīng)存在操作結(jié)果：假如S為空二叉樹(shù)，如此返回TRUE否如此返回FALSEBitreedepth(S,&e)初始條件：二叉樹(shù)S已經(jīng)存在操作結(jié)果：返回S的深度Parent(S)初始條件：二叉樹(shù)S已經(jīng)存在，e是S中的某個(gè)結(jié)點(diǎn)操作結(jié)果：假如e是T的非根結(jié)點(diǎn)，如此返回它的雙親，否如此 返回空Preordertraverse(S)初始條件：二叉樹(shù)S已經(jīng)存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：先序遍歷S,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit 一次且僅一次。一旦visit失敗，如此操作失敗。Inordertraverse (S,&e)初始條件：二叉樹(shù)S已經(jīng)存在，Visit

5、是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：中序遍歷S,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit 一次且僅一次。一旦visit失敗，如此操作失敗。3 / 20wordPostordertraverse (&S,e)初始條件：二叉樹(shù)S已經(jīng)存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。操作結(jié)果：后序遍歷S,對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit 一次且僅一次 一旦visit失敗，如此操作失敗。ADT Binarytree五、詳細(xì)設(shè)計(jì)擴(kuò)展先序遍歷:include include include typedefstruct binarytreechar data;struct binarytree *lchild, *rchild;BiT

6、reeNode, * BiTree;void CreateBiTree(BiTree *bt)char ch;ch=getchar();if (ch= )*bt=NULL;else *bt =(BiTreeNode *)malloc( sizeof (BiTreeNode);4 / 20word(*bt) -data =ch;CreateBiTree( &( * bt) - Ichild);CreateBiTree( &( * bt) - rchild);void PreOder(BiTree root)if (root !=NULL)printf( %4c,root -data);PreOd

7、er(root - lchild);PreOder(root - rchild);main()BiTree root;CreateBiTree( &root);printf(先序遍歷:n);PreOder(root);遞歸算法：#include stdio.h#define PR printf#define ERROR 0#define MAX 1005 / 20word/*卷立各結(jié)構(gòu)體*/*卷立各結(jié)構(gòu)體*/typedefstruct node (char data; /* 數(shù)據(jù)域 */struct node *lchild;struct node *rchild; /*結(jié)點(diǎn)的左右指針，分別指

8、向結(jié)點(diǎn)的左右孩子*/ BTNode;typedef BTNode * DataType;typedefstruct (DataType dataMAX;int top; SeqStack;SeqStack *s;/*=我的操作=*/SeqStack * createemptystacks() /* 創(chuàng)建一個(gè)空棧 */ (SeqStack *s;s=(SeqStack *)malloc( sizeof (SeqStack);s-top =0;return s;6 / 20word)int stackemptys(SeqStack *s)/* 判?？?/(return s -top =0;)int

9、 stackfulls(SeqStack *s)/* 判棧滿*/(return s -top =MAX;)void pushs(SeqStack *s,DataType x) /* 進(jìn)棧*/(if (stackfulls(s)PR(over flown);elses-datas -top + =x;)void pops(SeqStack *s)/* 退棧*/(if (stackemptys(s)PR(underflown);else7 / 20words-top-;)DataType gettops(SeqStack *s) /* 棧非空時(shí)取棧頂元素 */(return s -datas -t

10、op-1;)/*=立二叉樹(shù)=*/BTNode *createbintree()/*輸入擴(kuò)大的先序序列，建立二叉樹(shù) */(BTNode *t;char x;scanf( %c, &x);if (x=#)t =NULL; /*讀入#,返回空指針*/else(t =(BTNode *)malloc( sizeof (BTNode); /* 生成結(jié)點(diǎn) */t - data =x;t- Ichild =createbintree();/* 構(gòu)造左子樹(shù) */t- rchild =createbintree();/* 構(gòu)造右子樹(shù) */8 / 20wordreturn (t);)/*=輯的遍歷 =*/void

11、 preorder(BTNode *t) /*NLR 先序遍歷*/(if (t !=NULL)(PR( %ct ,t -data); /* 訪問(wèn)結(jié)點(diǎn) */preorder(t -lchild);/* 中序遍歷左子樹(shù) */preorder(t -rchild); /* 中序遍歷右子樹(shù) */)/*=*/void inorder(BTNode *t) /*LNR 中序遍歷*/(if (t !=NULL)(inorder(t - lchild); /* 中序遍歷左子樹(shù) */PR( %ct ,t -data); /* 訪問(wèn)結(jié)點(diǎn) */inorder(t -rchild); /* 中序遍歷右子樹(shù) */)9

12、/ 20word)/*= */void postorder(BTNode *t) /*LRN 后序遍歷 */(if (t !=NULL)(postorder(t-lchild);/* 后序遍歷左子樹(shù) */postorder(t-rchild);/* 后序遍歷右子樹(shù) */PR( %ct ,t -data); /* 訪問(wèn)結(jié)點(diǎn) */)/*=全函數(shù) =-=*/void main()(BTNode *t;int n =0;PR(- 請(qǐng)輸入二叉樹(shù)各元素:(例如abd#e#cf#g#)n ); /例如 abd#e#cf#g#t =createbintree();PR(nn - 1.按先序遍歷輸出為：n);p

13、reorder(t);/*NLRpreorder(t);/*NLR先序遍歷*/10 / 20wordPR( n按中序遍歷輸出為：n);inorder(t); /*LNR 中序遍歷 */PR( n按后序遍歷輸出為：n);postorder(t); /*LRN 后序遍歷 */)includeincludeincludedefine TRUE 1includeincludeincludedefine TRUE 1define FALSE 0define Stack_Size 50define NUM 20typedef struct binarytree /*char data;struct bin

14、arytree *LChild,*RChild;BiTNode,*BiTree;typedef struct/*BiTree dataStack_Size;int top;SeqStack;void CreateBiTree(BiTree &bt) /*定義一棵二叉樹(shù)*/定義順序棧S*/利用“擴(kuò)展先序遍歷創(chuàng)建二叉鏈表*/11 / 20word(char ch;ch=getchar(); /* 調(diào)用getchar函數(shù)，需要用戶輸入字符，用戶按回車鍵完畢輸入*/if(ch=.) bt=NULL;else(bt=(BiTNode *)malloczeof(BiTNode);bt-data=ch;Cr

15、eateBiTree(bt-LChild);CreateBiTree(bt-RChild);void InitStack(SeqStack &S) /* 初始化順序棧 S*/(S.top=-1;int IsEmpty(SeqStack S) /* 判?？?*/(return(S.top=-1? TRUE:FALSE);int Push(SeqStack &S,BiTree &x) /*進(jìn)棧*/(if(S.top=Stack_Size-1)return(FALSE);12 / 20wordS.top+;S.dataS.top=x;return(TRUE);)int Pop(SeqStack &S

16、,BiTree &x) /* 出棧*/(if(S.top=-1)return(FALSE);else(x=S.dataS.top;S.top-;return(TRUE);)void PreOrder(BiTree root) /* 先序遍歷非遞歸 */(BiTNode *p;SeqStack S;p=root;InitStack(S);while(p!=NULL|!IsEmpty(S)(while(p!=NULL)13 / 20wordprintf(%4c,p-data);Push(S,p);p=p-LChild;)if(IsEmpty(S)return;Pop(S,p);p=p-RChild

17、;)中序遍歷非遞歸*/中序遍歷非遞歸*/BiTNode *p;SeqStack S;InitStack(S);p=root;while(p!=NULL | ! IsEmpty(S)if(p!=NULL)Push(S,p);p=p-LChild;)else14 / 20wordPop(S,p);printf(%4c,p-data);p=p-RChild;)void PostOrder(BiTree root) /*后序遍歷非遞歸 */BiTNode *p,*q;BiTNode *S;int top=0;q=NULL;p=root;S=(BiTNode*)malloc(sizeof(BiTNode

18、*)*NUM); /*NUM為預(yù)定義的常數(shù) */while(p!=NULL | top!=0)while(p!=NULL)top+;Stop=p;p=p-LChild;)if(top0)p=Stop;if(p-RChild=NULL)|(p-RChild=q) printf(%4c,p-data);15 / 20wordq=p；top-;p=NULL;)elsep=p-RChild;)free(S);)void main() /* 主函數(shù)局部*/loop:BiTree root=NULL;CreateBiTree(root);printf(PreOrder traversal is:n);Pr

19、eOrder(root);printf(n);printf(InOrder traversal is:n);InOrder(root);printf(n);printf(PostOrder traversal is:n);PostOrder(root);printf(n);printf(Please input a new one:n);16 / 20wordchar c=getchar();goto loop;)實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有的數(shù)據(jù)類型，對(duì)每個(gè)操作給出偽碼算法或算法流程圖 對(duì)主程序和其他模塊也都需要寫(xiě)出偽碼算法或流程圖。五、調(diào)試分析主要描述調(diào)試過(guò)程中碰到的問(wèn)題與解決方法.初步完成編

20、程的工作時(shí)，在輸入二叉樹(shù)的發(fā)現(xiàn)只能輸入一個(gè)字符，而且程序不再進(jìn)展，最后是自己的不小心將語(yǔ)句 char a; scanf(%c,&a); 中的%c寫(xiě)為得致的。.在編寫(xiě)元素入棧和出棧的時(shí)候，程序報(bào)如下的錯(cuò)誤：語(yǔ)法有錯(cuò)誤。 ，經(jīng) 過(guò)檢查原來(lái)是定義的時(shí)候的類型使用錯(cuò)了。六、程序使用說(shuō)明通過(guò)運(yùn)行截圖再加以必要的文字說(shuō)明七、程序測(cè)試結(jié)果提供測(cè)試數(shù)據(jù)和運(yùn)行結(jié)果擴(kuò)展先序遍.IjVawwtemp.ewe-AB, DF., G. , C. E_ H.先序遍歷：A B D F G C E HPress any key to continue17 / 20word遞歸算法： i Fi ttC j Ya n brnww

21、t e m p.exe一請(qǐng)輸入二叉樹(shù)各元素：（例如油dtttteltttcftwg曲） abd=Pe=cf=g?=- L按先序遍歷輸出為:a b d c f 宮按中多遍歷輸出為：dbeafcg按后序遍歷輸出為：debfgca非遞歸算法:c C:ITlW0f5Xsystoe6LG Sa h5faGrBaDrB5ArDeGrBtF1、函數(shù)的參數(shù)傳遞有哪幾種？ref和out的區(qū)別?值傳遞、引用傳遞、輸出傳遞、參數(shù)數(shù)組18 / 20wordref和out的區(qū)別：out 關(guān)鍵字會(huì)導(dǎo)致參數(shù)通過(guò)引用來(lái)傳遞，這與 ref關(guān)鍵字類似。不同之處在于：1ref傳進(jìn)去的參數(shù)必須在調(diào)用前初始化，而 out不必，因?yàn)閛u

22、t的函數(shù)會(huì)先清空變量，即使變量 已經(jīng)賦值。2ref傳進(jìn)去的參數(shù)在函數(shù)內(nèi)部可以直接使用，而 out不可。3ref傳進(jìn)去的參數(shù)在函數(shù)內(nèi)部可以不被修改，但 out必須在離開(kāi)函數(shù)體前進(jìn)展賦值。4ref:當(dāng)需要通過(guò)調(diào)用某函數(shù)來(lái)改變實(shí)參變量的值時(shí)，使用 ref。out:主要是為了 一個(gè)方法能返回兩個(gè)以上的結(jié)果。2、虛函數(shù)和抽象函數(shù)的區(qū)別？答：虛函數(shù)是有代碼的并明確允許子類去覆蓋，但子類也可不覆蓋，就是說(shuō)可以直接用，不用重寫(xiě)；抽象函數(shù)沒(méi)有實(shí)現(xiàn)代碼，即沒(méi)有函數(shù)體，而是由 abstract修飾符聲明。抽象函數(shù)只提供函數(shù)名稱，具 體實(shí)現(xiàn)交由繼承的派生類，子類繼承后必須要重寫(xiě)。3、抽象類和接口的區(qū)別？一樣點(diǎn)：都不能被直接實(shí)例化，都可以通過(guò)繼承實(shí)現(xiàn)其抽象方法。都是面向抽象編程的技術(shù)根底，實(shí)現(xiàn)了諸多的設(shè)計(jì)模式。不同點(diǎn)：接口支持多繼承；抽象類不能實(shí)現(xiàn)多繼承。接口只能定義抽象規(guī)如此；抽象類既可以定義規(guī)如此，還可