最新[2017计算机考研数据结构要点：二叉树]数据结构与算法java版.doc

《最新[2017计算机考研数据结构要点：二叉树]数据结构与算法java版.doc》由会员分享，可在线阅读，更多相关《最新[2017计算机考研数据结构要点：二叉树]数据结构与算法java版.doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最新2017计算机考研数据结构要点：二叉树数据结构与算法java版考研网权威发布2017计算机考研数据结构要点：二叉树，更多2017计算机考研数据结构要点相关信息请访问考研网。相关推荐： >>>2017年考研现场确认时间及地点汇总 >>>全国各地2017年考研报考点汇总 >>>2017年考研时间、研究生考试时间安排 >>>2017年考研大纲下载及解析汇总 >>>2017年全国硕士研究生招生简章专题 新东方网校推荐：2017年考研政治、英语、数学一次课程！点击进入免费试听>> 下面为大家介绍一下

2、二叉树的几种遍历方法：由二叉树的定义可知，一颗二叉树由根节点及左、右子树三个基本部分组成，因此，只要依次遍历这三部分，就可以遍历整个二叉树。1.先序遍历先序遍历的递归过程为：若二叉树为空，遍历结束。否则，(1)访问根节点;(2)先序遍历根节点的左子树;(3)先序遍历根节点的右子树。2.中序遍历中序遍历的递归过程为：若二叉树为空，遍历结束。否则，(1)中序遍历根节点的左子树;(2)访问根节点;(3)中序遍历根节点的右子树。3.后序遍历后序遍历的递归过程为：若二叉树为空，遍历结束。否则，同济大学四平路(1)后序遍历根节点的左子树;(2)后序遍历根节点的右子树;(3)访问根节点。层次遍历二叉树的层次

3、遍历，是指从二叉树的第一层(根结点)开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。在进行层次遍历时，对一层结点访问完后，再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先访问，这与队列的操作原则比较吻合。因此，在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取一个元素，执行下面两个操作：(1)访问该元素所指结点;(2)若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。下面大家来

4、看二叉树遍历这部分在考试中常考题型1.由二叉树的两个遍历序列的组合(先序序列和中序序列)、(中序序列和后序序列)、(层次序列和中序序列)构造该二叉树或求其他遍历序列是一种常见的题型。需要注意的是已知二叉树的先序序列和后序序列不能唯一确定该二叉树。2.以遍历为基础的二叉树算法设计是考试的重点和难点。常见的试题有以下几类：(1)基于二叉树遍历的递归算法这类题目的特点是直接根据三种递归算法改写，修改访问语句来实现。例如：求二叉树的结点个数。(2)基于二叉树层次遍历的算法这类题目有求二叉树的高度，求二叉树最大宽度等。(3)基于顺序存储的二叉树遍历算法例如：求顺序存储的满二叉树中序遍历的非递归算法。(4)其他二叉树遍历算法例如：左、右子树交换等。大家要重点掌握这些以遍历为基础的二叉树算法题目，这就要求大家多做练习，通过习题训练加深理解，掌握解题思路和技巧，提高解题能力。另外，现在大家开始冲刺复习了，选择一本涵盖全面、与真题题型一致、题目难度和真题难度高度相近，并对这两年的考试试题进行了详细分析的全真模拟试题集，是此时冲刺的最佳帮手，可以帮助你查缺补漏，显著提高应试能力。第 3 页 共 3 页