第四章树与树的表示(一)案例.ppt

4.1树与树的表示;什么是树;什么是树;查找（Searching）;4;方法2：二分查找（Binary Search);[例] 假设有13个数据元素，按关键字由小到大顺序存放. 二分查找关健字为444的数据元素过程如下：;二分查找算法 int BinarySearch ( StaticTable * Tbl, ElementType K) { /*在表Tbl中查找关键字为K的数据元素*/ int left, right, mid, NoFound=-1;;[例] 仍然以上面13个数据元素构成的有序线性表为例 二分查找关健字为 43 的数据元素如下：;6;L;D;A;A;12.有序树和无序树：对于一棵树，若其中每一个结点的子树 （若有）具有一定的次序，则该树称为有序树，否则称为无序树。 ;树的表示 A;?;A N;4.2 二叉树及存储结构; ? 二叉树具体五种基本形态;特殊二叉树;8;二叉树几个重要性质 性质1： 在二叉树的第i层上至多有2i-1个结点。(i≥1) 性质2： 深度为k的二叉树上至多含2k-1个结点。(k≥1) 性质3： 对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点， A 则必存在关系式：n0 = n2+1。 ;满二叉树的特点： ◆ 基本特点是每一层上的结点数总是最大结点数。 ◆ 满二叉树的所有的支结点都有左、右子树。 ◆ 可对满二叉树的结点进行连续编号，若规定从根结点开始，按“自上而下、自左至右”的原则进行。 完全二叉树(Complete Binary Tree)：如果深度为k，由n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树。 或深度为k的满二叉树中编号从1到n的前n个结点构成了一棵深度为k的完全二叉树。 其中 2k-1 ≦ n≦2k-1 。; 完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特例。 完全二叉树的特点： 若完全二叉树的深度为k ，则所有的叶子结点都出现在第k层或k-1层。对于任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l+1。 性质4：n个结点的完全二叉树深度为：?㏒2n? +1。 其中符号： ?x?表示不大于x的最大整数。 ?x? 表示不小于x的最小整数。 ;,; 二叉树的存储结构 1. 顺序存储结构 用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树 的数据元素。对于完全二叉树上编号为i的结点元素存储在一维数组的下标 值为i的分 量中。 ;? 一般二叉树也可以采用这种结构，但会造成空间浪费…… 1;I