Java版数据结构(程序员必须看).pptVIP

数 据 结 构 第一章 绪 论 第二章 线性表 第五章 数组和广义表 第六章 树和二叉树 6.2 二叉树 二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。 6.2.1 二叉树的定义 定义：二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。 这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。下图列出二差树的5种基本形态， (c) 和（d）是不同的两棵二叉树。 6.2.2 二叉树的性质 二叉树具有下列重要性质： 6.2.2 二叉树的性质 性质2： 6.2.2 二叉树的性质 二叉树具有下列重要性质： 如果深度为k、由n个结点的二叉树中每个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为完全二叉树，满二叉树是完全二叉树的特例。 性质4： 性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i（1=i=n),有： （1）如果i＝1，则结点i无双亲，是二叉树的根；如果i1，则其双亲的编号是 i/2(整除）。 （2）如果2in，无左孩子；否则，其左孩子是结点2i。 （3）如果2i＋1n，则结点i无右孩子；否则，其右孩子是结点2i＋1。 一般二叉树 1、图的定义和术语 2、图的存储结构 3、图的遍历 4、图的连通性问题 5、有向无环图及其应用 6、最短路径 第七章 图 7.1 图的定义和术语 7.3 图的遍历 7.6 最短路径 8.1 静态查找表 8.3 哈希表 3、冲突解决 A)开放定址法 方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即 Hi=(H(key)+di) % m，i=1,2,……k(k?m-1) 其中：H(key)——哈希函数 m——哈希表表长 di——增量序列 分类 线性探测再散列：di=1,2,3,……m-1 二次探测再散列：di=12,-12,22,-22,32,……±k2(k?m/2) 伪随机探测再散列：di=伪随机数序列 9.1 概述 9.1 概述 9.1 概述 9.4 选择类排序 外部排序的方法 第 11章 有效算法的设计 4）建立初始堆：从标号最大的有孩子的点i开始筛选，（i=n整除2）,然后i减 1，直到i为1为止。 97 76 13 65 49 49 38 69 49 49 38 69 97 76 13 65 4）建立初始堆：从标号最大的有孩子的点i开始筛选，（i=n整除2）,然后i减 1，直到i为1为止。 97 76 13 65 49 49 38 69 49 49 38 69 97 76 13 65 4）建立初始堆：从标号最大的有孩子的点i开始筛选，（i=n整除2）,然后i减 1，直到i为1为止。 38 76 13 65 49 49 97 69 49 49 97 69 38 76 13 65 4）建立初始堆：从标号最大的有孩子的点i开始筛选，（i=n整除2）,然后i减 1，直到i为1为止。 49 76 13 65 38 49 97 69 38 49 97 69 49 76 13 65 4）建立初始堆：从标号最大的有孩子的点i开始筛选，（i=n整除2）,然后i减 1，直到i为1为止。 49 76 13 65 38 49 97 69 38 49 97 69 49 76 13 65 4）建立初始堆：从标号最大的有孩子的点i开始筛选，（i=n整除2）,然后i减 1，直到i为1为止。 49 76 13 65 38 97 49 69 38 97 49 69 49 76 13 65 4）建立初始堆：从标号最大的有孩子的点i开始筛选，（i=n整除2）,然后i减 1，直到i为1为止。 49 49 13 65 38 97 76 69 38 97 76 69 49 49 13 65 最大者在r[1]中 下一步r[1]与r[n]对换 4）建立初始堆：从标号最大的有孩子的点i开始筛选，（i=n整除2）,然后i减 1，直到i为1为止。 49 49 13 65 97 38 76 69 97 38 76 69 49 49 13 65 此时可理解为r[n]