二叉树-借助于队列的层次遍历版本实现

#include <stdio.h>
#include <stdlib.h>

typedef struct BinNode{
	char data;
	struct BinNode *lchild, *rchild;
}BinNode, *BinTree;

typedef BinTree QElemType;
typedef struct QNode{
	QElemType data;
	struct QNode *next;
}QNode, *QueuePtr;
typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

int (LinkQueue &Q);
int EnQueue(LinkQueue &Q, QElemType e);
int DeQueue(LinkQueue &Q, QElemType &e);
int QueueEmpty(LinkQueue Q);


void createBinTree(BinTree &T){
	char ch;
	scanf_s("%c", &ch);
	if (ch == '#'){
		T = NULL;
	}
	else{
		if (!(T = (BinNode*)malloc(sizeof(BinNode)))){
			exit(-1);
		}
		T->data = ch;
		printf("数据%cn", T->data);
		createBinTree(T->lchild);
		createBinTree(T->rchild);
	}
}
/*递归实现二叉树的遍历方法*/
void preOrderTraverse(BinTree &T){
	if (T){
		printf("%c", T->data);
		preOrderTraverse(T->lchild);
		preOrderTraverse(T->rchild);
	}
}

/*二叉树的层次遍历*/
int LevelOrderTraverse(BinTree &T){
	LinkQueue Q;
	InitQueue(Q);
	
	EnQueue(Q, T);
	while (!QueueEmpty(Q)){
		BinTree p;
		DeQueue(Q,p);
		printf("%c", p->data);
		if (p->lchild)
			EnQueue(Q,p->lchild);
		if (p->rchild){
			EnQueue(Q,p->rchild);
		}
	}
	return 1;
}

int main(){
	BinTree T;
	createBinTree(T);
	printf("递归版本的先序遍历");
	preOrderTraverse(T);
	printf("层次遍历版本:n");
	LevelOrderTraverse(T);

	return 0;
}

int (LinkQueue &Q){
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
	if (!Q.front)
		exit(-1);
	Q.front->next = NULL;
	return 1;
}

int EnQueue(LinkQueue &Q, QElemType e){
	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
	if (!p){
		exit(-1);
	}
	p->data = e;
	p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
	return 1;
}

int DeQueue(LinkQueue &Q, QElemType &e){
	if (Q.front == Q.rear)
		return -1;
	QueuePtr p = Q.front->next;
	e = p->data;
	Q.front->next = p->next;
	if (Q.rear == p)
		Q.rear = Q.front;
	free(p);
	return 1;
}

int QueueEmpty(LinkQueue Q){
	return (Q.front->next ==NULL &&  Q.rear->next == NULL) ? 1 : 0;
}