求二叉树的宽度?
求二叉树的宽度?
给出详细的步骤, 并给出注解...
[解决办法]
#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;
}//算法结束
