核心思想：二叉树层次i的结点遍历结束后，层次i+1的结点已全部进队，此时队列的元素个数即为层次 i + 1的宽度

难点：如何判断二叉树层次i已经遍历结束呢？可采用一个变量width记录层次i的结点个数，每出队一个元素，变量width减一，当width == 0时，表明层次i遍历完毕。

二叉树层次i遍历结束后（width == 0），只需要用当前队列的元素个数来更新width，表示二叉树层次i + 1的结点个数

int BTWidth(BTNode *b)
{
	if(b == NULL)   //为空树，返回宽度为0
		return 0;

	int width, max;
	int i = 1, max_i; //初始化二叉树层次i，最大宽度所在层次max_i
	BTNode * p;
	SqQueue * qu;       
	InitQueue(qu);     //初始化层次遍历需要借助的队列
	enQueue(qu, b);    //树不为空，根节点进队
	width = 1;         // 宽度置为1
	max = width;       //最大宽度为1
	max_i = i;         //最大宽度所在层次

	while(!QueueEmpty(qu))   //队列为空，表明二叉树遍历完毕，退出循环
	{
		deQueue(qu, p);      //节点出队，赋给p
		width --;            //出队一次，width减1
		if(p -> lchild != NULL) //出队节点的左孩子进队
			enQueue(qu, p -> lchild);
		if(p -> rchild != NULL)
			enQueue(qu, p -> rchild); //出队节点的右孩子出队

		if(width == 0)  //width == 0，表示当前层次i所有节点已遍历完毕
		{               //此时队列元素个数即为下一层次 i + 1 的节点个数
			width = (qu->rear - qu->front + MaxSize) % MaxSize;  //更新宽度
			i++;     //层次变为下一层 i + 1
			if(width > max)  //如果层次 i + 1 宽度 > max
			{
				max = width;  //更新max
				max_i = i;   //并记录最大宽度所在层次
			}
		}
	}

	printf("二叉树层次 %d 的宽度最大\n", max_i);
	return max;
}

/**
* 2020-04-30
* 当第n层的最后一个结点被访问时，第n+1层的最后一个结点已经入队
*/
int getWidthOfBinTree(BTNode T) {
	if(!T) return;
	BTNode Q[MAX], last == T;
	int r, f, max, max_tmp;
	r = f = max= max_tmp = 0;
	Q[++r] = T;
	while(r != f) {
		BTNode p = Q[++f];
		++max_tmp;
		if(p->lChild != NULL) Q[++r] = p->lChild;
		if(p->rChild != NULL) Q[++r] = p->rChild;
		if(p == pre) {
			max = max > max_tmp ? max : max_tmp;
			max_tmp = 0;
			last = Q[r];
		}
	}
	return max;
}

二叉树的层次遍历、二叉树求宽度、图的广度优先搜索

一类问题，层次遍历思想。

1. 二叉树的层次遍历

/*
1.将根结点入队
2.出队访问出队结点，若有左子树将左子树入队，若有右子树将右子树入队
循环2直到队空。
*/
Status LevelOrder(BiTree T)
{
	queue<BiTree> q;
	BiTree p;
	q.push(T);
	while (q.empty() == false)
	{
		p = q.front();
		q.pop();
		visit(p);
		if (p->lchild != NULL)
			q.push(p->lchild);
		if (p->rchild != NULL)
			q.push(p->rchild);
	}
}

2. 二叉树求宽度

int GetWidth(BiTree T)
{
	if (T == NULL)		return 0;  //空树
	queue <BiTree> q;
	BiTree p = T;
	int maxsize = 1;  //根节点为一层
	int len;
	q.push(p);
	while (q.empty() == false)  //保证每次大循环，队列里的结点为某一层的全部结点。
	{
		for (len = q.size(); len > 0; len--)  //将当前队列里结点出队，将它们的所有孩子入队
		{
			p = q.front();
			q.pop();
			if (p->lchild)		q.push(p->lchild);
			if (p->rchild)		q.push(p->rchild);
		}
		int size = q.size();  //当前层的下一层元素个数
		maxsize = max(maxsize, size);
	}
	return maxsize;
}

3. 图的广度优先搜索

/*
1. 访问，入队
2. 出队，将其所有未访问的邻接点，访问并入队
循环2直到队空。
*/
void visit(int v){}
void BFS(ALGraph G, int v)  //用邻接表表示法宽度优先搜索
{
	queue<int> q;
	ArcNode* p;  //边结点
	int visited[MVNum] = {0};  //访问标记数组，0表示未访问
	int w;
	
	visit(v);
	visited[v] = 1;  //已访问
	q.push(v);
	while (q.empty() == false)
	{
		w = q.front();
		q.pop();
		for (p = G.vertexes[w].firstarc; p != NULL; p = p->nextarc)
		{
			if (visited[p->adjvex] == 0)
			{
				visit(p->adjvex);
				visited[p->adjvex] = 1;
				q.push(p->adjvex);
			}
		}
	}
}