求二叉树的宽度的程序

发布网友发布时间：2022-04-24 10:03

共2个回答

热心网友时间：2023-04-25 04:03

要求二叉树的宽度的话，则可根据树的高度设置一个数组temp。temp[i]用于存放第i层上的结点数(即宽度)。在访问结点时,把相应计算该结点下一层的孩子数并存入相应数组元素中，遍历左子树后向上返回一层计算右子树的宽度，并取出最大的一个数组元素作为树的宽度。

#define M 10 //假设二叉树最多的层数
int Width(BinTree T)
{
int static n[M];//向量存放各层结点数
int static i=1;
int static max=0;//最大宽度
if(T)
{
if(i==1) //若是访问根结点
{
n[i]++; //第1层加1
i++; //到第2层
if(T->lchild)//若有左孩子则该层加1
n[i]++;
if(T->rchild)//若有右孩子则该层加1
n[i]++;
}
else
{ //访问子树结点
i++; //下一层结点数
if(T->lchild)
n[i]++;
if(T->rchild)
n[i]++;
}
if(max<n[i])max=n[i];//取出最大值
Width(T->lchild);//遍历左子树
i--; //往上退一层
Width(T->rchild);//遍历右子树
}
return max;
}//算法结束

希望可以给你帮助！

热心网友时间：2023-04-25 04:04

就是按层次遍历，在每层里判断一个该层的结点值
代码很简单，修改一下层次遍历的代码就好了