X
跨考考研 搜一搜
跨考考研
跨考考研
跨考考研
跨考考研
数据结构第六章算法设计题[13]_跨考网
跨考考研2011-11-25
来源跨考网整理
跨考考研

         1.对于二叉树的链接实现,完成非递归的中序遍历过程。 中山大学 1999 五、 (15)

  类似本题的另外叙述有:

  (1)写出中序遍历二叉树的非递归算法及递推算法。【大连海事大学1996 六、2 10)】。

  (2)设计一个中序遍历算法,应用栈来存储树结点,要求结点仅能进栈和出栈一次。(本题指中序遍历二叉树)【西安电子科技大学1999计应用 (10)

  (3)用非递归方式写出二叉树中序遍历算法。【山东科技大学 2002 六、2 (9)

  【参考答案】

  void InOrder(BiTree bt)

  {BiTree s[],p=bt; //s是元素为二叉树结点指针的栈,容量足够大

  int top=0;

  while(p || top>0)

  {while(p) {s[++top]=p; bt=p->lchild;} //中序遍历左子树

  if(top>0){p=s[top--]; printf(p->data); p=p->rchild;} //退栈,访问,转右子树

} }

2.试给出二叉树的自下而上、自右而左的层次遍历算法。【吉林大学 2001 2 8)

  【参考答案】

  [题目分析] 借助队列和栈,最后弹出栈中元素实现对二叉树按自下至上,自右至左的层次遍历

  void InvertLevel(biTree bt) // 对二叉树按自下至上,自右至左的进行层次遍历

  {if(bt!=null)

  {StackInit(s); //栈初始化,栈中存放二叉树结点的指针

  QueueInit(Q); //队列初始化。队列中存放二叉树结点的指针

  QueueIn(Q,bt);

  while(!QueueEmpty(Q)) //从上而下层次遍历

  {p=QueueOut(Q); push(s,p); //出队, 入栈

  if(p->lchild) QueueIn(Q,p->lchild); //若左子女不空,则入队列

  if(p->rchild) QueueIn(Q,p->rchild);} //若右子女不空,则入队列

  while(!StackEmpty(s)) {p=pop(s); printf(p->data);} //自下而上,从右到左的层次遍历

  }//if(bt!=null)

  } //结束InvertLevel

  

  3.在一棵以二叉链表表示的二叉树上,试写出用按层次顺序遍历二叉树的方法,统计树中具有度为1的结点数目的算法。二叉链表的类型定义为:

  TYPE bitreptr=^bnodetp;

  bnodetp=RECORD data:char; lchild,rchild:bitreptr END; 同济大学 2000 三、2 12分)】

  【参考答案】

  int Level(BiTree bt) //层次遍历二叉树,并统计度为1的结点的个数

  {int num=0; //num统计度为1的结点的个数

  if(bt){QueueInit(Q); QueueIn(Q,bt)//Q是以二叉树结点指针为元素的队列

  while(!QueueEmpty(Q))

  {p=QueueOut(Q); printf(p->data); //出队,访问结点

  if(p->lchild && !p->rchild ||!p->lchild && p->rchild)num++;//度为1的结点

  if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入队

  if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入队

  } }//if(bt)

  return(num); }//返回度为1的结点的个数

查看更多

  2022考研初复试已经接近尾声,考研学子全面进入2023届备考,跨考为23考研的考生准备了10大课包全程准备、全年复习备考计划、目标院校专业辅导、全真复试模拟练习和全程针对性指导;2023考研的小伙伴针也已经开始择校和复习了,跨考考研畅学5.0版本全新升级,无论你在校在家都可以更自如的完成你的考研复习,暑假集训营带来了院校专业初步选择,明确方向;考研备考全年规划,核心知识点入门;个性化制定备考方案,助你赢在起跑线,早出发一点离成功就更近一点!

点击右侧咨询或直接前往了解更多

考研院校专业选择和考研复习计划
2023备考学习 2023线上线下随时学习 34所自划线院校考研复试分数线汇总
2022考研复试最全信息整理 全国各招生院校考研复试分数线汇总
2023全日制封闭训练 全国各招生院校考研调剂信息汇总
2023考研先知 考研考试科目有哪些? 如何正确看待考研分数线?
不同院校相同专业如何选择更适合自己的 从就业说考研如何择专业?
手把手教你如何选专业? 高校研究生教育各学科门类排行榜

当前位置: 首页> 频道> 考研报名> 正文
考研报名相关栏目
跨考考研
考研热点
推荐阅读
推荐课程
跨考考研
2022全年魔鬼集训营二期
跨考考研开班时间:2021.4.20
在线咨询跨考考研
跨考考研
2022大三抢先学
跨考考研开班时间:每月20日
在线咨询跨考考研
Copyright©2008-2020 北京尚学硕博教育咨询有限公司
公司地址:北京市西城区宣武门庄胜广场中央办公楼南翼19层
客服电话:400-833-2220
跨考考研