题目

一个二叉树采用二叉链表存储，设计一个函数计算这个二叉树的宽度

解题思路

采用层次遍历，将每一个结点的信息存储在数组中，结点的信息包括这个结点的层数，以及结点的左右子树，数据类型(为char型字符),然后对这个数组进行遍历，层号数目最多的即为该二叉树最大宽度处的层号，然后计算这个层号的数目，即为最大宽度

函数源码

int maxNode(BTNode *b)	//求该二叉树的宽度,也就是二叉树中最大的度
{
	St que[maxSize];
	int front,rear;	//定义顺序非循环队列
	int Lno=0,i,j,n,max=0;
	front=0,rear=0;	//队头队尾为零，把队列置空
	BTNode *q;
	if(b!=NULL)
	{
		++rear;
		que[rear].p=b;	//二叉树的根入队
		que[rear].lno=1;	//树根所在的层次号设为1；若题中指定第一层层号为0，更改即可
		while(front!=rear)
		{
			++front;
			q=que[front].p;
			Lno=que[front].lno;	//Lno用来存储当前节点的层次号
			if(q->lchild!=NULL)
			{
				++rear;
				que[rear].p=q->lchild;
				que[rear].lno=Lno+1;	//根据当前的层次号推知其孩子节点的层次号
			}
			if(q->rchild!=NULL)
			{
				++rear;
				que[rear].p=q->rchild;
				que[rear].lno=Lno+1;	//同理，根据当前层次号推测知道其孩子结点的层次号
			}
		}//注意，当循环结束的时候，Lno保存的是这棵二叉树的最大层数
		//然后找出来含有结点最多的层中的节点数目
		max=0;
		for(i=0;i<=Lno;++i)
		{
			n=0;
			for(j=1;j<=rear;++j)//注意此处，数组从1处开始存储，结束时，rear处有数据
			{
				if(que[j].lno==i)
				{
					++n;
				}
				if(max<n)
				{
					max=n;
				}
			}
		}
		return max;
	}
	else
	{
		return 0;	//如果是空树，则返回0
	}
}

待检测的二叉树

测试程序完整源码

#include<iostream>
using namespace std;
typedef char mytype;

#define maxSize 10000	//给这个队列尽可能大的空间

//二叉树链表结点
typedef struct BTNode{
	struct BTNode *lchild;
	struct BTNode *rchild;
	char data;	
}BTNode;

//定义特殊的结构型，用于存储结点指针以及指针所在的层次号
typedef struct St
{
	BTNode *p;	//结点指针
	int lno;	//结点所在层次号
}St;

//构造二叉树
BTNode *createbinarytree()	//利用递归思想构造二叉树
{
	char element;
	cin>>element;	//输入二叉树的根节点的data值
	
	BTNode *T;
	if(element!='s')	//设置终止条件
	{
		T=(BTNode*)malloc(sizeof(BTNode));
		T->data=element;
		cout<<"please input the left child node of "<<element<<endl;
		T->lchild=createbinarytree();
		cout<<"please input the right child node of "<<element<<endl;
		T->rchild=createbinarytree();
	}
	else
	{
		T=NULL;
	}
	return T;
}



int maxNode(BTNode *b)	//求该二叉树的宽度,也就是二叉树中最大的度
{
	St que[maxSize];
	int front,rear;	//定义顺序非循环队列
	int Lno=0,i,j,n,max=0;
	front=0,rear=0;	//队头队尾为零，把队列置空
	BTNode *q;
	if(b!=NULL)
	{
		++rear;
		que[rear].p=b;	//二叉树的根入队
		que[rear].lno=1;	//树根所在的层次号设为1；若题中指定第一层层号为0，更改即可
		while(front!=rear)
		{
			++front;
			q=que[front].p;
			Lno=que[front].lno;	//Lno用来存储当前节点的层次号
			if(q->lchild!=NULL)
			{
				++rear;
				que[rear].p=q->lchild;
				que[rear].lno=Lno+1;	//根据当前的层次号推知其孩子节点的层次号
			}
			if(q->rchild!=NULL)
			{
				++rear;
				que[rear].p=q->rchild;
				que[rear].lno=Lno+1;	//同理，根据当前层次号推测知道其孩子结点的层次号
			}
		}//注意，当循环结束的时候，Lno保存的是这棵二叉树的最大层数
		//然后找出来含有结点最多的层中的节点数目
		max=0;
		for(i=0;i<=Lno;++i)
		{
			n=0;
			for(j=1;j<=rear;++j)//注意此处，数组从1处开始存储，结束时，rear处有数据
			{
				if(que[j].lno==i)
				{
					++n;
				}
				if(max<n)
				{
					max=n;
				}
			}
		}
		return max;
	}
	else
	{
		return 0;	//如果是空树，则返回0
	}
}


int main()
{
	
	BTNode *T;
	int k;
	T=createbinarytree();
	
	cout<<"the tree's biggest width is "<<maxNode(T)<<endl;
	
	return 0;
}

测试结果为4，正确！