《二叉树创建非递归、递归前中后序层次遍历.doc》由会员分享，可在线阅读，更多相关《二叉树创建非递归、递归前中后序层次遍历.doc（6页珍藏版）》请在金锄头文库上搜索。
1、1数据结构实验报告 姓名：王晓彬 学号：1301100211 班级：信计1002 时间：2012.04.30 实验四 二叉树的创建与遍历实验目的：通过上机实验进一步掌握栈、队列、二叉树的存储结构及基本操作的实现方法。实验内容与要求：基于二叉链表存储结构实现二叉树的基本运算，要求： 能建立非空二叉树； 实现二叉树的先、中、后序递归遍历算法； 实现二叉树的非递归的先（或中、或后）序遍历算法及层序遍历算法； 记录运行结果并对递归算法和非递归算法的效率加以分析。程序设计： 注释： /创建者：王晓彬 /班级：信计1002 /学号：1301100211 /创建时间：2012.04.30 /最后修改时间：2
2、012.05.05程序设计：#include #includetypedef int datatype;typedef struct node datatype data; struct node *lchild,*rchild;bitree,*bitrees;typedef struct queuenode /定义队列结点结构 bitrees ch; struct queuenode *next;queuenode,*queueptr; typedef struct /定义队列指针 queueptr front; queueptr rear;linkqueue; struct node* b
3、ulitbitree() /前序法创建二叉树bitree *T;int a;scanf(%d,&a);if(a=0)T=NULL;elseT=(bitree*)malloc(sizeof(bitree);T-data=a;T-lchild=bulitbitree();T-rchild=bulitbitree();return (T);void PreOrderTraverse(bitree *T) /递归前序 if(T) printf(%dt,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); void InOrde
4、rTraverse(bitree *T) /递归中序 if(T) InOrderTraverse(T-lchild); printf(%dt,T-data); InOrderTraverse(T-rchild); void PostOrderTraverse(bitree *T) /递归后序 if(T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(%dt,T-data); void InOrder(bitree* T) /非递归前序bitree *stack99,*p; int top=-1; if(T!=N
5、ULL) top+; stacktop=T; /根节点入栈while(top-1) p=stacktop; /出栈 top-; printf(%dt,p-data); if(p-rchild!=NULL) top+; stacktop=p-rchild; if(p-lchild!=NULL) top+; stacktop=p-lchild; void initqueue(linkqueue &q) /初始化一个带头结点的队列 q.front=q.rear=(queueptr)malloc(sizeof(queuenode); q.front-next=NULL;void enqueue(lin
6、kqueue &q,bitrees p) /入队列 queueptr s; int first=1; s=(queueptr)malloc(sizeof(queuenode); s-ch=p; s-next=NULL; q.rear-next=s; q.rear=s;void dequeue(linkqueue &q,bitrees &p) /出队列 int data; queueptr s; s=q.front-next; p=s-ch; data=p-data; q.front-next=s-next; if(q.rear=s) q.rear=q.front; free(s); print
7、f(%dt,data);int queueempty(linkqueue q) /判断队列是否为空 if(q.front-next=NULL) return 1; return 0;void traverse(bitrees bt) /按层次遍历树中结点 linkqueue q; bitrees p; initqueue(q); p=bt; enqueue(q,p); while(queueempty(q)!=1) dequeue(q,p); if(p-lchild!=NULL) enqueue(q,p-lchild); if(p-rchild!=NULL) enqueue(q,p-rchil
8、d); void main() /主程序 bitree *T;printf(输入二叉树(以0为空节点标志):n); T=bulitbitree();printf(递归法输出:n);printf(t先序遍历为:n);PreOrderTraverse(T);printf(n);printf(t中序遍历为:n);InOrderTraverse(T);printf(n);printf(t后序遍历为:n);PostOrderTraverse(T);printf(n);printf(非递归先序遍历为:n);InOrder(T);printf(n);printf(层次遍历为:n);traverse(T);printf(n);运行结果：效率分析：1.递归算法的优点(1)问题的数学模型或算法设计方法本身就是递归的，采用递归算法来描述它们非常自然；(2)描述直观，结构清晰、简洁；正确性证明比非递归算法容易。2.递归算法的不足(1)算法的执行时间与空间开销往往比非递归算法要大，当问题规模较大时尤为明显；(2)对算法进行优化比较困难；(3)分析跟踪算法的执行过程比较麻烦；(4)描述算法的语言不具有递归功能时，算法无法描述。
