求用C语言实现二叉树层次遍历的递归算法，谢谢！！！

Question

如题所述

Answer 1

#include
"stdio.h"
#include
"stdlib.h"
#include
"string.h"
#define
null
0
struct
node
{
char
data;
struct
node
*lchild;
struct
node
*rchild;
};
//先序，中序
建树
struct
node
*create(char
*pre,char
*ord,int
n)
{
struct
node
*
head;
int
ordsit;
head=null;
if(n<=0)
{
return
null;
}
else
{
head=(struct
node
*)malloc(sizeof(struct
node));
head->data=*pre;
head->lchild=head->rchild=null;
ordsit=0;
while(ord[ordsit]!=*pre)
{
ordsit++;
}
head->lchild=create(pre+1,ord,ordsit);
head->rchild=create
(pre+ordsit+1,ord+ordsit+1,n-ordsit-1);
return
head;
}
}
//中序递归遍历
void
inorder(struct
node
*head)
{
if(!head)
return;
else
{
inorder(head->lchild
);
printf("%c",head->data
);
inorder(head->rchild
);
}
}
//中序非递归遍历
void
inorder1(struct
node
*head)
{
struct
node
*p;
struct
node
*stack[20];
int
top=0;
p=head;
while(p||top!=0)
{
while
(p)
{
stack[top++]=p;
p=p->lchild
;
}
p=stack[--top];
printf("%c
",p->data
);
p=p->rchild
;
}
}
//主函数
int
main()
{
struct
node
*
head;
char
pre[30],ord[30];
int
n;
gets(pre);
gets(ord);
n=strlen(pre);
head=create(pre,ord,n);
inorder(head);
printf("\n");
inorder1(head);
printf("\n");
}
//测试事例；
/*
-+a*b%cd/ef
a+b*c%d-e/f
*/
几个月前自己编写，原版
vc++
6.0实验通过
怎么样，老板，第一次上百度知道，好激动
给点面子
给分！给分啊

Answer 2

算法思想：层次遍历目前最普遍用的就是队列的那种方式，不是递归，但是用到while循环，既然题目要求用递归，可以用递归实现该while循环功能。算法如下：
void
TransLevele(Tree
*r)
{
if
(r==NULL)
{
return
;
}
printf("%c",r->ch);
if
(r->left
!=
NULL)
{
InsertQueue(r->left);
}
if
(r->right
!=
NULL)
{
InsertQueue(r->right);
}
Tree
*t
=
DeleteQueue();
TransLevele(t);
}
//测试程序，创建树输入例如ABD##E##C##,根左右创建的方式。
如下代码是测试通过的。
#include
"stdlib.h"
#define
MAX
100
typedef
int
Element;
typedef
struct
tree
{
Element
ch;
struct
tree
*left;
struct
tree
*right;
}Tree;
typedef
struct
queue
{
Tree
*a[MAX];
int
front;
int
rear;
}Queue;
Queue
Qu;
void
Init();
int
InsertQueue(Element
ch);
Tree
*DeleteQueue();
void
CreateTree(Tree
**r);
void
TransLevele(Tree
*r);
void
PrintTree(Tree
*r);
int
main()
{
Tree
*r=NULL;
CreateTree(&r);
PrintTree(r);
printf("\n");
TransLevele(r);
return
0;
}
void
Init()
{
int
i=0;
for
(i=0;
i<MAX;
i++)
{
Qu.a[i]
=
NULL;
}
Qu.front
=
0;
Qu.rear
=
0;
}
int
InsertQueue(Tree
*r)
{
if
(
(Qu.rear+1)%MAX
==
Qu.front)
{
printf("Queue
full!");
return
0;
}
Qu.a[Qu.rear]
=
r;
Qu.rear
=
(Qu.rear+1)%MAX;
return
1;
}
Tree
*DeleteQueue()
{
if
(Qu.front
==
Qu.rear)
{
printf("Queue
empty");
return
NULL;
}
Tree
*t=NULL;
t
=
Qu.a[Qu.front];
Qu.front
=
(Qu.front+1)%MAX;
return
t;
}
void
CreateTree(Tree
**r)
{
Element
ch;
ch=getchar();
if
(ch=='#')
{
(*r)=NULL;
return
;
}
*r
=
(Tree
*)malloc(sizeof(Tree));
(*r)->ch
=
ch;
CreateTree(&((*r)->left));
CreateTree(&((*r)->right));
}
void
PrintTree(Tree
*r)
{
if
(r==NULL)
{
return
;
}
printf("%c",r->ch);
PrintTree(r->left);
PrintTree(r->right);
}
void
TransLevele(Tree
*r)
{
if
(r==NULL)
{
return
;
}
printf("%c",r->ch);
if
(r->left
!=
NULL)
{
InsertQueue(r->left);
}
if
(r->right
!=
NULL)
{
InsertQueue(r->right);
}
Tree
*t
=
DeleteQueue();
TransLevele(t);
}