二叉樹地遍歷算法

實(shí)驗(yàn)三二叉樹遍歷算法一、實(shí)驗(yàn)?zāi)康倪M(jìn)一步理解掌握二叉樹二叉鏈表存儲(chǔ)結(jié)構(gòu)。掌握二叉樹遍歷的遞歸與非遞歸算法。二、實(shí)驗(yàn)要求認(rèn)真閱讀和掌握（先序、中序、后序和層次）遍歷的遞歸與非遞歸算法。上機(jī)調(diào)試（先序、中序、后序和層次）遍歷的遞歸與非遞歸算法。保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。上機(jī)后，認(rèn)真整理源程序及其注釋，完成實(shí)驗(yàn)報(bào)告（包括源程序、實(shí)驗(yàn)結(jié)果、算法分析、心得體會(huì)等）。三、實(shí)驗(yàn)內(nèi)容先序、中序、后序遍歷的遞歸與非遞歸算法和層次遍歷的算法實(shí)現(xiàn)程序：#include"stdio.h"#include"stdlib.h"#include"conio.h"#definemaxsize100typedefintdatatype;typedefstructbnode{datatypedata;structbnode*lchild,*rchild;}bnode,*btree;typedefstruct{bnode*node;intflag;}DataType;typedefstruct{DataTypedata[maxsize];inttop;}SeqStack,*PSeqStack;typedefstruct{btreedata[maxsize];intfront,rear;}SeqQueue,*PSeqQueue;typedefstruct{btreedata[maxsize];inttop;}SeqStack1,*PSeqStack1;〃建立一個(gè)二叉樹btreecreate()(btreet;charch;scanf("%c",&ch);if(ch=='?')t=NULL;else(t=(btree)malloc(sizeof(bnode));t->data=ch;t->lchild=create();t->rchild=create();}returnt;}//先序遍歷//入棧操作voidpush1(PSeqStack1s,btreesq)(if(s->top==maxsize-1)printf("棧滿不得入棧");else(s->top++;s->data[s->top]=sq;}}〃出棧操作voidpop1(PSeqStack1s,btree*sq)(if(s->top==-1)printf("?？詹坏贸鰲?);else(*sq=s->data[s->top];s->top--;}}〃先序遍歷的遞歸算法voidPreOrder1(btreet)(if(t)(printf("%c",t->data);PreOrder1(t->lchild);PreOrder1(t->rchild);}}〃先序遍歷的非遞歸算法voidPreOrder2(btreet)(PSeqStack1s;s=(PSeqStack1)malloc(sizeof(SeqStack1));btreep=t;s->top=-1;while(p||s->top!=-1)(if(p)(printf("%c",p->data);push1(s,p);p=p->lchild;}else(pop1(s,&p);p=p->rchild;}}}〃中序遍歷的遞歸算法voidInOrder1(btreet)(if(t)(InOrder1(t->lchild);printf("%c",t->data);InOrder1(t->rchild);}}〃中序遍歷的非遞歸算法voidInOrder2(btreet)(PSeqStack1s;s=(PSeqStack1)malloc(sizeof(SeqStack1));btreep=t;s->top=-1;while(p||s->top!=-1)(if(p)(push1(s,p);p=p->lchild;}else(pop1(s,&p);printf("%c",p->data);p=p->rchild;}}}〃后序遍歷的遞歸算法voidPostOrder1(btreet)(if(t)(//t=(btree)malloc(sizeof(bnode));PostOrder1(t->lchild);PostOrder1(t->rchild);printf("%c",t->data);}}〃后序遍歷的非遞歸算法//入棧操作voidpush(PSeqStacks,DataTypesq)(if(s->top=二maxsize-1)printf（-棧滿不得入棧"）;else(s->top++;s->data[s->top]=sq;}}〃出棧操作voidpop(PSeqStacks,DataType*sq)(if(s->top==-1)printf(-?？詹坏贸鰲?);else(*sq=s->data[s->top];s->top--;}}〃后序遍歷的非遞歸算法voidPostOrder2(btreet)(PSeqStacks;DataTypesq;btreep=t;s=(PSeqStack)malloc(sizeof(SeqStack));s->top=-1;while(p||s->top!=-1)(if(p)(//s=(PSeqStack)malloc(sizeof(SeqStack));sq.flag=0;sq.node=p;push(s,sq);p=p->lchild;}else(pop(s,&sq);p=sq.node;if(sq.flag==0)(sq.flag=1;push(s,sq);p=p->rchild;}else(printf("%c",p->data);p=NULL;}}}}//按照層次遍歷二叉樹//隊(duì)列的初始化PSeqQueueinit()(PSeqQueueq;q=(PSeqQueue)malloc(sizeof(SeqQueue));if(q)(q->front=0;q->rear=0;}returnq;}〃判斷隊(duì)空intempty(PSeqQueueq)(if(q&&q->front=二q->rear)return1;elsereturn0;}//入隊(duì)voidinput(PSeqQueueq,btreex)(if((q->rear+1)%maxsize=二q->front)printf("隊(duì)滿")；else(q->rear=(q->rear+1)%maxsize;q->data[q->rear]=x;}}//出隊(duì)voidoutput(PSeqQueueq,btree*x)(if(empty(q))printf(-隊(duì)空");else(q->front=(q->front+1)%maxsize;*x=q->data[q->front];}}//按照層次遍歷二叉樹voidLevelOrder1(btreet)(PSeqQueueq;btreep=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->rchild);}}voidmain()(btreet;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(-此二叉樹的后序遞歸遍歷輸出為：");PostOrder2(t);printf("\n");printf("此二叉樹的層次遍歷輸出為：")；LevelOrderl(t);printf("\n");}程序結(jié)果：■1'C:\Usert\yH\De5(ct0p\Pel>ug^h<jju2O17O42De!(e'-□X此三叉新菌堯序遞歸遍歷輸出為；ABCDE此二叉樹的先序非遞歸遍歷輸出為ABCDE此二又樹的中序遞歸遍歷輸出