网站通行证  
天津考研网 资讯中心-网尽考研信息 考研专卖店-考研资料书籍一站购齐 考研辅导班 BBS社区-便易的交流平台 专业课教材 院校导航-权威院校招生信息 下载中心-海量考研复习资料 客服中心-解决所有问题 考研热线4000220908
 您现在的位置: 天津考研网 >> 资讯中心 >> 全国统考科目 >> 计算机考研 >> 正文 相信自己,加油!
    考研计算机:数据结构知识点分析讲解
考研计算机:数据结构知识点分析讲解
责任编辑:teng91  作者:佚名  来源:转自网络   更新时间:2013-6-4 9:45:01

  二叉树是数据结构中的重点内容,在这两年的考试中也将二叉树作为重点内容来考查。二叉树这部分内容要求大家掌握二叉树的定义、性质、存储结构、遍历、线索化、森林和二叉树的转换等内容。算法的重点是二叉树的遍历及其应用,这也是二叉树这部分的重点和难点。遍历是二叉树各种操作的基础,可以在遍历过程中对结点进行各种操作。例如:求二叉树结点总数,建立二叉树,建立二叉树的存储结构等。二叉树的很多算法是在遍历算法基础上改造完成的,这就要求大家在复习时,熟练掌握二叉树遍历的递归和非递归算法。

  下面,我们介绍一下二叉树的几种遍历方法:

  由二叉树的定义可知,一颗二叉树由根节点及左、右子树三个基本部分组成,因此,只要依次遍历这三部分,就可以遍历整个二叉树。

  1.先序遍历

  先序遍历的递归过程为:若二叉树为空,遍历结束。否则,

  (1)访问根节点;

  (2)先序遍历根节点的左子树;

  (3)先序遍历根节点的右子树。

  2.中序遍历

  中序遍历的递归过程为:若二叉树为空,遍历结束。否则,

  (1)中序遍历根节点的左子树;

  (2)访问根节点;

  (3)中序遍历根节点的右子树。

  3.后序遍历

  后序遍历的递归过程为:若二叉树为空,遍历结束。否则,

  (1)后序遍历根节点的左子树;

  (2)后序遍历根节点的右子树;

  (3)访问根节点。

  层次遍历

  二叉树的层次遍历,是指从二叉树的第一层(根结点)开始,从上至下逐层遍历,在同一层中,则按从左到右的顺序对结点逐个访问。在进行层次遍历时,对一层结点访问完后,再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问,这样一层一层进行,先遇到的结点先访问,这与队列的操作原则比较吻合。因此,在进行层次遍历时,可设置一个队列结构,遍历从二叉树的根结点开始,首先将根结点指针入队列,然后从对头取出一个元素,每取一个元素,执行下面两个操作:

  (1)访问该元素所指结点;

  (2)若该元素所指结点的左、右孩子结点非空,则将该元素所指结点的左孩子指针和右孩子指针顺序入队。

  此过程不断进行,当队列为空时,二叉树的层次遍历结束。

  这部分相关算法以及二叉树遍历的非递归算法在《计算机学科专业基础综合辅导讲义》中有详细讲解,大家如果对这部分内容还有疑问,可以查阅《计算机学科专业基础综合辅导讲义》,一定要把这些基础内容搞清楚。

  下面大家来看二叉树遍历这部分在考试中常考题型

  1.由二叉树的两个遍历序列的组合(先序序列和中序序列)、(中序序列和后序序列)、(层次序列和中序序列)构造该二叉树或求其他遍历序列是一种常见的题型。需要注意的是已知二叉树的先序序列和后序序列不能唯一确定该二叉树。

  2.以遍历为基础的二叉树算法设计是考试的重点和难点。常见的试题有以下几类:

  (1)基于二叉树遍历的递归算法

  这类题目的特点是直接根据三种递归算法改写,修改访问语句来实现。例如:求二叉树的结点个数。

  (2)基于二叉树层次遍历的算法

  这类题目有求二叉树的高度,求二叉树最大宽度等。

  (3)基于顺序存储的二叉树遍历算法

  例如:求顺序存储的满二叉树中序遍历的非递归算法。

  (4)其他二叉树遍历算法

  例如:左、右子树交换等。

  大家要重点掌握这些以遍历为基础的二叉树算法题目,这就要求大家多做练习,通过习题训练加深理解,掌握解题思路和技巧,提高解题能力。针对以上几种算法题,大家可通过计算机学科专业基础综合辅导讲义同步练习来准备相应的练习题并配有详细的解答,掌握此部分内容。

  另外,现在大家开始冲刺复习了,选择一本涵盖全面、与真题题型一致、题目难度和真题难度高度相近,并对这两年的考试试题进行了详细分析的全真模拟试题集,是此时冲刺的最佳帮手,可以帮助你查缺补漏,显著提高应试能力。

分享到:
复制本文地址给好友 -
  • 上一篇文章:

  • 下一篇文章:
  • 发表评论】【加入收藏】【告诉好友】【打印此文】【关闭窗口】 
    文章搜索
    天津考研网版权、投稿与免责申明:
    1)凡本网署名文字、图片和音视频稿件,版权均属天津考研网所有。任何媒体、网站或个人未经本网协议授权不得转载、链接、转贴或以其他方式复制发表。已经本网协议授权的媒体、网站,在下载使用时必须注明稿件来源:天津考研网,违者本网将依法追究责任。
    2)本网注明"来源:转自网络"的文章均为转载稿,本网转载出于传递更多信息之目的。此类稿件并不代表本网观点,本网不承担此类稿件侵权行为的直接责任及连带责任。
    3. 如因作品内容、版权等需要同本网联系的,请在作品在本网发表之日起30日内联系,否则视为放弃相关权利。
      热门考研服务
      最新考研信息
      相关文章
    2023年考研复试分数线国家线
    天津地区考研成绩预计2021年2月26日公布
    考研报名确认结束 全国16057人报考南开
    天津市教育招生考试院致2021年在津参加研考考生的
    如何快速掌握导师论文?复试,讨好导师的“人情秘
    复试真的有黑幕吗?黑在哪里?
    341万“考研大军”,他们为何考研?
    考研-考试流程揭秘,脑补一下,提前进入状态!
    今年考研人数比去年增加了50万!史上最难留学年到
    【2020考研冲刺】考研复习冲刺,如何克服进度不前
      热卖考研资料
    资讯栏目导航
    新闻政策 考研新闻 考研政策 热点点评
    复习指导 英语 数学 政治 专业课 分数线 大纲 复试
    经验心得 经验交流 考研故事
    院校导航 天津大学 天津医科大学 天津师范大学
    南开大学 天津财经大学 河北工业大学
    天津工业大学 中国民航大学 天津外国语大学
    天津理工大学 天津科技大学 天津商业大学
    天津中医药大学 天津城市建设学院 其他
    统考科目 心理学考研 教育学考研 历史学考研
    计算机考研 医学考研网 法律硕士 农学
    热门专业 会计学 行政管理 土木建筑 化学 机械 法学
    自动化 新闻传播 人力资源 生物 电气 中文
    管理学 电子通信 国际关系 外语 经济 社保
    | 关于我们 | 网站导航 | 招聘信息 | 广告业务 | 隐私条款 | 客服中心 | 联系我们设为首页 顶部 全国统一热线:022-58054788,58054799,27056088
    版权所有 Copyright©2003-2024 天津格瑞斯教育科技有限公司 All Rights Reserved 旗下网站:[天津考研网]52kaoyan.com上学网]chinakao.cn
    公司地址:天津市和平区卫津路佳怡国际D座底商(天津大学东门斜对过) -办公室地图-行车路线 工商网银在线支付平台,安全快捷!支付宝特约商家,信任标志!考研一站式服务,考研无忧!
    公司总机:022-85681642 客服热线:022-58054788,58054799(7X24小时热线支持)
    法律顾问:王自强律师 信息产业部备案:津ICP备07001356号-3