遍歷二叉樹遞歸非遞歸試驗(yàn)報(bào)告

1、實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱二叉樹的遍歷日期2013/05/30學(xué)生學(xué)號(hào)B11050226姓名枯天蝎班級(jí)B110502實(shí)驗(yàn)?zāi)康模赫莆斩鏄涞慕Y(jié)構(gòu)特征，掌握用指針類型描述、遍歷二叉樹的運(yùn)算。實(shí)驗(yàn)條件：電腦一臺(tái)VC+6.0實(shí)驗(yàn)內(nèi)容與算法思想：內(nèi)容：P213實(shí)習(xí)題 1建立一棵用二叉鏈表方式存儲(chǔ)的二叉樹，并對(duì)其進(jìn)行遍歷（先序、中序、 和后序），打印輸出遍歷結(jié)果?；疽笕缦拢簭逆I盤接受輸入線序序列，以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹（以先序來建立）并對(duì)其進(jìn)行遍歷（先序、中序、后序），然后將遍歷結(jié)果打印輸出。要求采用遞歸和非遞歸兩種方法實(shí)現(xiàn)。算法思想：定義二叉樹結(jié)構(gòu)體類型時(shí)，也定義了一個(gè)順序棧結(jié)構(gòu)體

2、類型，用以輔助完 成二叉樹的非遞歸遍歷。由鍵盤輸入二叉樹先序序列，用擴(kuò)展線序序列函數(shù)接受并創(chuàng)建二叉鏈表。遍歷前先判斷二叉樹是否為空，若為空，執(zhí)行空操作；否則依次執(zhí)行各遍 歷函數(shù)相應(yīng)操作。先序遍歷算法思想，先訪問根節(jié)點(diǎn)，然后按先序遍歷左子樹，再按先序遍 歷右子樹。中序遍歷算法思想，先按中序遍歷左子樹，再訪問根節(jié)點(diǎn)，然后按中序訪 問右子樹。后序遍歷算法思想，先按后序遍歷左子樹，接著按中序遍歷右子樹，然后 訪問根節(jié)點(diǎn)。運(yùn)行結(jié)果：遞歸算法：非遞歸算法:ftBCDEG先序遞歸遍歷序列，n H f n E ip B中序遞歸遍歷序列=u n 首口 口后序遞歸遍歷序列B C D E G r Asi key t

3、o continue先序序列創(chuàng)建二叉樹ftBCDEGF先序遍歷序列：ABCDEGF中序追歷序列:CBEGDFA后序遍歷序列：Press amy key to Gontinue實(shí)驗(yàn)總結(jié)（結(jié)論或問題分析）：通過實(shí)驗(yàn)，加深了對(duì) C語(yǔ)言尤其是函數(shù)調(diào)用部分的認(rèn)識(shí)和掌握。沒有找到在實(shí)驗(yàn)運(yùn)行結(jié)果上明確區(qū)分遞歸算法實(shí)現(xiàn)的遍歷和非遞歸算法實(shí) 現(xiàn)的遍歷的方法。實(shí)驗(yàn)成績(jī)?nèi)握n教師簽名張紅霞附：源程序：遞歸算法程序#in elude <stdio.h>#in elude <stdlib.h>#i nclude <malloe.h>#defi ne maxsize 100#define

4、 FALSE 0#define TRUE 1typedef struct nodechar data;struct node *lchild;struct node *rchild;/二叉樹結(jié)構(gòu)體類型定義bit no de,*bitree;/* 擴(kuò)展先序序列創(chuàng)建二叉鏈表 */void cteatebitree(bitree *bt)char ch;ch=getchar();if(ch='.')*bt=NULL;else*bt=(bitree)malloc(sizeof(bitnode);(*bt)->data=ch;cteatebitree(&(*bt)->

5、lchild); cteatebitree(&(*bt)->rchild);/* 先序遞歸遍歷 */void preorder(bitree root)if(root!=NULL)printf("%c ",root->data);preorder(root->lchild);preorder(root->rchild);/* 中序遞歸遍歷 */void inorder(bitree root)if(root!=NULL)preorder(root->lchild); printf("%c ",root->dat

6、a); preorder(root->rchild);/* 后序遞歸遍歷 */void postorder(bitree root)if(root!=NULL)preorder(root->lchild);preorder(root->rchild); printf("%c ",root->data);void main()bitree bt;cteatebitree(&bt);printf(" 先序遞歸遍歷序列： preorder(bt);printf("n");printf(" 中序遞歸遍歷序列：

7、inorder(bt);printf("n");printf(" 后序遞歸遍歷序列： postorder(bt);printf("n");n");n");n");非遞歸算法程序#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define FALSE 0#define TRUE 1#define maxsize 100typedef struct nodechar data;struct node *lchild;s

8、truct node *rchild;bitnode,*bitree;typedef structbitree elemmaxsize;int top;seqstack;int push(seqstack *s,bitree x)if(s->top=maxsize-1)return(FALSE);s->top+;s->elems->top=x;/ 二叉樹結(jié)構(gòu)體定義/ 順序棧結(jié)構(gòu)體定義/ 入棧return(TRUE);bitree pop(seqstack *s,bitree x)if(s->top=-1) return NULL;else x=s->elem

9、s->top;s->top-;return x;int gettop(seqstack *s,bitree *x)if(s->top=-1)return FALSE;else*x=s->elems->top;return TRUE;void createbitree(bitree *bt)char ch;ch=getchar();if(ch='.')*bt=NULL;else/ 出棧/ 讀取棧頂元素/ 擴(kuò)展先序序列創(chuàng)建二叉鏈表*bt=(bitree)malloc(sizeof(bitnode);(*bt)->data=ch;createbit

10、ree(&(*bt)->lchild);createbitree(&(*bt)->rchild);/ 先序遍歷/ 中序遍歷void preorder1(bitree root,seqstack s) bitnode *p;p=root;while(p!=NULL|!(s.top=-1)while(p!=NULL)printf("%c",p->data);push(&s,p);p=p->lchild;if(!(s.top=-1)p=pop(&s,p);p=p->rchild;void inorder1(bitree

11、 root,seqstack s)bitnode *p;s.top=-1;p=root;while(p!=NULL|!(s.top=-1) if(p!=NULL)push(&s,p);p=p->lchild; elsep=pop(&s,p);printf("%c",p->data);p=p->rchild;void postorder1(bitree root) / 后序遍歷bitnode *p,*q;seqstack s;q=NULL;p=root;s.top=-1;/printf("%c",p->data);w

12、hile(p!=NULL|!(s.top=-1)while(p!=NULL)push(&s,p); p=p->lchild;if(!(s.top=-1)gettop(&s,&p);if(p->rchild=NULL)|(p->rchild=q)printf("%c",p->data);q=p;p=pop(&s,p);p=NULL;else p=p->rchild;void main()printf(" 先序序列創(chuàng)建二叉樹 n");seqstack s;s.top=-1;bitree root;createbitree(&root);printf(" 先序遍歷序列