二叉树的遍历算法

1、实验三二叉树遍历算法一、实验目的1 进一步理解掌握二叉树二叉链表存储结构。2.掌握二叉树遍历的递归与非递归算法。二、实验要求1. 认真阅读和掌握（先序、中序、后序和层次）遍历的递归与非递归 算法2. 上机调试（先序、中序、后序和层次）遍历的递归与非递归 算法。3. 保存和打印出程序的运行结果，并结合程序进行分析。4. 上机后，认真整理源程序及其注释，完成实验报告（包括源程序、实验 结果、算法分析、心得体会等）。三、实验容先序、中序、后序遍历的递归与非递归算法和层次遍历的算法实现程序：#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(" 栈空不得出栈");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");程序结果： st如DegklDpXDebugWhujLMn 70420-OX征二叉初爲羌序递归遍历输出为ABCDE 此二叉树的先序菲递归遍历输出为:ABCDE 此二叉