/*层次遍历二叉树，每一层遍历完成以后都重新插入特定的指针

（比如本例使用的特殊指针是数据元素为#，左右儿子为空的指针），

这样在每次访问到所指向数据为#的队列中的结点指针是就知道该指针是这层的末尾，需要统计，

但是又有个问题是，最后队中所剩下的节点指针起数据一定是#，因此会陷入无限循环，解决的方法是，

在发现当前结点指针所指向的结点的数据是#的时候，在查看队列中是否还有元素（节点指针），

如果没有，则说明是最后一层的最后一个结点指针，所以应该跳出循环*/

#include <stdio.h>

#include <malloc.h>

#define M 100

typedef struct BTNode

{

	char data;

	struct BTNode *lchild;

	struct BTNode *rchild;

}BTNode;

typedef struct Queue

{

	BTNode *data[M];

	int f;

	int r;

}Queue;

//创建二叉树（先序方式）

void createTree(BTNode* *T)

{

	char ch = getchar();

	if(ch=='#')

	{

		*T=NULL;

		return;

	}

	(*T) = (BTNode*)malloc(sizeof(BTNode));

	(*T)->data = ch;

	createTree(&(*T)->lchild);

	createTree(&(*T)->rchild);

}

void preOrder(BTNode *T)//先序遍历

{

	if(T==NULL) return;

	printf("%c\t", T->data);

	if(T->lchild!=NULL)

		preOrder(T->lchild);

	if(T->rchild != NULL)

		preOrder(T->rchild);

}

//求二叉树的宽度

int width(BTNode *T)

{

	if(T==NULL) return 0;

	int num = 0;

	int max = 0;

	Queue Q;

	Q.r = 0;

	Q.f = 0;//initialize Queue

	memset(Q.data,NULL,M);

	Q.data[Q.r++] = T;

	BTNode *t = (BTNode*)malloc(sizeof(BTNode));

	t->data = '#';

	t->lchild = NULL;

	t->rchild = NULL;

	Q.data[Q.r++] = t;//enter Queue

	while(Q.r!=Q.f)

	{

		t = Q.data[Q.f++];

		if(t->data=='#')

		{

			if(max<num)

			{

				max = num;

				num = 0;

			}

			if(Q.data[Q.f]!=NULL)

			{

				t = (BTNode*)malloc(sizeof(BTNode));

				t->data = '#';

				t->lchild = NULL;

				t->rchild = NULL;

				Q.data[Q.r++] = t;

			}

		}

		else

		{

			++num;

			if(t->lchild) Q.data[Q.r++] = t->lchild;

			if(t->rchild) Q.data[Q.r++] = t->rchild;

		}

	}

	return max;

}

int main(int argc, char const *argv[])

{

	BTNode *T;

	createTree(&T);

	puts("PreOrder visit:");

	preOrder(T);

	putchar('\n');

	printf("the width of BTree is %d\n",width(T) );

	return 0;

}