#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
struct chtp
{
int len;
char ch[100];
};
typedef struct QNode
{
BiTree point;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
struct chtp s;
int i=0;
int CreateBiTree(BiTree &T)
{
char c;
c=s.ch[i];i++;
if(c=='#') T=NULL;
else
{
if(!(T=(BiTNode*) malloc (sizeof(BiTNode)))) exit(-1);
T->data=c;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return 1;
}//先序递归建立二叉树
int InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)exit (-1);
Q.front->next=NULL;
return 1;
}
int EnQueue(LinkQueue &Q,BiTree &p)
{
QueuePtr t;
t= (QueuePtr)malloc (sizeof(QNode));
if(!t) exit (-1);
t->point=p;t->next=NULL;
Q.rear->next=t;
Q.rear=t;
return 1;
}
int DeQueue(LinkQueue &Q,BiTree p)
{
QueuePtr t;
if(Q.front==Q.rear)return -1;
t=Q.front->next;
p=t->point;
Q.front->next=t->next;
if(Q.rear==t) Q.rear==Q.front;
free(t);
return 1;
}
LevelTraverse(BiTree &T)
{
LinkQueue Q;
InitQueue(Q);
BiTree p;
p=T;EnQueue(Q,p);DeQueue(Q,p);
while(p)
{
printf("%c",p->data);
if(p->lchild) EnQueue(Q, p->lchild);
if(p->rchild) EnQueue(Q,p->rchild);
DeQueue(Q,p);
}
}//层次遍历二叉树
main()
{
BiTree T;
char exp[100];
int j;
printf("请输入二叉树结点,并以!号结束\n");
gets(exp);
for(j=0,s.len=0;exp[j]!='!';j++,s.len++) s.ch[j]=exp[j];
CreateBiTree(T);
printf("二叉树建立完毕!\n");
LevelTraverse(T);
}
自己写的一个层次遍历二叉树的非递归算法,可是调试的时候说出队入队时有异常,我不是很懂,大家帮忙看看,谢谢了!