数据结构实验报告之二叉树遍历

湘潭大学数学与计算科学学院学生实验报告专业信息与计算科学班级一班姓名苗瑞丰学号2010750215实验日期2012年12月5日至2012年12月8日实验项目数据结构实验实验内容与要求题目：7、建立一棵二叉树，并按照中序、先序、后序及按层次方法访问。指导教师意见成绩：签名：年月日备注（程序源代码和运行结果图见附页）源程序7：#include<cstdio>#include<cstdlib>#defineMAX100//队列长度typedefcharTDataType;//可以在这将char改为你需要的基本类型，如inttypedefstructTreeNode//树节点{TDataTypedata;//数据域structTreeNode*lchild,*rchild;//左右孩子}TreeNode,*Tree;typedefTreeQDataType;//队列元素类型为树节点类型typedefstruct{QDataTypedata[MAX+1];//队列长度为101intfront,rear;//分别指向队头、尾}Queue;/*（1）初始化队列q*/voidInitQueue(Queue&q){q.front=0;q.rear=0;}/*（2）判断队列q是否非空；*/intEmptyQueue(Queue&q){if(q.rear==q.front)return1;elsereturn0;}/*（3）依次进队元素a，b，c*/voidInsqQueue(Queue&q,QDataTypex)//&q为变量引用，与调用函数处的实参共享存储空间{if(q.rear==MAX){printf("overflow");}//队满q.rear++;//未满，入队q.data[q.rear]=x;}/*(4)出队一个元素，输出该元素；*/intOutsqQueue(Queue&q,Tree&p){if(EmptyQueue(q))//队空{printf("underflow");return0;//出队失败}else{p=q.data[q.front+1];//printf("%c",x);q.front++;}if(EmptyQueue(q)){q.front=0;q.rear=0;}//队内已无元素return1;//出队成功}/*（5）输出队列的元素个数；*/intNumberQueue(Queue&q){if(EmptyQueue(q))return0;elsereturn(q.rear-q.front);}/*（8）输出出队序列；begin*/intDisplaySqQueue(Queue&q){inti;if(EmptyQueue(q))return1;for(i=1;i<=q.rear;i++){printf("%c",q.data[q.front+1]);q.front++;}printf("\n");return1;}//n（9）释放队列。voidDestroyList_SqQueue(Queue&q){if(EmptyQueue(q)==0)q.front=0;q.rear=0;}TreeCreateTree(Tree&r)//以先序遍历的方式建立二叉树{charc;scanf("%c",&c);if(c=='')r=NULL;//空格表无此节点else{r=(Tree)malloc(sizeof(TreeNode));if(!r)return(NULL);//内存分配失败r->data=c;//否则以先序遍历二叉树的方式建立二叉树r->lchild=CreateTree(r->lchild);r->rchild=CreateTree(r->rchild);}return(r);}/*先序遍历二叉树*/voidPreorder(Treer){if(r){printf("%c",r->data);Preorder(r->lchild);Preorder(r->rchild);}}/*中序遍历二叉树*/voidmidorder(Treer){if(r){midorder(r->lchild);printf("%c",r->data);midorder(r->rchild);}}//后序遍历二叉树voidpostorder(Treer){if(r){postorder(r->lchild);postorder(r->rchild);printf("%c",r->data);}}//层次遍历二叉树voidTravelTree(Treer){Queueq;InitQueue(q);Treep,p1,p2;p=r;//(Tree)malloc(sizeof(TreeNode));if(p)InsqQueue(q,p);//树非空，入队while(!EmptyQueue(q)){OutsqQueue(q,p);printf("%c",p->data);//输出队首元素,即层次遍历的当前节点p1=p->lchild;p2=p->rchild;//若有孩子节点，入队同上处理if(p1)InsqQueue(q,p1);if(p2)InsqQueue(q,p2);}}intmain(){Treer;printf("初始化树\n");CreateTree(r);//以先序遍历顺序建立二叉树printf("\n先序遍历二叉树\n");Preorder(r);//先序遍历printf("\n中序遍历二叉树\n")