《二叉树地遍历算法》由会员分享，可在线阅读，更多相关《二叉树地遍历算法（8页珍藏版）》请在金锄头文库上搜索。
1、实验三二叉树遍历算法一、实验目的1. 进一步理解掌握二叉树二叉链表存储结构。2. 掌握二叉树遍历的递归与非递归算法。二、实验要求1. 认真阅读和掌握（先序、中序、后序和层次）遍历的递归与非递归算法。2. 上机调试（先序、中序、后序和层次）遍历的递归与非递归算法。3. 保存和打印出程序的运行结果，并结合程序进行分析。4. 上机后，认真整理源程序及其注释，完成实验报告（包括源程序、实验 结果、算法分析、心得体会等）。三、实验内容先序、中序、后序遍历的递归与非递归算法和层次遍历的算法实现程序：#include stdio.h#include stdlib.h#include conio.h#defi
2、ne 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 struc
3、tbtree datamaxsize;int top;SeqStack1,*PSeqStack1;建立一个二叉树btree create() (btree t;char ch;scanf(%c,&ch);if(ch=?)t=NULL;else(t=(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(栈满不得入栈);else(s-top+;s-d
4、atas-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 p=t;
5、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;中序遍历的递归算法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;else(pop1(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)prin
7、tf（-栈满不得入栈）;else(s-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(sizeo
8、f(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;/按照层次遍历二叉树/队列的初始化PSeqQueue init()(PSeqQueue q;q=(PSeqQueue)malloc(sizeof(SeqQueue); if(q)(q-front=0;q-rear=0;return q;判断队空int empty(PSeqQueue
9、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(队满)；else(q-rear=(q-rear+1)%maxsize; q-dataq-rear=x;/出队void output(PSeqQueue q,btree *x)(if(empty(q)printf(-队空);else(q-front=(q-front+1)%maxsize;*x=q-dataq-front;/按照层次遍历二叉树void Lev
10、elOrder1(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-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);printf(n);printf(此二叉树的后序递归遍历输出为：)；PostOrder1(t);printf(n);printf (-此二叉树的后序递归遍历输出为：);PostOrder2(t);printf(n);printf(此二叉树的层次遍历输出为：)；LevelOrderl(t);printf(n);程序结果：1 C:UsertyHDe5(ct0pPelughjju2O17O42De!(e- X此三叉新菌尧序递归遍历输出为；ABCDE 此二叉树的先序非递归遍历输出为ABCDE 此二又树的中序递归遍历输出为:BADCE 此二叉树的中序递归遍历输出为；BADCE 此二叉树的后序递归遍历输出为！ BDECA 此二叉树的后序递归遍历输H为：BDECA 此二叉树的层次遍历输出为，ABCDE Press any key to continue五：实验心得、体会：熟练地掌握递归算法的核心内容，能够较为熟练地使用递归算法的思想，了解二 叉树的各种遍历的特点，了解各种遍历算法的递归算法和非递归算法。
