[计算机考研只考数据结构的学校]2017计算机考研数据结构要点:二叉树

副标题:2017计算机考研数据结构要点:二叉树

时间:2023-05-21 06:14:01 阅读: 最新文章 文档下载
说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

相关推荐:

>>>2017年考研现场确认时间及地点汇总

>>>全国各地2017年考研报考点汇总

>>>2017年考研时间、研究生考试时间安排

>>>2017年考研大纲下载及解析汇总

>>>2017年全国硕士研究生招生简章专题

新东方网校推荐:2017年考研政治、英语数学课程!!点击进入免费试听>>


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

2017计算机考研数据结构要点:二叉树.doc

本文来源:https://www.wddqw.com/qUXx.html