2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库(17)

19．编写算法，求二叉树的宽度。

【答案】算法如下： int Width （BiTree bt）

//求二叉树bt的最大宽度

//空二叉树宽度为0

{if（bt==null）return （0）;

BiTree Q[]; //Q是队列，元素为二叉树结点指针，容量足够大 front=l;rear=l; //front为队头指针，rear为队尾指针 last=l;

//last为同层最右结点在队列中的位置

temp=0; maxw=0; //temp记当前层宽度，maxw记最大宽度 Q[rear]=bt; //根结点入队 while（front<=last）

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

if（p->lchild!=rull） Q[++rear]=p->lchild; //左子女入队 if（p->rchild!=null） Q[++rear]=p->rchild; //右子女入队 if（front>last） //—层结束 {last=rear;

//last指向下层最右元素

If（temp>maxw） maxw=temp;//更新当前最大宽度 temp=0; }//if}//while

return （maxw）; }//结束 Width

20．设求按

是一个记录构成的数组，

是一个整数数组，其值介于1～100之间，现要

时，则要求将

的内容调整到

中

的内容调整A中记录的次序，比如当

去。规定可使用的附加空间为

【答案】算法如下：

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库(17)在线全文阅读。