二叉樹的遍歷算法

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

2、#include "conio.h"#define maxsize 100typedef int datatype;typedef struct bnodedatatype data;struct bnode *lchild,*rchild;bnode,*btree;typedef struct bnode *node;int flag;DataType;typedef structDataType datamaxsize;int top;SeqStack,*PSeqStack;typedef struct btree datamaxsize;int front,rear;

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

4、qStack1 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)printf("%c",t->data);P

5、reOrder1(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)printf("%c",p->data);push1(s,p);p=p->lchild;elsepop1(s,&p);p=p->rchild;/中序遍歷的遞歸算法void InOrder1

6、(btree t)if(t)InOrder1(t->lchild);printf("%c",t->data);InOrder1(t->rchild);/中序遍歷的非遞歸算法void InOrder2(btree t)PSeqStack1 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);printf("%c",p-&g

7、t;data);p=p->rchild;/后序遍歷的遞歸算法void PostOrder1(btree t)if(t)/t=(btree)malloc(sizeof(bnode);PostOrder1(t->lchild);PostOrder1(t->rchild);printf("%c",t->data);/后序遍歷的非遞歸算法/入棧操作void push(PSeqStack s,DataType sq)if(s->top=maxsize-1)printf("棧滿不得入棧");elses->top+;s->da

8、tas->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(p)/s=(PSeqStack)mall

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

10、=0;return q;/判斷隊空int empty(PSeqQueue q)if(q&&q->front=q->rear)return 1;else return 0;/入隊void input(PSeqQueue q,btree x)if(q->rear+1)%maxsize=q->front)printf("隊滿");elseq->rear=(q->rear+1)%maxsize;q->dataq->rear=x;/出隊void output(PSeqQueue q,btree *x)if(empty(q

11、)printf("隊空");elseq->front=(q->front+1)%maxsize;*x=q->dataq->front;/按照層次遍歷二叉樹void LevelOrder1(btree t)PSeqQueue q;btree p=t;q=init();input(q,p);while(!empty(q)output(q,&p);printf("%c",p->data);if(p->lchild)input(q,p->lchild);if(p->rchild)input(q,p->

12、rchild);void main()btree t;t=create();printf("此二叉樹的先序遞歸遍歷輸出為：");PreOrder1(t);printf("n");printf("此二叉樹的先序非遞歸遍歷輸出為：");PreOrder2(t);printf("n");printf("此二叉樹的中序遞歸遍歷輸出為：");InOrder1(t);printf("n");printf("此二叉樹的中序遞歸遍歷輸出為：");InOrder2(t);printf("n");printf("此二叉樹的后序遞歸遍歷輸出為：");PostOrder1(t);printf("n");printf("此二叉樹的后序遞歸遍歷輸出為：&