二叉树创建非递归、递归前中后序层次遍历

《二叉树创建非递归、递归前中后序层次遍历》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6数据结构实验报告姓名：王晓彬学号：1301100211班级：信计1002时间：2012.04.306实验四二叉树的创建与遍历实验目的：通过上机实验进一步掌握栈、队列、二叉树的存储结构及基本操作的实现方法。实验内容与要求：基于二叉链表存储结构实现二叉树的基本运算，要求：⑴能建立非空二叉树；⑵实现二叉树的先、中、后序递归遍历算法；⑶实现二叉树的非递归的先（或中、或后）序遍历算法及层序遍历算法；⑷记录运行结果并对递归算法和非递归算法的效率加以分析。程序设计：注释：//创建者：王晓彬//班级：信计1002//学号：1301100211//创建时间：2012.04.30//最后修改时间：2012.

2、05.05程序设计：#include#includetypedefintdatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree,*bitrees;typedefstructqueuenode//定义队列结点结构{bitreesch;structqueuenode*next;}queuenode,*queueptr;typedefstruct//定义队列指针{queueptrfront;queueptrrear;}linkqueue;structnode*buli

3、tbitree()//前序法创建二叉树{bitree*T;6inta;scanf("%d",&a);if(a==0)T=NULL;else{T=(bitree*)malloc(sizeof(bitree));T->data=a;T->lchild=bulitbitree();T->rchild=bulitbitree();}return(T);}voidPreOrderTraverse(bitree*T)//递归前序{if(T){printf("%dt",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}

4、voidInOrderTraverse(bitree*T)//递归中序{if(T){InOrderTraverse(T->lchild);printf("%dt",T->data);InOrderTraverse(T->rchild);}}voidPostOrderTraverse(bitree*T)//递归后序{if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%dt",T->data);}}voidInOrder(bitree*T)//非递归前序{bitree*stack[99],*p;i

5、nttop=-1;6if(T!=NULL){top++;stack[top]=T;//根节点入栈while(top>-1){p=stack[top];//出栈top--;printf("%dt",p->data);if(p->rchild!=NULL){top++;stack[top]=p->rchild;}if(p->lchild!=NULL){top++;stack[top]=p->lchild;}}}}voidinitqueue(linkqueue&q)//初始化一个带头结点的队列{q.front=q.rear=(queueptr)malloc(sizeof(queuenode))

6、;q.front->next=NULL;}voidenqueue(linkqueue&q,bitreesp)//入队列{queueptrs;intfirst=1;s=(queueptr)malloc(sizeof(queuenode));s->ch=p;s->next=NULL;q.rear->next=s;q.rear=s;}voiddequeue(linkqueue&q,bitrees&p)//出队列{intdata;queueptrs;s=q.front->next;p=s->ch;6data=p->data;q.front->next=s->next;if(q.rear==s)q.

7、rear=q.front;free(s);printf("%dt",data);}intqueueempty(linkqueueq)//判断队列是否为空{if(q.front->next==NULL)return1;return0;}voidtraverse(bitreesbt)//按层次遍历树中结点{linkqueueq;bitreesp;initqueue(q);p=bt;enqueue(q,p);while(qu