假设二叉树采用二叉链表存储结构，设计一个算法，求非空二叉树b的宽度（即具有结点数最多的那一层的结点个数）。_假设二叉树采用二叉链表存储结构,设计一个算法

结合图例，一目了然！ 

（一）熟悉掌握层序遍历的算法编程：

C语言实现层序遍历：

typedef struct{
	BiTree data[MaxSize];//保存队列中的结点指针
	int level[MaxSize];//保存data中相同下标结点的层次
	int front, rear;
}BQ;
void leverOrder(BiTree b) {
	BiTree p;
	BQ Q;
	Q.front = Q.rear = -1;//队列为空
	Q.rear++;
	Q.data[Q.rear] = b;//根结点指针入队
	while (Q.front < Q.rear) {
		Q.front++;//出队
		p = Q.data[Q.front];//出队结点
		printf("%c ", p->data);
		if (p->lchild != NULL) {//左孩子进队列
			Q.rear++;
			Q.data[Q.rear] = p->lchild;
		}
		if (p->rchild != NULL) {//右孩子进队列
			Q.rear++;
			Q.data[Q.rear] = p->rchild;
		}
	}
}

 （二）利用层序遍历和相关算法设计出算法方案

代码如下：

typedef struct{
	BiTree data[MaxSize];//保存队列中的结点指针
	int level[MaxSize];//保存data中相同下标结点的层次
	int front, rear;
}BQ;
 
int BTWidth(BiTree b) {
	BiTree p;
	int k, max, i, n;
	BQ Q;
	Q.front = Q.rear = -1;//队列为空
	Q.rear++;
	Q.data[Q.rear] = b;//根结点指针入队
	Q.level[Q.rear] = 1;//根结点的层次为1
	while (Q.front<Q.rear) {
		Q.front++;//出队
		p = Q.data[Q.front];//出队结点
		k = Q.level[Q.front];//出队结点的层次
		if (p->lchild != NULL) {//左孩子进队列
			Q.rear++;
			Q.data[Q.rear] = p->lchild;
			Q.level[Q.rear] = k + 1;
		}
		if (p->rchild != NULL) {//右孩子进队列
			Q.rear++;
			Q.data[Q.rear] = p->rchild;
			Q.level[Q.rear] = k + 1;
		}
	}
	max = 0, i = 0;//max保存同一层最多的结点个数
	k = 1;//k表示从第一层开始查找
	while (i<=Q.rear) {//i扫描队中所有元素
		n = 0;//n统计第k层的结点个数
		while (i <= Q.rear && Q.level[i] == k) {
			n++;
			i++;
		}
		k = Q.level[i];
		if (n > max)
			max = n;//保存最大的n
	}
	return max;
}

（1）其中，这部分代码的逻辑是为了获取level数组

（2）这部分代码是为了统计出level数组中的具有结点数最多的那一层的结点个数。

（3）完整的推导过程如下图所示： 

（4）实验结果：

（5）C语言完整代码：

//假设二叉树采用二叉链表存储结构，设计一个算法，求非空二叉树b的宽度（即具有结点数最多
//的那一层的结点个数）
 
//在考层次遍历
//在层次遍历的过程中，标记出每一个结点的层数（或者说是将每一层的结点做出来分类）
//所以其实这道题的重点就是‘按层划分’
 
//三种解决方案
//①记录的同时，为每个结点绑定一个对应的高度值
//②做两个队列，轮换使用
//③一个队列，中间加上‘分界线结点’
 
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
 
#define MaxSize 100
typedef char ElemType;
typedef struct BiNode {
	ElemType data;
	BiNode* lchild;
	BiNode* rchild;
 
}BiNode, * BiTree;
 
//构建二叉树
BiNode* Create(BiNode* bt) {
	static int i = 0;
	char ch;
	//string str = "AB#D##C##";
	//string str = "124##56##7##3##";
	//string str = "ABD#G##E##CF###";
	//string str = "ABD#GH##I##E##CF###";
	//string str = "ABD#GH##I##E##CFJ##K###";
	string str = "ABDH##I##E#J##CFK###GL###";
	ch = str[i++];
	if (ch == '#')bt = NULL;//建立一棵空树 
	else {
		bt = (BiTree)malloc(sizeof(BiNode)); bt->data = ch;//生成一个结点，数据域为ch
		bt->lchild = Create(bt->lchild);//递归建立左子树
		bt->rchild = Create(bt->rchild);//递归建立右子树
	}
	return bt;
}
 
typedef struct{
	BiTree data[MaxSize];//保存队列中的结点指针
	int level[MaxSize];//保存data中相同下标结点的层次
	int front, rear;
}BQ;
 
int BTWidth(BiTree b) {
	BiTree p;
	int k, max, i, n;
	BQ Q;
	Q.front = Q.rear = -1;//队列为空
	Q.rear++;
	Q.data[Q.rear] = b;//根结点指针入队
	Q.level[Q.rear] = 1;//根结点的层次为1
	while (Q.front<Q.rear) {
		Q.front++;//出队
		p = Q.data[Q.front];//出队结点
		k = Q.level[Q.front];//出队结点的层次
		if (p->lchild != NULL) {//左孩子进队列
			Q.rear++;
			Q.data[Q.rear] = p->lchild;
			Q.level[Q.rear] = k + 1;
		}
		if (p->rchild != NULL) {//右孩子进队列
			Q.rear++;
			Q.data[Q.rear] = p->rchild;
			Q.level[Q.rear] = k + 1;
		}
	}
	max = 0, i = 0;//max保存同一层最多的结点个数
	k = 1;//k表示从第一层开始查找
	while (i<=Q.rear) {//i扫描队中所有元素
		n = 0;//n统计第k层的结点个数
		while (i <= Q.rear && Q.level[i] == k) {
			n++;
			i++;
		}
		k = Q.level[i];
		if (n > max)
			max = n;//保存最大的n
	}
	return max;
}
 
 
void leverOrder(BiTree b) {
	BiTree p;
	BQ Q;
	Q.front = Q.rear = -1;//队列为空
	Q.rear++;
	Q.data[Q.rear] = b;//根结点指针入队
	while (Q.front < Q.rear) {
		Q.front++;//出队
		p = Q.data[Q.front];//出队结点
		printf("%c ", p->data);
		if (p->lchild != NULL) {//左孩子进队列
			Q.rear++;
			Q.data[Q.rear] = p->lchild;
		}
		if (p->rchild != NULL) {//右孩子进队列
			Q.rear++;
			Q.data[Q.rear] = p->rchild;
		}
	}
}
int main() {
	//创建一棵二叉树
	BiTree T = (BiTree)malloc(sizeof(BiNode));//创建一颗二叉树
	T = Create(T);
	printf("这棵非空二叉树的层序遍历序列：\n");
	leverOrder(T);
	int btWidth = BTWidth(T);
	printf("\n非空二叉树b的宽度（即具有结点数最多的那一层的结点个数）为：%d 个\n", btWidth);
}

过程推演是小编的想法，如有不对的地方，欢迎指正，我将继续制作出更加有质量的博客内容，希望个位小伙伴能够点个赞，这是对我的付出的肯定，谢谢您们！！！