查找-北京师范大学.PPT

导航图(1) 查找 基本概念 和术语 静态查找表 动态查找表 哈希表 无序表的查找 有序表的查找 分块查找 二叉排序树 平衡二叉树 B-树 B+树 键树 导航图(2) 查找 基本概念 和术语 静态查找表 动态查找表 哈希表 无序表的查找 有序表的查找 分块查找 二叉排序树 平衡二叉树 B-树 B+树 键树 导航图(3) 查找 基本概念 和术语 静态查找表 动态查找表 哈希表 无序表的查找 有序表的查找 分块查找 二叉排序树 平衡二叉树 B-树 B+树 键树 导航图(4) 查找 基本概念 和术语 静态查找表 动态查找表 哈希表 无序表的查找 有序表的查找 分块查找 二叉排序树 平衡二叉树 B-树 B+树 键树 导航图(5) 查找 基本概念 和术语 静态查找表 动态查找表 哈希表 无序表的查找 有序表的查找 分块查找 二叉排序树 平衡二叉树 B-树 B+树 键树 导航图(6) 查找 基本概念 和术语 静态查找表 动态查找表 哈希表 无序表的查找 有序表的查找 分块查找 二叉排序树 平衡二叉树 B-树 B+树 键树 导航图(7) 查找 基本概念 和术语 静态查找表 动态查找表 哈希表 无序表的查找 有序表的查找 分块查找 二叉排序树 平衡二叉树 B-树 B+树 键树 导航图(8) 查找 基本概念 和术语 静态查找表 动态查找表 哈希表 无序表的查找 有序表的查找 分块查找 二叉排序树 平衡二叉树 B-树 B+树 键树 导航图(9) 查找 基本概念 和术语 静态查找表 动态查找表 哈希表 无序表的查找 有序表的查找 分块查找 二叉排序树 平衡二叉树 B-树 B+树 键树 导航图(10) 查找 基本概念 和术语 静态查找表 动态查找表 哈希表 无序表的查找 有序表的查找 分块查找 二叉排序树 平衡二叉树 B-树 B+树 键树 三、动态查找表——二叉排序树(3) 二叉排序树的插入 【基本思想】 如果二叉排序树是空树，那么就将key结点作为二叉排序树的根； 如果不是空树，就将根结点与key比较 如果相等，直接返回； 如果根结点比key大，则将key插入到左子树中； 如果根结点比key小，则将key插入到右子树中。 最终要么插入失败，要么key将成为一个叶子结点。 三、动态查找表——二叉排序树(4) int Insert(BTREE *root,int key) {/*向二叉排序树root中插入结点key，插入成功返回1，否则返回0*/ if(*root==NULL) {/*树为空，生成新的根结点*/ *root=(BTREE)malloc(sizeof(BTREENODE)); if(*root==NULL) return 0; (*root)-lchild=(*root)-rchild=NULL; (*root)-data=key; return 1; } if((*root)-datakey) return Insert((*root)-lchild,key); /*向左子树插入*/ else if((*root)-datakey) return Insert((*root)-rchild,key); /*向右子树插入*/ else return 1;/*直接返回*/ } 三、动态查找表——二叉排序树(5) 二叉排序树的删除 【基本思想】 假设p指向某二叉排序树中要删除的结点，而f指向该结点的双亲，要删除结点p，需要区分三种情况 ： ⑴结点p是单枝结点 ⑵结点p是叶子结点 ⑶结点p是双枝结点 三、动态查找表——二叉排序树(6) void Delete(BTREE *root,int key) {/*在二叉排序树root中删除关键字是key的结点*/ BTREENODEPTR p,q,f,h; /*在二叉排序树中查找key，获得指向key结点的指针p和p结点的双亲f*/ p=Search(*root,key,f); if(p==NULL)return;/*查找失败，直接返回*/ if(p-lchild==NULLp-rchild==NULL) h=NULL;/*叶子结点的情况*/ else if(p-lchild==NULL||p-rchild==NULL) {/*单枝结点的情况,h指向p的单枝子树*/ if(p-lchild!=NULL)h=p-lchild; else h=p-rchild; } 三、动态查找表——二叉排序树(6) else/*双枝结点*/ { f=p;/*开始寻找p的直接后继，并且f跟随q，保持是q的双亲状态*/ q=p-rchild;/*