#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
typedef char ElemType;
typedef struct Node
{
ElemType val;
struct Node *lchild;
struct Node *rchild;
} TNode, *BiTree;
typedef struct
{
BiTree *base;
BiTree *top;
int stacksize;
} Stack;
typedef struct
{
BiTree data[MAXSIZE];
int front, rear;
} Queue;
void InitStack(Stack *S)
{
S->base = (BiTree *)malloc(sizeof(BiTree) * 20);
if(!S->base)
{
exit(-1);
}
S->top = S->base;
S->stacksize = 20;
}
int StackEmpty(Stack *S)
{
if(S->base == S->top)
{
return 1;
}
else
{
return 0;
}
}
void Push(Stack *S, BiTree b)
{
if(S->top - S->base >= S->stacksize)
{
S->base = (BiTree *)realloc(S->base, sizeof(BiTree) * (S->stacksize + 10));
if(!S->base)
{
exit(-1);
}
S->top = S->base + S->stacksize;
S->stacksize += 10;
}
*S->top = b;
S->top += 1;
}
void Pop(Stack *S, BiTree *b)
{
if(S->top == S->base)
{
exit(-1);
}
S->top -= 1;
*b = *S->top;
}
void GetTop(Stack *S, BiTree *b)
{
if(S->top == S->base)
{
exit(-1);
}
S->top -= 1;
*b = *S->top;
S->top += 1;
}
void InitQueue(Queue *Q)
{
Q->front = Q->rear = 0;
}
int QueueEmpty(Queue *Q)
{
if(Q->front == Q->rear)
{
return 1;
}
else
{
return 0;
}
}
void EnQueue(Queue *Q, BiTree e)
{
if((Q->rear + 1) % MAXSIZE == Q->front)
{
exit(-1);
}
Q->data[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAXSIZE;
}
void DeQueue(Queue *Q, BiTree *e)
{
if(Q->rear == Q->front)
{
exit(-1);
}
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZE;
}
void Create(BiTree *T)
{
printf("Input a char: ");
ElemType ch = getchar();
getchar();
if(ch == '#')
{
(*T) = NULL;
}
else
{
(*T) = (BiTree)malloc(sizeof(TNode));
if(!T)
{
exit(-1);
}
(*T)->val = ch;
Create(&(*T)->lchild);
Create(&(*T)->rchild);
}
}
void PreOrder(BiTree T, Stack *S)
{
BiTree p = T;
while(p || !StackEmpty(S))
{
if(p)
{
printf("%4c", p->val);
Push(S, p);
p = p->lchild;
}
else
{
Pop(S, &p);
p = p->rchild;
}
}
}
void InOrdeer(BiTree T, Stack *S)
{
BiTree p = T;
while(p || !StackEmpty(S))
{
if(p)
{
Push(S, p);
p = p->lchild;
}
else
{
Pop(S, &p);
printf("%4c", p->val);
p = p->rchild;
}
}
}
void PostOrder(BiTree T, Stack *S)
{
BiTree p = T;
BiTree cur = NULL;
while(p || !StackEmpty(S))
{
if(p)
{
Push(S, p);
p = p->lchild;
}
else
{
GetTop(S, &p);
if(p->rchild && cur != p->rchild)
{
p = p->rchild;
Push(S, p);
p = p->lchild;
}
else
{
Pop(S, &p);
printf("%4c", p->val);
cur = p;
p = NULL;
}
}
}
}
void LevelOrder(BiTree T, Queue *Q)
{
BiTree p = T;
EnQueue(Q, p);
while(!QueueEmpty(Q))
{
DeQueue(Q, &p);
printf("%4c", p->val);
if(p->lchild)
{
EnQueue(Q, p->lchild);
}
if(p->rchild)
{
EnQueue(Q, p->rchild);
}
}
}
int main()
{
Stack S;
Queue Q;
BiTree T;
InitStack(&S);
InitQueue(&Q);
Create(&T);
printf("前序遍历：");
PreOrder(T, &S);
printf("\n");
printf("中序遍历：");
InOrdeer(T, &S);
printf("\n");
printf("后序遍历：");
PostOrder(T, &S);
printf("\n");
printf("层次遍历：");
LevelOrder(T, &Q);
printf("\n");
return 0;
}
网友评论