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

1.已知一具有n个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组IN[1n]POST[1n]中,(设该二叉树各结点的数据值均不相同)。请写一建立该二叉树的二叉链表结构的非递归算法。该二叉链表的链结点结构为(lchild,data,rchild),其中data为数据域,lchildrhild分别为指向该结点左、右孩子的指针域(当孩子结点不存在时,相应指针域为空,用nil表示)。【北京航空航天大学 1998 (15)
  【参考答案】
  [题目分析]知二叉树中序序列与后序序列,第30题以递归算法建立了二叉树,本题是非递归算法。
  void InPostCreat(ElemType IN[],POST[],int l1,h1,l2,h2)
  //由二叉树的中序序列IN[]和后序序列POST[]建立二叉树,l1,h1l2,h2分别是中序序列和

  //后序序列第一和最后元素的下标,初始调用时,l1=l2=1,h1=h2=n
  {typedef struct {int l1,h1,l2,h2; BiTree t; }node;
  node s[],p;//s为栈,容量足够大

  BiTree bt=(BiTree)malloc(sizeof(BiNode)); int top=0,i;
  p.l1=l1; p.h1=h1; p.l2=l2; p.h2=h2; p.t=bt; s[++top]=p;//初始化

  while(top>0)
  {p=s[top--]; bt=p.t; l1=p.l1; h1=p.h1; l2=p.l2; h2=p.h2;//取出栈顶数据

  for(i=l1;i<=h1;i++) if(IN[i]==POST[h2]) break;//在中序序列中查等于POST[h2]的结点
  bt->data=POST[h2]; //根结点的值
  if(i==l1) bt->lchild=null; //bt无左子树
  else //将建立左子树的数据入栈
  {bt->lchild=(BiTree)malloc(sizeof(BiNode)); p.t=bt->lchild;
  
p.l1=l1; p.h1=i-1; p.l2=l2; p.h2=l2+i-l1-1; s[++top]=p; }
  if(i==h1) bt->rchild=null; //bt无右子树

  else {bt->rchild=(BiTree)malloc(sizeof(BiNode)); p.t=bt->rchild;
  p.l1=i+1; p.h1=h1; p.l2=l2+i-l1; p.h2=h2-1; s[++top]=p; }//右子树数据入栈

  }// while(top>0)
  }结束InPostCreat

查看更多

  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
跨考考研