è 图1-15二叉链表的逻辑状态 1.6.4二叉树的遍历 二叉树的遍历是指不重复的访问二叉树中的所有结点： 由于 一种非线性结构，因此对 叉树的遍历要比遍历线性表复杂很多。在遍历 又对过程中，当访问到某个结点时，再往下访问可能有两个分支，应访向一不如 对于二叉树来说需要访问根结点、左子树所有结点、右子树所有结点，在这三者中，应访问 哪一个？也就是说，遍历二叉树实际是要确定访问各结点的顺序。以便不重复又不能丢掉访 问结点，直到访问到所有结点。 在遍历二叉树的过程中 一般选遍历左子树，然后再遍历右子树，在先左后右原则下 据访问结点次序，二叉树的遍历分为三种方法：前序遍历、中序遍历和后序遍历。 1.前序遍历(DLR) 前序遍历首先访问根结点，然后遍历左子树，最后遍历右子树。在遍历左、右子树时， 仍然先访问根结点，然后遍历左子树，最后遍历右子树。即： 若二叉树为空则结束返回，否则： (1)访问根结点 (2)前序遍历左子树 (3)前序追历右子树 注意：遍历左右子树时仍然采用前序遍历方法。 例：如图1-16二叉树， A c D HF 图1-16前序遍历 则前序遍历结果是：ABDEC F 2.中序遍历(LDR
21 图 1-15 二叉链表的逻辑状态 1.6.4 二叉树的遍历 二叉树的遍历是指不重复的访问二叉树中的所有结点。 由于二叉树是一种非线性结构，因此对二叉树的遍历要比遍历线性表复杂很多。在遍历 二叉树过程中，当访问到某个结点时，再往下访问可能有两个分支，应访问哪一个分支呢？ 对于二叉树来说需要访问根结点、左子树所有结点、右子树所有结点，在这三者中，应访问 哪一个？也就是说，遍历二叉树实际是要确定访问各结点的顺序。以便不重复又不能丢掉访 问结点，直到访问到所有结点。 在遍历二叉树的过程中，一般选遍历左子树，然后再遍历右子树，在先左后右原则下根 据访问结点次序，二叉树的遍历分为三种方法：前序遍历、中序遍历和后序遍历。 1. 前序遍历（DLR） 前序遍历首先访问根结点，然后遍历左子树，最后遍历右子树。在遍历左、右子树时， 仍然先访问根结点，然后遍历左子树，最后遍历右子树。即： 若二叉树为空则结束返回，否则： （1）访问根结点 （2）前序遍历左子树 （3）前序遍历右子树 注意：遍历左右子树时仍然采用前序遍历方法。 例：如图 1-16 二叉树， 图 1-16 前序遍历 则前序遍历结果是：A B D E C F 2. 中序遍历（LDR） A F C D E B A B C D E
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时， 仍然先追历左子树，再访问根结点，最后遍历右子树。即： 若 又树为空则结束返国，否则 (1)中序远历左子树 (2)访问根结点 (3)中序遍历右子树。 注意：遍历左右子树时仍然采用中序遍历方法 例：如图1-17二又树， c D E 图1-17中序遍历 则中序遍历结果是：DBEAFC 3.后序遍历(LRD) 后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时， 仍然先遍历左子树，然后遍历右子树，最后访问根结点。即： 若二叉树为空则结束返回，否则： (1)后序遍历左子树， (2)后序遍历右子树 (3)最后访问根结点。 注意：遍历左右子树时仍然采用后序遍历方法。 例：如图1-18二叉树， A c D 包 图1-18前序遍历 则中序遍历结果是：DEBFCA
22 中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时， 仍然先遍历左子树，再访问根结点，最后遍历右子树。即： 若二叉树为空则结束返回，否则： （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树。 注意：遍历左右子树时仍然采用中序遍历方法。 例：如图 1-17 二叉树， 图 1-17 中序遍历 则中序遍历结果是：D B E A F C 3. 后序遍历（LRD） 后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时， 仍然先遍历左子树，然后遍历右子树，最后访问根结点。即： 若二叉树为空则结束返回，否则： （1）后序遍历左子树， （2）后序遍历右子树 （3）最后访问根结点。 注意：遍历左右子树时仍然采用后序遍历方法。 例：如图 1-18 二叉树， 图 1-18 前序遍历 则中序遍历结果是：D E B F C A A F C D E B A F C D E B
1.7查找技术 个数处黄中的一个重要内家所查是指在一个定的据结的中 1.7.1顺序查找 顺序查找是从线性表的第一个元素开始，依次将线性表的元素与被查元素进行比较，若 相等则表示找到：若线性表中所有元素都与被查元素进行了比较都不相等，则表示线性表中 没有要找的元素。顺序查找适合无序表和使用链式存储结构的线性表。 1.7.2二分法查找 二分法查找只适用于顺序存储的有序表。对分查找方法如下：将被查元素与线性表的 中间项进行比较，若中间项值等于被查元素说明查到：若被查元素小于中间项的值，则在线 性表的前半部分以相同方法进行查找：若被查元素大于中间项的值，则在线性表的后半部分 以相同方法进行查找 1.8排序技术 排序是指将一个无序序列整理成有序序列（一般指升序，即非递减顺序）。 1.8.1交换类排序法 1、冒泡排序法 冒泡排序法的基本过程是：从线性表开头逐次比较相邻数据 元素的大小，若相邻两个 元素中，前面元素大于后面元换，则将它们交换。依次下去最后将最大元素换到了表的最后， 然后再从剩下的线性表中按上述方法进行操作，直到剩余下的线性表变空为止。此时线性表 已经变为有序。 2、快速排序法 快速排序法基本思想：从线性表中 近取 设为T,将线性表后面小于T的元 移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分，T插入到其分界 线的位置处，这个过程称为线性表的分割。通过对线性表一次分割，就以T为分界线，将线 性表分阶段成了两个子表，前面子表中所有元素均不大于T,后面的子表中所有元素均不小 于T。 对分制后的各子表再按上述原则进行分制，直到所有子表变空为止，则线性表就变成了 有序 快速排序法关键是对线性表进行分割，以及对各分割出的子表再进行分割
23 1.7 查找技术 查找是数据处理领域中的一个重要内容。所谓查找是指在一个给定的数据结构中查找某 个指定元素。 1.7.1 顺序查找 顺序查找是从线性表的第一个元素开始，依次将线性表的元素与被查元素进行比较，若 相等则表示找到；若线性表中所有元素都与被查元素进行了比较都不相等，则表示线性表中 没有要找的元素。顺序查找适合无序表和使用链式存储结构的线性表。 1.7.2 二分法查找 二分法查找只适用于顺序存储的有序表。对分查找方法如下：将被查元素与线性表的 中间项进行比较，若中间项值等于被查元素说明查到；若被查元素小于中间项的值，则在线 性表的前半部分以相同方法进行查找；若被查元素大于中间项的值，则在线性表的后半部分 以相同方法进行查找。 1.8 排序技术 排序是指将一个无序序列整理成有序序列(一般指升序，即非递减顺序)。 1.8.1 交换类排序法 1、冒泡排序法 冒泡排序法的基本过程是：从线性表开头逐次比较相邻数据元素的大小，若相邻两个 元素中，前面元素大于后面元换，则将它们交换。依次下去最后将最大元素换到了表的最后。 然后再从剩下的线性表中按上述方法进行操作，直到剩余下的线性表变空为止。此时线性表 已经变为有序。 2、快速排序法 快速排序法基本思想：从线性表中选取一个元素，设为 T，将线性表后面小于 T 的元素 移到前面，而前面大于 T 的元素移到后面，结果就将线性表分成了两部分，T 插入到其分界 线的位置处，这个过程称为线性表的分割。通过对线性表一次分割，就以 T 为分界线，将线 性表分阶段成了两个子表，前面子表中所有元素均不大于 T，后面的子表中所有元素均不小 于 T。 对分割后的各子表再按上述原则进行分割，直到所有子表变空为止，则线性表就变成了 有序表。 快速排序法关键是对线性表进行分割，以及对各分割出的子表再进行分割
1.8.2插入类排序法 1、简单插入排序法 插入排序是将无序序列中的各元素依次插入到已经有序的线性表中。插入过程是： 选将第j个元素放入一个变量T中，然后从有序子表的最后一个元素开始，往前逐个与T 比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为此，此时就 将T插入到刚移出的空位置上。 2、希尔排序法 希尔排序法基本思想是： 将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法是：将相 邻某个增量h的元素构成一个子序列。在排序过程中，逐次诚少这个增量，最后当减到1 时，进行一次插入排序。 增量序列一般取ht=m/2k(k=l,2,[1og2nJ),其中n为待排序序列的长度 1.8.3选择类排序法 1、简单选择排序法 选择排序法基本思想是：对整个线性表，从中选择出最小的的元素，将它交换到最前面， 然后对剩下的子表采用同样方法，直到子表空为止。 2、堆排序法 堆排序法属于选择类的排序方法。堆的定义如下 具有n个元素的序列(hl,h2,·,hn),当且仅当满足 hi)=h2i和hi>=h2i+1 hi<h2i和hi<=h2it1 (=1,2,.,/2)时称之为堆。这时只讨论前者堆。堆顶元素（第一个元素）必为最大 项。 在实际处理中，可以用一维数组来存储堆序列中元素，也可以用完全二叉树来直观表示 推的结构。如序列(91,85,53,36,47,30,24,12)是一个堆，它所对应的完全两叉树。 用完全二叉树表示堆时，树中所有非叶子结点均不小于其左、右子树的根结点值。如图1-19 所示。 91 85 53 36 4730 24 12 图1-19完全二又树表示堆
24 1.8.2 插入类排序法 1、 简单插入排序法 插入排序是将无序序列中的各元素依次插入到已经有序的线性表中。插入过程是： 选将第 j 个元素放入一个变量 T 中，然后从有序子表的最后一个元素开始，往前逐个与 T 比较，将大于 T 的元素均依次向后移动一个位置，直到发现一个元素不大于 T 为此，此时就 将 T 插入到刚移出的空位置上。 2、希尔排序法 希尔排序法基本思想是： 将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法是：将相 邻某个增量 h 的元素构成一个子序列。在排序过程中，逐次减少这个增量，最后当 h 减到 1 时，进行一次插入排序。 增量序列一般取 ht=n/2k(k=1,2,.,[log2n])，其中 n 为待排序序列的长度 1.8.3 选择类排序法 1、 简单选择排序法 选择排序法基本思想是：对整个线性表，从中选择出最小的的元素，将它交换到最前面， 然后对剩下的子表采用同样方法，直到子表空为止。 2、堆排序法 堆排序法属于选择类的排序方法。堆的定义如下： 具有 n 个元素的序列（h1, h2, . ,hn），当且仅当满足： hi>=h2i 和 hi>=h2i+1 hi<=h2i 和 hi<=h2i+1 (i=1, 2, .,n/2)时称之为堆。这时只讨论前者堆。堆顶元素（第一个元素）必为最大 项。 在实际处理中，可以用一维数组来存储堆序列中元素，也可以用完全二叉树来直观表示 堆的结构。如序列（91，85，53，36，47，30，24，12）是一个堆，它所对应的完全两叉树。 用完全二叉树表示堆时，树中所有非叶子结点均不小于其左、右子树的根结点值。如图 1-19 所示。 图 1-19 完全二叉树表示堆 91 30 24 53 12 36 47 85
在调整建堆过程中，总是将根结点值与左、右子树的根结点值进行比较，若不满足堆的 条件，则将左、右子树结点值中的大者与根结点进行交换。直到所有子树均为堆为 设无序序列H(1 :n)以完 从 二叉树的最后 个非 结点（即 第(/2个元素)开始，直到根结点（即第一个元素）为止，对每一个结点进行调整建堆， 最后就可以得到与该序列对应的堆。 如此得到堆的排序方法： (1)首失将一个无序序列建成堆 (2)然后将堆顶元素（序列中最大项）与堆中最后一个元素交换（最大项应该在序列 的最后)。 1.9本章小结 学习完本章之后要掌握以下内容： 1.算法的基本概念：算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2。数据结构的定义：数据的逻辑结构与存储结构：数据结构的图形表示：线性结构与 非线性结构的概念 3。线性表的定义：线性表的顺序存储结构及其插入与除运算 4.栈和队列的定义：栈和队列的顺序存储结构及其基本运算。 5.线性单链表、双向链表与循环链表的结构及其基本运算。 6.树的基本概念：二叉树的定义及其存储结构：二叉树的前序、中序和后序遍历。 7.顺序查找与二分法查找算法：基本排序算法（交换类排序，选择类排序，插入类排 序)。 习题1 一、选择题 1.栈和队列的共同特点是( ) A)都是先进先出 B)都是先进后出 C)只允许在端点处插入和删除元素 D)没有共同占 2.已知二叉树后序遍历序列是dabec,中序历序列是debac,它的前序遍历序列 A)acbed
25 在调整建堆过程中，总是将根结点值与左、右子树的根结点值进行比较，若不满足堆的 条件，则将左、右子树结点值中的大者与根结点进行交换。直到所有子树均为堆为止。 设无序序列 H（1：n）以完全二叉树表示，从完全二叉树的最后一个非叶子子结点（即 第（n/2 个元素）开始，直到根结点（即第一个元素）为止，对每一个结点进行调整建堆， 最后就可以得到与该序列对应的堆。 如此得到堆的排序方法： （1）首先将一个无序序列建成堆 （2）然后将堆顶元素（序列中最大项）与堆中最后一个元素交换（最大项应该在序列 的最后）。 1.9 本章小结 学习完本章之后要掌握以下内容： 1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与 非线性结构的概念。 3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排 序）。 习 题 1 一、选择题 1. 栈和队列的共同特点是（ ） A）都是先进先出 B）都是先进后出 C）只允许在端点处插入和删除元素 D）没有共同点 2. 已知二叉树后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是 ( ) A）acbed