ds9.2.1陆小马功钟浩.pptVIP

9.2 动态查找表 二叉排序树 9.2 动态查找表 1. 动态查找表 2. 二叉排序树 1. 动态查找表 动态查找表除查找操作外，还可以进行插入和删除。 动态查找表本身是在查找过程中动态生成的。 动态查找表ADT定义。P226 2. 二叉排序树-概念 （1）什么是二叉排序树 P227 4 2 1 3 6 5 7 4 2 1 8 6 5 7 8 中序遍历二叉排序树，得到从小到大的有序序列。 2. 二叉排序树-查找 （2）查找算法 首先与根结点关键字比较，若相等则查找成功；否则根据大小关系在左子树或右子树上继续查找。 t-data t-data t =? 2. 二叉排序树-查找算法1 二叉排序树查找算法1 BstTree BstSearch ( BstTree t, ElemType x ) { if ( t==NULL ) return NULL; else if ( t-data==x ) return t; else if ( xt-data ) return BstSearch ( t-lchild, x); else return BstSearch ( t-rchild, x); } 继续在左子树查找 继续在右子树查找 2. 二叉排序树-查找算法2 查找过程正好走了一条从根结点到该结点的路径。若走到空指针则查找失败。 2. 二叉排序树-查找算法2 二叉排序树查找算法2 BstTree BstSearch ( BstTree t, ElemType x ) { p = t; while ( p ) { if ( p-data==x ) return p; //查找成功 else if ( xp-data ) p = p-lchild; else p = p-rchild; } return NULL; // 查找失败 } 2. 二叉排序树-插入 （3）插入 首先进行查找，如果找不到，则插入结点。 “找不到”时，查找过程必定走到某个空指针上，待插入结点就插入此处。 p t k s f f指向p的双亲 2. 二叉排序树-插入算法 BstTree BstInsert ( BstTree t, ElemType x ) { // 查找 x p = t; f = NULL; // f 指向p的双亲 while ( p ) { if ( p-data==x ) return p; //查找成功 else if ( xp-data ) { f = p; p = p-lchild; } else { f = p; p = p-rchild; } } } // 未找到，插入 x ? 2. 二叉排序树-插入算法 // 未找到，插入 x s = malloc(sizeof(BiNode)); s-data = x; s-lchild = s-rchild = NULL; if ( f == NULL ) t = s; // 插入s为根结点 else if ( x f-data ) f-lchild = s; else f-rchild = s; return s; // 返回插入结点 } 2. 二叉排序树-建立 （4）建立二叉排序树 开始时，二叉树为空，依次插入给定的关键字即可建立。 2. 二叉排序树-建立 例：给定关键字序列{53，45，12，24，90，45，80}，建立二叉排序树。 提示：从空二叉树开始，依次插入关键字。 53 45 90 12 24 80 2. 二叉排序树-删除 （5）删除 首先进行查找，若找到，则删除结点。 删除结点时需要修改 2. 二叉排序树-删除算法 BstTree BstDelete ( BstTree t, ElemType x ) { // 查找 x p = t; f = NULL; // f 指向p的双亲 while ( p ) { if ( p-data==x ) break; //查找成功，进行删除 else if ( xp-data ) { f = p; p = p-lchild; } else { f = p; p = p-rchild; } } } // 若找到，删除结点 if ( p != NULL ) …? 2. 二叉排序树-删除算法 被删除结点分三种情况： a) 叶子 b) 左子树或右子树为空 c) 左右子树都不空 f p (a) f p (b) f p f p f p f p (c) 2. 二叉排序树-