资源描述：
《二叉树的遍历算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实验三二叉树遍历算法一、实验目的1．进一步理解掌握二叉树二叉链表存储结构。2．掌握二叉树遍历的递归与非递归算法。二、实验要求1．认真阅读和掌握（先序、中序、后序和层次）遍历的递归与非递归算法。2．上机调试（先序、中序、后序和层次）遍历的递归与非递归算法。3．保存和打印出程序的运行结果，并结合程序进行分析。4．上机后，认真整理源程序及其注释，完成实验报告（包括源程序、实验结果、算法分析、心得体会等）。三、实验内容先序、中序、后序遍历的递归与非递归算法和层次遍历的算法实现程序：#include"stdio.h"#include"stdlib.h"#include"conio.h"#d
2、efinemaxsize100typedefintdatatype;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;typedefstru
3、ct{btreedata[maxsize];inttop;}SeqStack1,*PSeqStack1;//建立一个二叉树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("栈满不
4、得入栈");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){PSeqStack1
5、s;s=(PSeqStack1)malloc(sizeof(SeqStack1));btreep=t;s->top=-1;while(p
6、
7、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(btr
8、eet){PSeqStack1s;s=(PSeqStack1)malloc(sizeof(SeqStack1));btreep=t;s->top=-1;while(p
9、
10、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->rchil
11、d);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]
