#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef char BiElemType;
typedef struct BiNode {
BiElemType data;
struct BiNode* lchild;
struct BiNode* rchild;
}bi,BiTree;
typedef BiTree ElemType;
typedef struct tag {
BiTree p;
struct tag pnext;
}tag_t,*ptag_t;
void PreOrder(BiTree p) {
if (p!= NULL) {
putchar(p->data);
PreOrder(p->lchild);
PreOrder(p->rchild);
}
}
void InOrder(BiTree p) {
if (p != NULL) {
InOrder(p->lchild);
putchar(p->data);
InOrder(p->rchild);
}
}
void LaOrder(BiTree p) {
if (p != NULL) {
LaOrder(p->lchild);
LaOrder(p->rchild);
putchar(p->data);
}
}
typedef struct LinkNode {
ElemType data;
struct LinkNode* next;
}ln;
typedef struct {
ln* front, * rear;
}qu,Queue;
void QueueInit(qu&q) {
q.front = q.rear = (ln)malloc(sizeof(ln));
q.front->next = NULL;
}
bool Isempty(qu q) {
if (q.front == q.rear) {
return true;
}
return false;
}
void EnQueue(qu& q, ElemType x) {
ln* s = (ln*)malloc(sizeof(ln));
s->data = x;
s->next = q.rear->next;
q.rear->next = s;
q.rear = s;
q.rear->next = NULL;
}
bool DeQueue(qu& q, ElemType& x) {
if (q.front == q.rear) {
return false;
}
ln* p = q.front->next;
x = p->data;
p->next = q.front->next;
if (q.rear == p) {
q.front = q.rear;
}
free(p);
return true;
}
void LevelOrder(BiTree t) {
qu q;
QueueInit(q);
BiTree p;
EnQueue(q, t);//树根入队
while (!Isempty(q))
{
DeQueue(q, p);//出队当前结点并打印
putchar(p->data);
if (p->lchild != NULL)
EnQueue(q, p->lchild);
if (p->rchild != NULL)
EnQueue(q, p->rchild);
}
}
int main() {
BiTree pnew;
BiTree tree = NULL;
char x;
ptag_t pfront = NULL, prear = NULL, listpnew = NULL, pcur =NULL;
while (scanf("%d", &x)!=EOF) {
if (x =='\n') {
break;
}
pnew = (BiTree)calloc(1, sizeof(bi));
pnew->data = x;
listpnew = (ptag_t)calloc(1, sizeof(tag_t));
listpnew->p = pnew;
if (tree == NULL) {
tree = pnew;
pfront = listpnew;
prear = listpnew;
continue;
}
else {
prear->pnext = listpnew;
prear = listpnew;
}
if (NULL==pcur->p->lchild) {//就是这里！
pcur->p->lchild = pnew;
}
else if (pcur->p->rchild == NULL) {
pcur->p->rchild = pnew;
pcur=pcur->pnext ;
}
}
PreOrder(tree);
InOrder(tree);
LaOrder(tree);
LevelOrder(tree);
}
