编辑代码

#include <stdio.h>
#include <stdlib.h>
//二叉树的实现-二叉链表(左子，右子) 
typedef struct node{
	char data;
	struct node *lchild,*rchild;
}BNode,*BTree;

BTree createTree();
void visit(BTree T);	//访问T，打印根节点的数据 
void preOrder(BTree T);    //前序 
void inOrder(BTree T);    //中序 
void postOrder(BTree T);    //后序 
void layOrder(BTree T);    //层次遍历 

#define M (1000+5)
typedef BTree ElemType;
typedef struct{
	ElemType data[M];
	int front,rear;
}SqCyQueue;

void init(SqCyQueue *q);
int isEmpty(SqCyQueue q);
int isFull(SqCyQueue q);
int push(SqCyQueue *q,ElemType item);
int pop(SqCyQueue *q,ElemType *item);

int main(){
	freopen("btree02.in","r",stdin);
	BTree T = createTree();
	printf("\n前序遍历：");
	preOrder(T);
	printf("\n中序遍历：");
	inOrder(T);
	printf("\n后序遍历：");
	postOrder(T);
	printf("\n层次遍历：");
	layOrder(T);
	return 0; 
}

BTree createTree(){
	BTree T = NULL;
	char ch;
	while(1){
		scanf("%c",&ch);
		if(ch != '\n' && ch != ' ')
			break;
	}
	if(ch != '#'){
		T = (BTree)malloc(sizeof(BNode));
		T->lchild = T->rchild = NULL;
		T->data = ch;
		T->lchild = createTree();
		T->rchild = createTree();
	}
	return T;
}

void visit(BTree T)
{
	printf("%c",T->data);
}

void preOrder(BTree T)
{
	if(T == NULL)
		return;
	visit(T);
	preOrder(T->lchild);
	preOrder(T->rchild);
}

void inOrder(BTree T)
{
	if(T == NULL)
		return;
	inOrder(T->lchild);
	visit(T);
	inOrder(T->rchild);
}
void postOrder(BTree T)
{
	if(T == NULL)
		return;
	postOrder(T->lchild);
	postOrder(T->rchild);
	visit(T);
}
void layOrder(BTree T)
{
	SqCyQueue q;
	init(&q);
	push(&q,T);
	while(!isEmpty(q)){
		pop(&q,&T);
		visit(T);
		q.front ++;
		T = q.front;
		visit(T);
		if(T->lchild != NULL)
		{
			q.rear ++;
			q.rear = T->lchild;	
		}
		if(T->rchild != NULL)
		{
			q.rear ++;
			q.rear = T->rchild;
		}
	}
}

void init(SqCyQueue *q)
{
	q->front = q->rear = 0;
}

int isEmpty(SqCyQueue q)
{
	return q.front == q.rear;
}

int isFull(SqCyQueue q)
{
	return (q.rear + 1) % M == q.front;
}

int push(SqCyQueue *q,ElemType item)
{
	if(isFull(*q)){
		printf("队列已满，入队失败！\n");
		return 0;
	}
	q->data[q->rear] = item;
	q->rear = (q->rear + 1) % M;
	return 1;
}

int pop(SqCyQueue *q,ElemType *item)
{
	if(isEmpty(*q)){
		printf("队列为空，出队失败！\n");
		return 0;
	}
	*item = q->data[q->front];
	q->front = (q->front + 1) % M;
	return 1;
}