二叉树创建非递归、递归前中后序层次遍历
姓名:王晓彬
学号:1301100211
班级:信计1002
时间:2012.04.30
1
实验四 二叉树的创建与遍历 实验目的:
通过上机实验进一步掌握栈、队列、二叉树的存储结构及基本操作的实现方法。
实验内容与要求:
基于二叉链表存储结构实现二叉树的基本运算，要求:
?能建立非空二叉树;
?实现二叉树的先、中、后序递归遍历算法;
?实现二叉树的非递归的先(或中、或后)序遍历算法及层序遍历算法;
?记录运行结果并对递归算法和非递归算法的效率加以分析。 程序
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
:
注释: //创建者:王晓彬
班级:信计1002 //
//学号:1301100211
//创建时间:2012.04.30
//最后修改时间:2012.05.05
程序设计:
#include
#include
typedef 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* bulitbitree() //前序法创建二叉树 {
bitree *T;
2
int a;
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);
}
void PreOrderTraverse(bitree *T) //递归前序
{
if(T)
{
printf("%d\t",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(bitree *T) //递归中序
{
if(T)
{
InOrderTraverse(T->lchild);
printf("%d\t",T->data);
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(bitree *T) //递归后序
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%d\t",T->data);
}
}
void InOrder(bitree* T) //非递归前序 {
bitree *stack[99],*p; int top=-1;
3
if(T!=NULL)
{
top++;
stack[top]=T; //根节点入栈
while(top>-1)
{
p=stack[top]; //出栈
top--;
printf("%d\t",p->data);
if(p->rchild!=NULL)
{
top++;
stack[top]=p->rchild;
}
if(p->lchild!=NULL)
{
top++;
stack[top]=p->lchild;
}
}
}
}
void initqueue(linkqueue &q) //初始化一个带头结点的队列 {
q.front=q.rear=(queueptr)malloc(sizeof(queuenode));
q.front->next=NULL;
}
void enqueue(linkqueue &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;
4
data=p->data;
q.front->next=s->next;
if(q.rear==s)
q.rear=q.front;
free(s);
printf("%d\t",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->rchild);
}
}
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");
5
traverse(T);printf("\n"); }
运行结果:
效率分析:
1.递归算法的优点
(1)问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
的数学模型或算法设计方法本身就是递归的，采用递归算法来描述它们非常自然;
(2)描述直观，结构清晰、简洁;正确性证明比非递归算法容易。 2.递归算法的不足
(1)算法的执行时间与空间开销往往比非递归算法要大，当问题规模较大时尤为明显;
(2)对算法进行优化比较困难;
(3)分析跟踪算法的执行过程比较麻烦;
(4)描述算法的语言不具有递归功能时，算法无法描述。
6
浙公网安备 33021202002483