队列层次建立二叉树

先层序创建二叉树，在层序创建二叉树的时候，提前创建一个空队列，输入根节点，判断是否为0,这里0代表是空树，动态分配一个内存给根节点（注意：这里是根节点，需要特殊化，名字起个BT），把输入的根节点的值给它，左右儿子赋值为NULL，入队列（这里入队列采用循环队列），进入循环，先把上一个父亲给出队列，然后创建一个它的左儿子，同理，创建一个它的右儿子，依次循环。最后，返回一个根节点（BT）。前序中序后序遍历用的递归，层序有队列用队列，创建一个新的队列，根节点入队，进入循环，出队，返回队头，遍历，左边有的话入队，右边有的话，入队。

/*利用顺序队列，层次建立二叉树*/
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 1000
typedef struct TNode{
   //树的数据结构
	char data;
	struct TNode *lchild,*rchild;
}*BinTree;
typedef struct QNode{
    //队列的数据结构
	struct TNode *data[MAXSIZE];
	int front;
	int rear;
}*Queue;
Queue CreatQ();//创建一个空队列 
void AddQ(Queue q,BinTree T);//将T入队 
BinTree DeleteQ(Queue q);//出队，并返回对头
bool IsEmpty(Queue q);//判断队列是否为空
BinTree CreatBintree();//按层次顺序创建一棵二叉树，并返回根节点
void Postorder(BinTree T);//前序遍历二叉树
void Inorder(BinTree T); //中序遍历二叉树 
void Preorder(BinTree T);//后序遍历二叉树
void LevelorderTraversal(BinTree T);//层序遍历二叉树
int main()
{
   
	struct TNode *T=NULL;
	//A B C D F G I 0 0 E 0 0 H 0 0 0 0 0 0
	T=CreatBintree();
	printf("Inorder: "); 
	Inorder(T);
	puts(" ");
	printf("Preorder: "); 
	Preorder(T);
	puts(" ");
	printf("Postorder: "); 
	Postorder(T);
	puts(" ");
	printf("Levelorder:"); 
	LevelorderTraversal(T);
	return 0;
}
Queue CreatQ()//创建一个空队列 
{
   
	Queue Q=(struct QNode*)malloc(sizeof(struct QNode));
	Q->front=0;
	Q->rear=0;
}
void AddQ(Queue q,BinTree T)//将t入队 
{
   
	if((q->rear+1)%MAXSIZE==q->front){
   
		printf("队列满了");
	}
	q->rear=(q->rear+1)%MAXSIZE;//循环队列 
	q->data[q->rear]=T;//T的地址存入队列中 
}
BinTree DeleteQ(Queue q){
   //出队，并返回对头
	struct TNode *T;
	q->front=(q->front+1)%MAXSIZE;//循环队列 
	T=q->data[q->front];//队列头的地址赋值给T 
	return T;
}
bool IsEmpty(Queue q)//判断队列是否为空
{
   
	return (q->front == q->rear);
}
BinTree CreatBintree()//按层次顺序创建一棵二叉树，并返回根节点
{
   
	char data;
	struct TNode *BT,*T;
	struct QNode *Q;
	Q=CreatQ();
	scanf("%c",&data);//造个根节点 
	getchar();//缓冲流，控制回车和空格 
	if(data!='0')
	{
   
		BT=(struct TNode*)malloc(sizeof(struct TNode));
		BT->data=data;
		BT->lchild=BT->rchild=NULL;
		AddQ(Q,BT);
	}
	else return NULL;
	while(!IsEmpty(Q)){
   
		T=DeleteQ(Q);//把上一个出队 ，并且返回队头，就是上一个的儿子们登场，依次推 
		scanf("%c",&data);//左儿子
		getchar();
		if(data=='0') T->lchild=NULL;//0表示没左儿子 
		else{
   
			T->lchild=(struct TNode*)malloc(sizeof(struct TNode));
			T->lchild->data=data;//左儿子赋值 
			T->lchild->lchild=T->lchild->rchild=NULL;//左孙子和右孙子为空 
			AddQ(Q,T->lchild);//左儿子入队 
		}
		scanf("%c",&data);//右儿子 
		getchar();
		if(data=='0') T->rchild=NULL;// 0表示没右二子 
		else{
   
			T->rchild=(struct TNode*)malloc(sizeof(struct TNode));
			T->rchild->data=data;
			T->rchild->lchild=T->rchild->rchild=NULL;//左孙子和右孙子为空 
			AddQ(Q,T->rchild);//右儿子入队 
		}
	}
	return BT;
}
void Postorder(BinTree T)//先序遍历 
{
   
	if (T == NULL)
	{
   
		return;
	}

	Postorder(T->lchild);
	Postorder(T->rchild);
	printf(" %c", T->data);
}
void Inorder(BinTree T)//中序遍历 
{
   
	if (T == NULL)
	{
   
		return;
	}

	Inorder(T->lchild);
	printf(" %c",T->data);
	Inorder(T->rchild);
}
void Preorder(BinTree T)//后序遍历 
{
   
	if (T == NULL)
	{
   
		return;
	}

	printf(" %c",T->data);
	Preorder(T->lchild);
	Preorder(T->rchild);
}
void LevelorderTraversal(BinTree T){
   //层序遍历，用的是队列层序遍历 
	struct QNode *Q;
	struct TNode *p;
	Q=CreatQ();
	if (T == NULL)
		return;
	AddQ(Q, T);
	while (!IsEmpty(Q))
	{
   
		p = DeleteQ(Q);
		printf(" %c",p->data);
		if(p->lchild)
		  AddQ(Q, p->lchild);
		if(p->rchild)
		  AddQ(Q, p->rchild);
	}
}