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

1、數(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ō)明：以下題目中（一）為全體必做，（二）（三）任選其一完成（一） 從鍵盤輸入二叉樹(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ò)展:允許目錄名是多字符組合)A B E F C G D三. 分工

2、說(shuō)明一起編寫、探討流程圖，根據(jù)流程圖分工編寫算法，共同討論修改，最后上機(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ū)；（2） 若Droot不為空，則存在DrootD1，Dr，且D1Dr為空集；（3） 若D1不為空，則D1中存在唯一的元素x1，<root，x1>H，且存在D1上的關(guān)系H1是H的子集；若Dr不為空集，則Dr

3、中存在唯一的元素Xr，<root，Xr>H，且存在Dr上的關(guān)系Hr為H的子集；H=<root，x1>,<root，Xr>,H1,Hr; (4) (D1,H1)是一顆符合本定義的二叉樹(shù)，稱為根的左子樹(shù)，(Dr,Hr)是一顆符合本定義的二叉樹(shù)，稱為根的右子樹(shù)。基本操作:Creatbitree(&S，definition)初始條件：definition給出二叉樹(shù)S的定義操作結(jié)果：按definition構(gòu)造二叉樹(shù)S counter(T) 初始條件：二叉樹(shù)T已經(jīng)存在 操作結(jié)果：返回二叉樹(shù)的總的結(jié)點(diǎn)數(shù) onecount(T)初始條件：二叉樹(shù)T已經(jīng)存在操作結(jié)果：返

4、回二叉樹(shù)單分支的節(jié)點(diǎn)數(shù)Clearbintree(S)初始條件：二叉樹(shù)S已經(jīng)存在操作結(jié)果：將二叉樹(shù)S清為空樹(shù)Bitreeempty(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一次且僅一次。一旦

5、visit失敗，則操作失敗。Inordertraverse (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失敗，則操作失敗。Postordertraverse (&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<stdio.h># include<stdlib.h

6、>#include<string.h>typedef struct binarytreechar data;struct binarytree *lchild,*rchild;BiTreeNode,*BiTree;void CreateBiTree(BiTree *bt)char ch;ch=getchar();if(ch='.') *bt=NULL; else *bt=(BiTreeNode *)malloc(sizeof(BiTreeNode); (*bt)->data=ch;CreateBiTree(&(*bt)->lchild);C

7、reateBiTree(&(*bt)->rchild); void PreOder(BiTree root)if(root!=NULL)printf("%4c",root->data);PreOder(root->lchild);PreOder(root->rchild);main()BiTree root;CreateBiTree(&root);printf("先序遍歷:n");PreOder(root);遞歸算法：#include "stdio.h"#define PR printf#def

8、ine ERROR 0#define MAX 100 /*=建立各結(jié)構(gòu)體=*/typedef struct node char data; /*數(shù)據(jù)域*/ struct node *lchild; struct node *rchild; /*結(jié)點(diǎn)的左右指針，分別指向結(jié)點(diǎn)的左右孩子*/BTNode;typedef BTNode *DataType;typedef struct DataType dataMAX;int top;SeqStack;SeqStack *s; /*=棧的操作=*/SeqStack *createemptystacks() /*創(chuàng)建一個(gè)空棧*/SeqStack *s;s

9、=(SeqStack*)malloc(sizeof(SeqStack);s->top=0;return s;int stackemptys(SeqStack *s) /*判棧空*/return s->top=0;int 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

10、) /*退棧*/if(stackemptys(s)PR("underflown");elses->top-;DataType gettops(SeqStack *s) /*棧非空時(shí)取棧頂元素*/return s->datas->top-1;/*=建立二叉樹(shù)=*/BTNode *createbintree() /*輸入擴(kuò)充的先序序列，建立二叉樹(shù)*/ BTNode *t; char x; scanf("%c",&x); if(x='#') t=NULL; /*讀入#，返回空指針 */ else t=(BTNode *

11、)malloc(sizeof(BTNode); /*生成結(jié)點(diǎn)*/ t->data=x; t->lchild=createbintree(); /*構(gòu)造左子樹(shù)*/ t->rchild=createbintree(); /*構(gòu)造右子樹(shù)*/ return(t); /*=樹(shù)的遍歷=*/void preorder(BTNode *t) /*NLR 先序遍歷*/ if(t!=NULL) PR(" %ct",t->data); /*訪問(wèn)結(jié)點(diǎn)*/ preorder(t->lchild); /*中序遍歷左子樹(shù)*/ preorder(t->rchild);

12、/*中序遍歷右子樹(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ù)*/ /*=*/void postorder(BTNode *t) /*LRN 后序遍歷*/ if(t!=NULL) postorder(t->lchild); /*后序遍歷左子樹(shù)*/ postorder(t->rchild); /*后序

13、遍歷右子樹(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"); preorder(t); /*NLR 先序遍歷*/ PR("n 按中序遍歷輸出為：n"); inorder(t); /*LNR 中序遍

14、歷*/ PR("n 按后序遍歷輸出為：n"); postorder(t); /*LRN 后序遍歷*/ # include<stdio.h># include<stdlib.h># include<string.h># define TRUE 1# define FALSE 0# define Stack_Size 50# define NUM 20typedef struct binarytree /*定義一棵二叉樹(shù)*/char data;struct binarytree *LChild,*RChild;BiTNode,*BiTree;

15、typedef struct /*定義順序棧S*/ BiTree dataStack_Size; int top;SeqStack;void CreateBiTree(BiTree &bt) /*利用“擴(kuò)展先序遍歷”創(chuàng)建二叉鏈表*/ char ch; ch=getchar(); /*調(diào)用getchar函數(shù)，需要用戶輸入字符，用戶按回車鍵結(jié)束輸入*/ if(ch='.') bt=NULL; else bt=(BiTNode *)malloc(sizeof(BiTNode); bt->data=ch; CreateBiTree(bt->LChild); Crea

16、teBiTree(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); S.top+; S.dataS.top=x; return(TRUE);int Pop(SeqStack &S,BiTree &x) /*出棧

17、*/ 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) printf("%4c",p->data);Push(S,p);p=p->LChild; if(IsEmpty(S) return; Pop(S,p); p=p->

18、RChild; void InOrder(BiTree root) /*中序遍歷非遞歸*/BiTNode *p;SeqStack S;InitStack(S);p=root;while(p!=NULL | ! IsEmpty(S)if(p!=NULL)Push(S,p);p=p->LChild;elsePop(S,p); printf("%4c",p->data);p=p->RChild;void PostOrder(BiTree root) /*后序遍歷非遞歸*/BiTNode *p,*q;BiTNode *S;int top=0;q=NULL;p=ro

19、ot;S=(BiTNode*)malloc(sizeof(BiTNode*)*NUM); /*NUM為預(yù)定義的常數(shù)*/while(p!=NULL | top!=0)while(p!=NULL)top+;Stop=p;p=p->LChild;if(top>0)p=Stop;if(p->RChild=NULL)|(p->RChild=q)printf("%4c",p->data);q=p;top-;p=NULL;elsep=p->RChild;free(S);void main() /*主函數(shù)部分*/loop:BiTree root=NULL

20、;CreateBiTree(root); printf("PreOrder traversal is:n");PreOrder(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:

21、n");char c=getchar();goto loop;實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有的數(shù)據(jù)類型，對(duì)每個(gè)操作給出偽碼算法或算法流程圖。對(duì)主程序和其他模塊也都需要寫出偽碼算法或流程圖。五、調(diào)試分析（主要描述調(diào)試過(guò)程中碰到的問(wèn)題及解決方法）初步完成編程的工作時(shí)，在輸入二叉樹(shù)的發(fā)現(xiàn)只能輸入一個(gè)字符，而且程序不再進(jìn)行，最后是自己的不小心將語(yǔ)句char a; scanf("%c",&a);中的%c寫為%d導(dǎo)致的。 在編寫元素入棧和出棧的時(shí)候，程序報(bào)如下的錯(cuò)誤：語(yǔ)法有錯(cuò)誤。，經(jīng)過(guò)檢查原來(lái)是定義的時(shí)候的類型使用錯(cuò)了。六、程序使用說(shuō)明（通過(guò)運(yùn)行截圖再加以必要的文字說(shuō)明）七

22、、程序測(cè)試結(jié)果（提供測(cè)試數(shù)據(jù)和運(yùn)行結(jié)果）擴(kuò)展先序遍歷遞歸算法：非遞歸算法：1、函數(shù)的參數(shù)傳遞有哪幾種？ref和out的區(qū)別？值傳遞、引用傳遞、輸出傳遞、參數(shù)數(shù)組ref和out的區(qū)別： out 關(guān)鍵字會(huì)導(dǎo)致參數(shù)通過(guò)引用來(lái)傳遞，這與 ref 關(guān)鍵字類似。 不同之處在于： （1）ref傳進(jìn)去的參數(shù)必須在調(diào)用前初始化，而out不必，因?yàn)閛ut的函數(shù)會(huì)先清空變量，即使變量已經(jīng)賦值。 （2）ref傳進(jìn)去的參數(shù)在函數(shù)內(nèi)部可以直接使用，而out不可。 （3）ref傳進(jìn)去的參數(shù)在函數(shù)內(nèi)部可以不被修改，但out必須在離開(kāi)函數(shù)體前進(jìn)行賦值。 （4）ref:當(dāng)需要通過(guò)調(diào)用某函數(shù)來(lái)改變實(shí)參變量的值時(shí)，使用ref。 out:主要是為了一個(gè)方法能返回兩個(gè)以上的結(jié)果。2、虛函數(shù)和抽象函數(shù)的區(qū)別？答：虛函數(shù)是有代碼的并明確允許子類去覆蓋，但子類也可不覆蓋，就是說(shuō)可以直接用，不用重寫；抽象函數(shù)沒(méi)有實(shí)現(xiàn)代碼，即沒(méi)有函數(shù)體，而是由abstract修飾符聲明。抽象函數(shù)只提供函數(shù)名稱，具體實(shí)現(xiàn)交由繼承的派生類，子類繼承后必須要重寫。3、抽象類和接口的區(qū)別？相同點(diǎn)：都不能被直接實(shí)例化，都可以通過(guò)繼承實(shí)現(xiàn)其抽象方法。都是面向抽象編程的技術(shù)基礎(chǔ)，實(shí)現(xiàn)了諸多的設(shè)計(jì)模式。不同點(diǎn)：接口支持多繼承；抽象類不能實(shí)現(xiàn)多繼承。接口只能定義抽象規(guī)則；抽象類既可以