二叉树的层次遍历有点问题
#include<iostream>#include<stdio.h>
#define OK 1
#define ERROR -1
#define OVERFLOW -2
typedef char Type;
using namespace std;
typedef struct node
{
Type data;
struct node *lchild,*rchild;
}node,*tree;
typedef struct QNode
{
char data;
struct QNode *next;
}*link;
typedef struct
{
link front;
link rear;
}linkqueue;
void initqueue(linkqueue&q)
{
q.front =q.rear = new QNode();
if(!q.front) exit(OVERFLOW);
q.front->next = NULL;
}
int EnQueue (linkqueue&q,char e)
{
QNode *p = new QNode();
if(!p) exit(OVERFLOW);
p->data = e;
p->next = NULL;
q.rear->next = p;
q.rear = p;
return OK;
}
int DeQueue (linkqueue&q)
{
if(q.front ==q.rear)
{
cout<<"已为空，不可再删除"<<endl;
return ERROR;
}
link p =q.front->next;
q.front->next = p->next;
if(q.rear == p)
q.rear =q.front;
delete p;
return OK;
}
int EmptyQueue(linkqueue&q)
{
if(q.rear==q.front) return 1;
else return 0;
}
tree creattree(tree&t)
{
char ch;
ch=getchar();
if(ch=='#')
t=NULL;
else
{
t=new node();
t->lchild=t->rchild=NULL;
if(!t)exit (OVERFLOW);
t->data=ch;
creattree(t->lchild);
creattree(t->rchild);//实现递归
}
return t;
}
int TravelTree(tree r)//层次遍历
{
linkqueue q;
initqueue(q);
tree p,p1,p2;
p=r;
if(!p)
{
cout<<"二叉树为空";
return ERROR;
}
EnQueue(q,p->data);
while(!EmptyQueue(q))
{
cout<<q->front->data;
p1=p->lchild;
p2=p->rchild;
if(p1) EnQueue(q,p1->data);
if(p2) EnQueue(q,p2->data);
DeQueue(q);
}
return OK;
}
