二叉樹的遍歷算法

1、實(shí)驗(yàn)三 二叉樹遍歷算法一、實(shí)驗(yàn)?zāi)康? 進(jìn)一步理解掌握二叉樹二叉鏈表存儲(chǔ)結(jié)構(gòu)。2 掌握二叉樹 遍歷的遞歸與非遞歸算法 。二、實(shí)驗(yàn)要求1 認(rèn)真閱讀和掌握（先序、中序、后序和層次） 遍歷的遞歸與非遞歸 算法2 上機(jī)調(diào)試（先序、中序、后序和層次） 遍歷的遞歸與非遞歸 算法。3 保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。4 上機(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#def

2、ine 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;SeqQueue,*PSeqQueue;typedef str

3、uctbtree datamaxsize;int top;SeqStack1,*PSeqStack1;/ 建立一個(gè)二叉樹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(PSeqStack1 s,btree sq)if(s-top=maxsize-1)printf( 棧滿不得入棧 );elses-top+;

4、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);PreOrder1(t-lchild);PreOrder1(t-rchild);/ 先序遍歷的非遞歸算法void PreOrder2(btree t)PSeqStack1 s;s=(PSeqStack1)malloc(sizeof(SeqStack1);btree

5、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(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

6、;while(p|s-top!=-1)if(p)push1(s,p);p=p-lchild;elsepop1(s,&p);printf(%c,p-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(

7、棧滿不得入棧 );elses-top+;s-datas-top=sq;/ 出棧操作void pop(PSeqStack s,DataType *sq)if(s-top=-1)printf( ?？詹坏贸鰲?);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)malloc(sizeof(Se

8、qStack);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;/ 按照層次遍歷二叉樹/ 隊(duì)列的初始化PSeqQueue init()PSeqQueue q;q=(PSeqQueue)malloc(sizeof(SeqQueue);if(q)q-front=0;q-rear=0;return q;/ 判斷隊(duì)空int empty(PSeqQueue q)if(q&q

9、-front=q-rear)return 1;else return 0;/ 入隊(duì)void input(PSeqQueue q,btree x)if(q-rear+1)%maxsize=q-front)printf( 隊(duì)滿 );elseq-rear=(q-rear+1)%maxsize;q-dataq-rear=x;/ 出隊(duì)void output(PSeqQueue q,btree *x)if(empty(q)printf( 隊(duì)空 );elseq-front=(q-front+1)%maxsize;*x=q-dataq-front;/ 按照層次遍歷二叉樹void LevelOrder1(btr

10、ee 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-rchild);void main()btree t;t=create();printf( 此二叉樹的先序遞歸遍歷輸出為： );PreOrder1(t);printf(n);printf( 此二叉樹的先序非遞歸遍歷輸出為： );PreOrder2(t);printf(n);printf( 此二叉樹的中序遞歸遍

11、歷輸出為： );InOrder1(t);printf(n);printf( 此二叉樹的中序遞歸遍歷輸出為： );InOrder2(t);prin tf(n);printf(”此二叉樹的后序遞歸遍歷輸出為：);PostOrderl(t);prin tf(n);printf(”此二叉樹的后序遞歸遍歷輸出為：);PostOrder2(t);prin tf(n);printf(此二叉樹的層次遍歷輸出為：);LevelOrderl(t);prin tf(n);程序結(jié)果:-OX肚二叉袖話羌序遽歸遍歷輸出為：ABCDE 眥二叉*4的先序菲遽歸遍歷輸出為：ABCDE 區(qū)二叉樹的中序蠅歸遇歷輸出為：B.WCE 肚二叉樹的中序遞歸