#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
//首先实现一个队列
typedef char datatype;
typedef struct queue
{
datatype data;
struct queue *next;
}queue; //链队列的节点
typedef struct //链队列类型
{
queue *front,*rear; //队头指针、队尾指针
}linkqueue; //链队列
linkqueue *q; //q是链队列指针
void INITQUEUE(linkqueue *q) //置空队列
{
//q->front=(queue *)malloc(sizeof(queue));
q->front=(struct queue *)malloc(sizeof(struct queue)); //申请头节点
q->rear=q->front; //尾指针指向头节点
q->front->next=NULL; //头节点指针为空
}
bool EMPTYQUEUE(linkqueue *q) //判断队列是否为空
{
if(q->front == q->rear)
return 1;
else
return 0;
}
void ENQUEUE(linkqueue *q,datatype e) //将元素e插入队尾
{
queue *p;
p=(queue *)malloc(sizeof(queue)); //生成新节点p
p->data=e;
p->next=NULL; //新节点赋值
q->rear->next=p;
q->rear=p;
}
datatype DEQUEUE(linkqueue *q,datatype &e) //出队
{
if(EMPTYQUEUE(q))
{
printf("\nqueue is empty\n");
return NULL;
}
else
{
queue *p;
p=q->front->next;
e=p->data;
q->front->next=p->next;
if(q->rear->next==p->next)
q->front=q->rear;
free(p);
return e;
}
}
datatype GETFRONT(linkqueue *q) //取队头元素
{
if(EMPTYQUEUE(q))
{
printf("\nqueue is empty\n");
return NULL;
}
else
return(q->front->next->data);
}
//二叉树的建立
typedef struct bitnode
{
char data;
struct bitnode *lchild;
struct bitnode *rchild;
} *bitree; //二叉树链式存储结构，bittree为头指针
bitree CREATTREE()
{
//printf("请输入字符型结点，以字母n代表空结点\n");
char x;
scanf("%c",&x);
if(x == 'n')
return NULL;
bitnode *r;
r=(struct bitnode *)malloc(sizeof(struct bitnode));
r->data=x;
r->lchild=CREATTREE();
r->rchild=CREATTREE();
return r;
}
//前序遍历
void PREORDER(bitree t)
{
if(t != NULL)
{
printf("%C\n",t->data);
PREORDER(t->lchild);
PREORDER(t->rchild);
}
}
//后序遍历
void POSTORDER(bitree t)
{
if(t != NULL)
{
POSTORDER(t->lchild);
POSTORDER(t->rchild);
printf("%C\n",t->data);
}
}
//层次遍历
void LEVELORDER(bitree t)
{
//queue *a; //定义一个队列
linkqueue *q; //q为队列的结构指针
q=(linkqueue *)malloc(sizeof(linkqueue));//必须先给指针分配地址
INITQUEUE(q); //队置空
if(t==NULL) return;
ENQUEUE(q,t->data);//根结点入队
while(!EMPTYQUEUE(q))
{
char x;
t->data=DEQUEUE(q,x);
printf("%c",t->data);
if(t->lchild)
ENQUEUE(q,t->lchild->data); //左子树入队
if(t->rchild)
ENQUEUE(q,t->rchild->data); //右子树入队
}
}
void main()
{
printf("-----------------------------------------------------------------\n");
printf("二叉树的建立，前序遍历，后序遍历，层次遍历\n");
printf("-----------------------------------------------------------------\n");
printf("\n以下将使用递归的方法建立二叉树\n\n");
printf("请按照前序遍历的顺序输入一组结点，以字母n代表空结点\n\n");
printf("注意：将叶子结点仍看成是有左右子树的，其左右子树都为n，即空结点。例如：输入ann表示只有根结点a或输入anbnn表示根结点a，左子树为空，右子树为b，等等\n\n");
bitree t;
t = CREATTREE();//建立二叉树
printf("\n其前序遍历为:\n");
PREORDER(t);
printf("\n其后序遍历为:\n");
POSTORDER(t);
printf("\n其层次遍历为:\n");
LEVELORDER(t);
}
例如输入abnncnn,表示根节点a，左子树b，右c
前序后序均正常，层次出现死循环，不断打印c
求大家帮个忙，置顶的c++描述的我看不懂，谢谢
跟版主定义的有什么不同呢？