考研报名

数据结构第六章算法设计题[7]_跨考网

来源:跨考2011-11-25

1.二叉树采用二叉链表存储:

  (1)编写计算整个二叉树高度的算法(二叉树的高度也叫二叉树的深度)。

  (2)编写计算二叉树最大宽度的算法(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。【西北大学 2001 四】

  【参考答案】

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

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

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

  else

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

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

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

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

  while(front<=last)

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

  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=0;

  }//if

  }//while

  return (maxw);

  }//结束width

展开全文
频道>考研报名

近期热点

相关推荐

大家都在看

2022考研门类之:教育学门类考研院校排名

2022考研门类之:法学门类考研院校排名

2022考研门类之:经济学门类考研院校排名

2022考研门类之:哲学门类考研院校排名

2022考研择专业:相对热门的交叉学科

22考研:交叉学科可能成为新选择!它有哪些优势?

2022考研门类重大改革!增设“交叉学科”新门类!

跨考分校

加盟