非递归算法遍历二叉树.doc

文档介绍：课内实验报告学生姓名:  及学号:     学院: 班级: 课程名称: 实验题目: 指导教师姓名及职称:      目 录一、实验目的  1二、实验内容  1三、实验要点及说明  1四、实现方法  1五、实验结果  2六、源程序清单  7一、;;。二、实验内容采用二叉链表存储结构实现二叉树建立及其前序、中序和后序遍历。三、实验要点及说明在主函数中通过对函数的调用来实现如上的功能,运用指针将所有功能连接起来,使程序的可操作性更强。四、实现方法运行环境v++,然后创建了4个子函数以及主函数。实现对二叉树进行操作的函数有:创建二叉树函数CreateBTree,将括号输入法输入的二叉树通过switch语句建立成一棵二叉树。二叉树的先序遍历函数PreOrder。按照先序遍历的序列即先访问根节点,然后遍历左子树,最后遍历右子树输出。二叉树的中序遍历函数InOrder,按照中序遍历的序列即先遍历左子树,然后访问根节点,最后遍历右子树输出。二叉树的中序遍历函数PostOrder,按照后序遍历的序列即先遍历左子树,然后遍历右子树,最后访问根节点,。主函数为main函数,通过对三个函数的调用,从而完成先序、中序、后序的遍历。五、实验结果六、源程序清单#include<>#include<>                /*包含头文件*/#include<>#defineBTreeDTchar#defineMaxSize100/*******二叉链表存储结构定义*******/typedefstructbkbnode{BTreeDTdata;structbkbnode*lchild;structbkbnode*rchild;}BTNode;/*******建立二叉树*******/voidCreateBTree(BTNode*&bt,char*str){BTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;bt=NULL;ch=str[j];while(ch!='\n'){switch(ch){case'(':top++;St[top]=p;k=1;break;case')':top--;break;case',':k=2;break;default:p=(BTNode*)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if(bt==NULL)bt=p;else{switch(k){case1:St[top]->lchild=p;break;case2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}/**********先序遍历***********/voidPreOrder(BTNode*&bt){BTNode*p=bt,*St[MaxSize];inti=0;printf("先序遍历输出:\n");while(!(p==NULL&&St[i]==NULL)){if(p!=NULL){printf("%c",p->data);St[i]=p;i++;p=p->lchild;}else{i--;p=St[i];p=p->rchild;}}}/*********中序遍历*********/voidInOrder(BTNode*bt){BTNode*p=bt,*St[MaxSize];inttop=-1;printf("中序遍历输出:\n");do{while(p){top++;St[top]=p;p=p->lchild;}p=St[top];printf("%c",p->data);top--;if(p->rchild){p=p->rchild;top++;St[top]=p;p=p->lchild;}elsep=p->rchild;}while(top!=-1);}/*****后序遍历*****/voidPostOrder(BTNode*&bt){BTNode*p1,*p2;inti=0;p1=(BTNode*)malloc(sizeof(BTNode));p2=(BTNode*)malloc(sizeof(BTNode));p1->data=1;p2->data=2;BTNode*a[MaxSize];BTNode*p=bt;unsignedsign;printf("后序遍历序列的输出:\n");do{if(p!=NULL){a[i]=p;i++;a[i]=p1;i++;p=p->lchild;}elsewhile(a[i]!=