数据结构考研分类复习真题 第六章 答案 (五)[10]

．[题目分析] 求二叉树高度的算法见上题求最大宽度可采用层次遍历的方法记下各层结点数每层遍历完毕若结点数大于原先最大宽度则修改最大宽度

int Width(BiTree bt)//求二叉树bt的最大宽度

{if (bt==null) return (); //空二叉树宽度为

else

{BiTree Q[];//Q是队列元素为二叉树结点指针容量足够大

front=;rear=;last=;//front队头指针rear队尾指针last同层最右结点在队列中的位置

temp=; maxw=; //temp记局部宽度 maxw记最大宽度

Q[rear]=bt; //根结点入队列

while(front<=last)

{p=Q[front++]; temp++; //同层元素数加

if (p>lchild!=null) Q[++rear]=p>lchild; //左子女入队

if (p>rchild!=null) Q[++rear]=p>rchild; //右子女入队

if (front>last) //一层结束

{last=rear;

if(temp>maxw) maxw=temp;//last指向下层最右元素 更新当前最大宽度

temp=;

}//if

}//while

return (maxw);

}//结束width

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []