二叉樹的遍歷算法

1、實驗三二叉樹遍歷算法一、實驗?zāi)康? 進(jìn)一步理解掌握二叉樹二叉鏈表存儲結(jié)構(gòu)。2.掌握二叉樹遍歷的遞歸與非遞歸算法。二、實驗要求1. 認(rèn)真閱讀和掌握（先序、中序、后序和層次）遍歷的遞歸與非遞歸 算法2. 上機(jī)調(diào)試（先序、中序、后序和層次）遍歷的遞歸與非遞歸 算法。3. 保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。4. 上機(jī)后，認(rèn)真整理源程序及其注釋，完成實驗報告（包括源程序、實驗 結(jié)果、算法分析、心得體會等）。三、實驗容先序、中序、后序遍歷的遞歸與非遞歸算法和層次遍歷的算法實現(xiàn)程序：#i nclude "stdio.h"#in elude "stdlib.h&qu

2、ot;#i nclude "con io.h"#defi ne maxsize 100typedef int datatype;typedef struct bno dedatatype data;struct bnode *lchild,*rchild;bno de,*btree;typedef struct bnode *node;int flag;DataType;typedef structDataType datamaxsize;int top;SeqStack,*PSeqStack;typedef struct btree datamaxsize;int fro

3、n t,rear;SeqQueue,*PSeqQueue;typedef structbtree datamaxsize;int top;SeqStack1,*PSeqStack1;/建立一個二叉樹btree create()btree t;char ch; scan f("%c",&ch);if(ch=?)t=NULL;elset=(btree)malloc(sizeof(b no de); t->data=ch;t->lchild=create(); t->rchild=create(); return t;/先序遍歷/入棧操作void pus

4、h1(PSeqStack1 s,btree sq)if(s->top=maxsize-1)printf("棧滿不得入棧");elses_>top+; s_>datas_>top=sq;/出棧操作void pop1(PSeqStack1 s,btree *sq)if(s->top=-1)printf("棧空不得出棧");else*sq=s->datas->top; s->top-;/先序遍歷的遞歸算法void PreOrder1(btree t)if(t)prin tf("%c",t-&g

5、t;data);PreOrder1(t->lchild); PreOrder1(t->rchild);/先序遍歷的非遞歸算法void PreOrder2(btree t)PSeqStack1 s; s=(PSeqStack1)malloc(sizeof(SeqStack1); btree p=t;s->top=-1;while(p|s->top!=-1)if(p)prin tf("%c",p->data);push1(s,p);p=p->lchild;elsepop1(s,&p); p=p->rchild;/中序遍歷的遞歸算

6、法void In Order1(btree t)if(t)In Order1(t->lchild);prin tf("%c",t->data);In Order1(t->rchild);/中序遍歷的非遞歸算法void In Order2(btree t)PSeqStackl s; s=(PSeqStack1)malloc(sizeof(SeqStack1); btree p=t;s->top=-1;while(p|s->top!=-1)if(p)push1(s,p); p=p->lchild;elsepop1(s,&p);prin

7、 tf("%c",p->data);p=p->rchild;/后序遍歷的遞歸算法void PostOrder1(btree t)if(t)t=(btree)malloc(sizeof(b no de);PostOrder1(t->lchild);PostOrder1(t->rchild); prin tf("%c",t->data);/后序遍歷的非遞歸算法/入棧操作void push(PSeqStack s,DataType sq)if(s->top=maxsize-1)printf(”棧滿不得入棧”)；elses_&

8、gt;top+; s_>datas_>top=sq;/出棧操作void pop(PSeqStack s,DataType *sq)if(s->top=-1) printf(" ?？詹坏贸鰲?quot;);else*sq=s->datas->top; s->top-;/后序遍歷的非遞歸算法void PostOrder2(btree t)PSeqStack s;DataType sq;btree p=t;s=(PSeqStack)malloc(sizeof(SeqStack);s->top=-1;while(p|s->top!=-1)if(

9、p) s=(PSeqStack)malloc(sizeof(SeqStack); sq.flag=O;sq .no de=p;push(s,sq);p=p->lchild;elsepop(s，& sq);p=sq .no de;if(sq.flag=0)sq.flag=1;push(s,sq);p=p->rchild; elseprin tf("%c",p->data); p=NULL;/按照層次遍歷二叉樹/隊列的初始化PSeqQueue init()PSeqQueue q; q=(PSeqQueue)malloc(sizeof(SeqQueue)

10、; if(q)q->fro nt=O; q->rear=0;return q;/判斷隊空int empty(PSeqQueue q)if(q&&q_>fron t=q->rear)return 1;else return 0;/入隊void in put(PSeqQueue q,btree x)if(q->rear+1)%maxsize=q->front)prin tf("隊滿”)；elseq_>rear=(q_>rear+1)%maxsize; q_>dataq_>rear=x;/出隊void output

11、(PSeqQueue q,btree *x)if(empty(q)prin tf("隊空");elseq->fron t=(q- >fron t+1)%maxsize; *x=q->dataq->fr on t;/按照層次遍歷二叉樹void LevelOrder1(btree t)PSeqQueue q;btree p=t;q=in it();in put(q,p);while(!empty(q)output(q,&p);prin tf("%c",p->data);if(p->lchild)in put(q,p

12、->lchild);if(p->rchild)in put(q,p->rchild);void mai n()btree t;t=create();printf(”此二叉樹的先序遞歸遍歷輸出為：”)；PreOrder1(t);prin tf("n");printf(”此二叉樹的先序非遞歸遍歷輸出為：");PreOrder2(t);prin tf("n");printf("此二叉樹的中序遞歸遍歷輸出為：");InO rder1(t);prin tf("n");printf("此二

13、叉樹的中序遞歸遍歷輸出為：");InO rder2(t);prin tf("n");printf(”此二叉樹的后序遞歸遍歷輸出為：”)；PostOrder1(t);prin tf("n");printf(”此二叉樹的后序遞歸遍歷輸出為：”);PostOrder2(t);prin tf("n");printf("此二叉樹的層次遍歷輸出為：");LevelOrderl(t);prin tf("n");程序結(jié)果： st如DegklDpXDebugWhujLMn 70420-OX征二叉初爲(wèi)羌序遞歸遍歷輸出為ABCDE 此二叉樹的先序菲遞歸遍歷輸出為:ABCDE 此二叉