考研网,考研考生的精神家园。祝大家考研成功 梦想成真!
注册 | 登陆 | 注销 | 会员中心 | 网站公告 |
您现在的位置: 教育频道-新都网 >> 考研 >> 考研专业课 >> 计算机学科专业基础综合 >> 正文

考研计算机专业超越130冲刺讲解——二叉树

作者:佚名    文章来源:文都教育    点击数:    更新时间:2010/12/9

    二叉树是数据结构中的重点内容,在这两年的考试中也将二叉树作为重点内容来考查。二叉树这部分内容要求大家掌握二叉树的定义、性质、存储结构、遍历、线索化、森林和二叉树的转换等内容。算法的重点是二叉树的遍历及其应用,这也是二叉树这部分的重点和难点。遍历是二叉树各种操作的基础,可以在遍历过程中对结点进行各种操作。例如:求二叉树结点总数,建立二叉树,建立二叉树的存储结构等。二叉树的很多算法是在遍历算法基础上改造完成的,这就要求大家在复习时,熟练掌握二叉树遍历的递归和非递归算法。
    下面,介绍一下二叉树的几种遍历方法:
    由二叉树的定义可知,一颗二叉树由根节点及左、右子树三个基本部分组成,因此,只要依次遍历这三部分,就可以遍历整个二叉树。
    1.先序遍历
    先序遍历的递归过程为:若二叉树为空,遍历结束。否则,
    (1)访问根节点;
    (2)先序遍历根节点的左子树;
    (3)先序遍历根节点的右子树。
    2.中序遍历
    中序遍历的递归过程为:若二叉树为空,遍历结束。否则,
    (1)中序遍历根节点的左子树;
    (2)访问根节点;
    (3)中序遍历根节点的右子树。
    3.后序遍历
    后序遍历的递归过程为:若二叉树为空,遍历结束。否则,
    (1)后序遍历根节点的左子树;
    (2)后序遍历根节点的右子树;
    (3)访问根节点。
    层次遍历
    二叉树的层次遍历,是指从二叉树的第一层(根结点)开始,从上至下逐层遍历,在同一层中,则按从左到右的顺序对结点逐个访问。在进行层次遍历时,对一层结点访问完后,再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问,这样一层一层进行,先遇到的结点先访问,这与队列的操作原则比较吻合。因此,在进行层次遍历时,可设置一个队列结构,遍历从二叉树的根结点开始,首先将根结点指针入队列,然后从对头取出一个元素,每取一个元素,执行下面两个操作:
    (1)访问该元素所指结点;
    (2)若该元素所指结点的左、右孩子结点非空,则将该元素所指结点的左孩子指针和右孩子指针顺序入队。
    此过程不断进行,当队列为空时,二叉树的层次遍历结束。
    这部分相关算法以及二叉树遍历的非递归算法在《计算机学科专业基础综合辅导讲义》中有详细讲解,大家如果对这部分内容还有疑问,可以查阅《计算机学科专业基础综合辅导讲义》,一定要把这些基础内容搞清楚。
    下面大家来看二叉树遍历这部分在考试中常考题型
    1.由二叉树的两个遍历序列的组合(先序序列和中序序列)、(中序序列和后序序列)、(层次序列和中序序列)构造该二叉树或求其他遍历序列是一种常见的题型。需要注意的是已知二叉树的先序序列和后序序列不能唯一确定该二叉树。
    2.以遍历为基础的二叉树算法设计是考试的重点和难点。常见的试题有以下几类:
    (1)基于二叉树遍历的递归算法
    这类题目的特点是直接根据三种递归算法改写,修改访问语句来实现。例如:求二叉树的结点个数。
    (2)基于二叉树层次遍历的算法
    这类题目有求二叉树的高度,求二叉树最大宽度等。
    (3)基于顺序存储的二叉树遍历算法
    例如:求顺序存储的满二叉树中序遍历的非递归算法。
    (4)其他二叉树遍历算法
    例如:左、右子树交换等。
    大家要重点掌握这些以遍历为基础的二叉树算法题目,这就要求大家多做练习,通过习题训练加深理解,掌握解题思路和技巧,提高解题能力。针对以上几种算法题,大家可通过计算机学科专业基础综合辅导讲义同步练习来准备相应的练习题并配有详细的解答,掌握此部分内容。
    另外,现在大家开始冲刺复习了,选择一本涵盖全面、与真题题型一致、题目难度和真题难度高度相近,并对这两年的考试试题进行了详细分析的全真模拟试题集,是此时冲刺的最佳帮手,可以帮助你查缺补漏,显著提高应试能力。

(责任编辑:admin)


查看更多关于考研专业课的文章
快速导航
培训信息
特别说明
    由于各方面情况的不断调整与变化,新都教育所提供的招生和考试信息仅供参考,敬请考生以权威部门公布的正式信息为准。
版权声明
    凡本网注明“来源:新都教育”的所有作品,版权均属于新都网,未经本网授权不得转载、摘编或利用其它方式使用上述作品。已经本网授权使用作品的,应在授权范围内使用,并注明“来源:新都教育”。违反上述声明者,本网将追究其相关法律责任。
  凡本网注明“来源:XXXXX(非新都教育)”的作品,均转载自其它媒体,转载目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。
  如作品内容、版权等存在问题,请在两周内同本网联系,联系邮箱:newdu2004@tom.com
  本网欢迎原创作品投稿,投稿邮箱:newdu2004@tom.com
  • 考研栏目导航
  • 招考资讯
    考试新闻
    招生简章
    考试大纲
    考研政策
    分数线及成绩
    录取调剂
    院校信息
    专业介绍
    综合新闻
    公告通知
    考研政治
    政治指导
    马克思主义基本原理概论
    毛泽东思想和社会主义理论
    中国近现代史纲要
    思想道德修养与法律基础
    形势与政策以及当代世界经济与政治
    历年真题
    模拟试题
    专项训练
    考研英语
    英语指导
    英语知识运用
    阅读理解
    写作
    历年真题
    模拟试题
    专项训练
    考研数学
    数学指导
    高等数学
    线性代数
    概率论与数理统计
    历年真题
    模拟试题
    专项训练
    考研专业课
    综合指导
    计算机学科专业基础综合
    植物生理学与生物化学
    动物生理学与生物化学
    教育学专业基础综合
    心理学专业基础综合
    管理类联考综合能力
    法硕联考专业基础
    法硕联考综合
    历史学基础
    西医综合
    中医综合
    化学
    日语
    俄语
    其它专业课
    历年真题
    模拟试题
    专项训练
    考研复试
    综合辅导
    综合辅导
    真题解读
    专家访谈
    专家解读
    备考经验
    经验技巧
    考研故事
    综合辅导
    考研网,考研门户网站,提供考研院校信息,考研论坛,报考指南,招生简章,复习资料,专业试卷,考研题库,考研政治,考研英语,考研数学,考研分数,考研调剂,考研经验,考研心情等考研信息。
    Copyright © 2004-2009 Newdu.com All Rights Reserved 京ICP备09058993号
    本站为非经营性网站,收藏资料纯属个人爱好,若有问题请联系管理员:newdu2004@tom.com