大学计算机基础第8章 算法与程序设计基础 (第二版).ppt

* 数学计算机科学学院 * * 二叉树 是一种特殊的树，是度不大于2的有序树。其特点是：①每个结点的度不大于2；②每个结点的孩子是有左右之分的，其次序不能任意更换。 数学计算机科学学院 二叉树的五种基本形态： 仅有根结点 右子树为空 左子树为空 左右子树均非空 空二叉树 * 二叉树的性质 在二叉树的第i（i≥1）层上至多有2i-1个结点。 深度为h（h≥1）的二叉树至多有2h－1个结点。 在任意一棵二叉树中，若叶子数为n0，度为2的结点数为n2，则n0=n2＋1。 数学计算机科学学院 * 4 2 3 1 6 7 8 9 10 11 12 13 14 15 5 * 满二叉树 是指一棵深度为h且有2h－1个结点的二叉树。即每层上都含有最大结点数。 完全二叉树 是除最底层外，其余各层的结点数目均达到最大值，并且最后一层中的结点均集中在最左边的位置上。 数学计算机科学学院 * * 二叉树的存储结构 顺序存储结构 链式存储结构 一般二叉树采用链式存储结构 数学计算机科学学院 * lchild value rchild * 11 A B c F E D ● ● ● ● ● ● ● ● ● 1 2 4 8 9 10 5 6 3 7 12 13 14 15 二叉树的顺序存储：用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。 0 0 0 0 F E 0 0 0 D C 0 B A 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。 * 二叉树的链式存储 数学计算机科学学院 * * 二叉树的遍历 遍历是指按某条有哪些信誉好的足球投注网站路线寻访树中每个结点，且每个结点只被访问一次。 查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。 按先左后右的原则，一般使用三种遍历： 先序遍历(D L R)：访问根结点，遍历左子树，遍历右子树。 中序遍历(L D R)：遍历左子树，访问根结点，遍历右子树。 后序遍历(L R D)：遍历左子树，遍历右子树，访问根结点。 数学计算机科学学院 * * 先序遍历：D L R 中序遍历：L D R 后序遍历：L R D A D B C T1 T2 T3 D L R A D L R D L R B D C D L R 以先序遍历D L R为例演示遍历过程 ABDC BDAC DBCA * 8.3 查找和排序 1、查找 在给定的某个数据结构中，寻找某个数值的过程。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。 查找的结果 查找成功：找到满足条件的结点 查找失败：找不到满足条件的结点。 数学计算机科学学院 * * 顺序查找 从给定的线性表的一端开始，顺序扫描表中各数据元素进行查找。 在下面两种情况下只能采取顺序查找： a. 线性表为无序表（元素排列是无序的） b. 即使是有序线性表，但采用的是链式存储结构。 折半查找（二分查找） 思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行。 数学计算机科学学院 * * 用折半查找方法寻找元素23的过程如下： 数学计算机科学学院 * 分三种情况： 1）若中间项的值等于23，则说明已查到。 2）若23小于中间项的值，则在线性表的前半部分查找； 3）若23大于中间项的值，则在线性表的后半部分查找。 * 2、排序 排序的功能：将一个数据元素（记录）的任意序列，重新排成一个按关键字有序的序列。 排序过程的组成步骤： 先比较两个关键字的大小； 然后将记录从一个位置移动到另一个位置。 外部排序、内部排序 内部排序方法主要有： 交换排序（冒泡、快速排序） 插入排序（直接插入排序、希尔排序） 选择排序（简单选择排序、堆排序） 数学计算机科学学院 * * 交换排序——通过交换数据元素的顺序进行排序 （1）冒泡排序 依次比较相邻的元素，若逆序则交换。 数学计算机科学学院 * * 快速排序 任取一元素T（基准），将小于T的元素移至前面，大于T的元素移至后面，如此下去。 以下是对初始序列的一趟快速排序过程： 数学计算机科学学院 * * 插入排序——依次将元素插入到有序的线性表中 直接插入排序 依次将无序序列中的各元素插入到有序的线性表中。 数学计算机科学学院 * * 希尔排序 将整个待排序元素分成若干个子序列分别进行直接插入排序。 分割子序列的方法：将位置相隔某个增量d的元素组成一个子序列，让增量d逐趟缩短，直到d＝1为止。 数学计算机科学学院 * *