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

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

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

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

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

5、是對結點操作的應用函數(shù)。操作結果：中序遍歷S,對每個結點調(diào)用函數(shù)visit 一次且僅一次。一旦visit失敗，如此操作失敗。3 / 20wordPostordertraverse (&S,e)初始條件：二叉樹S已經(jīng)存在，Visit是對結點操作的應用函數(shù)。操作結果：后序遍歷S,對每個結點調(diào)用函數(shù)visit 一次且僅一次 一旦visit失敗，如此操作失敗。ADT Binarytree五、詳細設計擴展先序遍歷: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/*卷立各結構體*/*卷立各結構體*/typedefstruct node (char data; /* 數(shù)據(jù)域 */struct node *lchild;struct node *rchild; /*結點的左右指針，分別指

8、向結點的左右孩子*/ BTNode;typedef BTNode * DataType;typedefstruct (DataType dataMAX;int top; SeqStack;SeqStack *s;/*=我的操作=*/SeqStack * createemptystacks() /* 創(chuàng)建一個空棧 */ (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) /* 進棧*/(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) /* 棧非空時取棧頂元素 */(return s -datas -t

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

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

12、/ 20word)/*= */void postorder(BTNode *t) /*LRN 后序遍歷 */(if (t !=NULL)(postorder(t-lchild);/* 后序遍歷左子樹 */postorder(t-rchild);/* 后序遍歷右子樹 */PR( %ct ,t -data); /* 訪問結點 */)/*=全函數(shù) =-=*/void main()(BTNode *t;int n =0;PR(- 請輸入二叉樹各元素:(例如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) /*定義一棵二叉樹*/定義順序棧S*/利用“擴展先序遍歷創(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) /*進棧*/(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為預定義的常數(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;)實現(xiàn)概要設計中定義的所有的數(shù)據(jù)類型，對每個操作給出偽碼算法或算法流程圖 對主程序和其他模塊也都需要寫出偽碼算法或流程圖。五、調(diào)試分析主要描述調(diào)試過程中碰到的問題與解決方法.初步完成編

20、程的工作時，在輸入二叉樹的發(fā)現(xiàn)只能輸入一個字符，而且程序不再進展，最后是自己的不小心將語句 char a; scanf(%c,&a); 中的%c寫為得致的。.在編寫元素入棧和出棧的時候，程序報如下的錯誤：語法有錯誤。 ，經(jīng) 過檢查原來是定義的時候的類型使用錯了。六、程序使用說明通過運行截圖再加以必要的文字說明七、程序測試結果提供測試數(shù)據(jù)和運行結果擴展先序遍.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一請輸入二叉樹各元素：（例如油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 關鍵字會導致參數(shù)通過引用來傳遞，這與 ref關鍵字類似。不同之處在于：1ref傳進去的參數(shù)必須在調(diào)用前初始化，而 out不必，因為ou

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