2021计算机考研复习:二叉树

2021计算机考研复习:二叉树


   2021计算机考研复习:二叉树  一年之计在于春,4月份,大家都要开始进行2020考研复习了。在家上课之余,不…

2021计算机考研复习:二叉树

   2021计算机考研复习:二叉树

  一年之计在于春,4月份,大家都要开始进行2020考研复习了。在家上课之余,不要忘记2021考研复习哦!考研小编为大家带来了2021计算机考研复习:二叉树,一起看看吧。

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

  下面为大家介绍一下二叉树的几种遍历方法:

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

  1.先序遍历

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

  (1)访问根节点;

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

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

  2.中序遍历

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

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

  (2)访问根节点;

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

  3.后序遍历

  后序遍历的递归过程为:若二叉树为空,遍历结束。否则,同济大学四平路

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

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

  (3)访问根节点。

  层次遍历

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  大家要重点掌握这些以遍历为基础的二叉树算法题目,这就要求大家多做练习,通过习题训练加深理解,掌握解题思路和技巧,提高解题能力。

  以上就是2021计算机考研复习:二叉树。更多2021计算机考研复习知识点,持续更新中。


2021计算机考研复习:二叉树

    关于作者: admin

    这里可以再内容模板定义一些文字和说明,也可以调用对应作者的简介!或者做一些网站的描述之类的文字活着HTML!

    为您推荐

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注

    评论列表 人参与

    联系我们

    联系我们

    8888-88888888

    在线咨询: QQ交谈

    邮箱: email@admin.com

    工作时间:周一至周五,9:00-17:30,节假日休息

    关注微信
    微信扫一扫关注我们

    微信扫一扫关注我们

    关注微博
    返回顶部