数据结构－第09章－查找_02.ppt

计算机控制系统 第一讲 9.2 动态查找表 特点：频繁进行插入、删除、查找，表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。 动态查找表可有不同的表示方法。本节主要讨论以各种树结构表示时的实现方法。 9.2 动态查找表 抽象数据类型查找表的定义： ADT DynamicSearchTable{ 数据对象D：Ｄ是具有相同特性的数据元素的集合。 各个数据元素均含有类型相同，有可唯一标识数据元 素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P： InitDSTable(DT); 操作结果：构造一个空的动态查找表DT。 9.2 动态查找表 抽象数据类型查找表的定义： DestroyDSTable(DT)； 初始条件： 动态查找表DT存在。 操作结果：销毁表DT。 SearchDSTable(DT, key); 初始条件：动态查找表DT存在，key为给定值。 操作结果：若DT中存在其关键字等于key的数据元 素，则函数值为该元素的值或在表中的位置，否则为 “空”。 9.2 动态查找表 InsertDSTable(DT, e)； 初始条件：动态查找表DT存在，e为插入的数据元素。 操作结果：若DT中不存在其关键字等于e的数据元素， 则插入e到DT。 DeleteDSTable(DT,key); 初始条件：动态查找表DT存在， key为和关键字类型 相同的给定值。 操作结果：若DT中存在其关键字等于key的数据元素， 则删除之。 9.2 动态查找表 抽象数据类型查找表的定义： TraverseDSTable(DT,Visit()); 初始条件：动态查找表DT存在，Visit是对数据元素操 作的应用函数。 操作结果：按某种次序对DT的每个数据元素调用函数 visit( )一次且仅一次。一旦visit( )失败，则操作失败。 }ADT DynamicSearchTable 9.2.1 二叉排序树 1、二叉排序树及其查找过程 二叉排序树或者是一棵空树；或者是具有下列性质的二叉树： 1) 若它的左子树不空，则左子树上所有结点的关键字的值均小于它的根结点的关键字的值； 2) 若它的右子树不空，则右子树上所有结点的关键字的值均大于它的根结点关键字均的值； 3) 它的左、右子树了分别为二叉排序树。 9.2.1 二叉排序树 例：二叉排序树 9.2.1 二叉排序树 二叉排序树查找算法思想： 1) 如果树为空，则返回不成功。否则，将给定的值与二叉排序树根结点的关键字比较，若等于根结点的关键字，成功，返回。否则，跳到步骤2); 2) 若给定的值小于根结点的关键字的值，查其左子树 执行步骤1) ，否则执行步骤3) ； 3) (大于根结点的关键字值)查其右子树，执行步骤1) 。 9.2 二叉排序树-查找 二叉排序树查找算法： 9.2 二叉排序树-查找-例 9.2 二叉排序树-插入 2、二叉排序树的插入和删除 插入算法思想： 首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左孩子还是右孩子，将被插结点作为叶子结点插入。 若二叉树为空，则首先单独生成根结点。 注意：新插入的结点总是叶子结点。 9.2 二叉排序树-插入-例1 例 1：将数的序列：122、99、250、110、300、280 作为二叉分类树的结点的关键字值，生成二叉分类树。 9.2 二叉排序树-插入 2、二叉排序树的插入和删除 插入算法思想： 首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右孩子。将被插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。 注意：新插入的结点总是叶子结点。 9.2 二叉排序树-插入算法 2、插入算法思想 9.2 二叉排序树-插入算法-例 2、插入算法：执行实例：插入值为 280 的结点 9.2 二叉排序树-插入算法程序 2、插入算法：查找算法改写 在根指针T所指二叉排序树递归查找关键字之值为 key 的结点。 1) 如树空， p 为 NULL( f )，返回查找不成功 2) 如树非空，将给定的值与二叉排序树根结点的关键字比较，若等于根结点的关键字，查找成功，则p指向该数据元素结点，并返回TRUE。否则，跳到步骤 3) 9.2.1 二叉排序树 二叉排序树查找算法思想： 3) 若给定的值小于根结点的关键字的值，查其左子树，执行步骤1 ) ，否则执行步骤4 ) 4 ) (大于根结点的关键字值)查其右子树，执行步骤1) 。 9.2 二叉排序树-插入算法程序 2、