静态查找表(练习题) 设有10000个结点的线性表,若采用顺序查找、 顺序分块查找和二分查找,问它们的成功平均 查找长度ASL各是多少?
静态查找表（练习题） ◼ 设有10000个结点的线性表，若采用顺序查找、 顺序分块查找和二分查找，问它们的成功平均 查找长度ASL各是多少？
动态查找表 二叉排序树(二叉查找树) 或者是一棵空树,或者是具有下列性质的二叉树 (1)若它的左子树不空,则左子树上所有结点的值均小于它的根结 点的值; (2)若它的右子树不空,则右子树上所有结点的值均大于它的根结 点的值 3)它的左、右子树也分别为二叉排序树 (参见:P227-图97) 重要性质:按中序遍历该树所得到的中序序列是一个递增有序序列
动态查找表 ◼ 二叉排序树（二叉查找树） 或者是一棵空树，或者是具有下列性质的二叉树： （1）若它的左子树不空，则左子树上所有结点的值均小于它的根结 点的值； （2）若它的右子树不空，则右子树上所有结点的值均大于它的根结 点的值； （3）它的左、右子树也分别为二叉排序树。 （参见：P227-图9.7） 重要性质：按中序遍历该树所得到的中序序列是一个递增有序序列
动态查找表 二叉排序树的查找 当二叉排序树不空时,首先将给定值和根结点的关键字比较,若 相等,则查找成功;否则将依据给定值和根结点的关键字之间的 大小关系,分别在左子树或右子树上继续查找 (通常,可取二叉链表作为二叉排序树的存储结构。) 查找算法 BiTree SearchBST(BiTree T, Key Type key) i if((! t) eQ(key, T->data. key)) return(T) else if (Lt(key, T->data key))return(SearchBSTT->lchild, key)) else return(SearchBST(T->rchild, key)
动态查找表 ◼ 二叉排序树的查找 当二叉排序树不空时，首先将给定值和根结点的关键字比较，若 相等，则查找成功；否则将依据给定值和根结点的关键字之间的 大小关系，分别在左子树或右子树上继续查找。 （通常，可取二叉链表作为二叉排序树的存储结构。） 查找算法： BiTree SearchBST(BiTree T, KeyType key) { if ((! T) || EQ(key, T->data.key)) return(T); else if (LT(key, T->data.key)) return(SearchBST(T->lchild, key)); else return(SearchBST(T->rchild, key)); }
动态查找表 二叉排序树的插入 若二叉排序树为空,则待插入结点作为根结点插入到树中 当二叉树非空时,将待插入结点的关键字与根结点的关键字相比 较,若相等,则不插入;若小于,则将待插入结点插入到根的左 子树中;否则插入到根的右子树中。而子树的插入过程与树中的 插入过程相同。 (新插入的结点一定是一个新添加的叶子结点,并且是查找不成 功时查找路径上访问的最后一个结点的左孩子或右孩子结点。) (参见:P229-图98)
动态查找表 ◼ 二叉排序树的插入 若二叉排序树为空，则待插入结点作为根结点插入到树中； 当二叉树非空时，将待插入结点的关键字与根结点的关键字相比 较，若相等，则不插入；若小于，则将待插入结点插入到根的左 子树中；否则插入到根的右子树中。而子树的插入过程与树中的 插入过程相同。 （新插入的结点一定是一个新添加的叶子结点，并且是查找不成 功时查找路径上访问的最后一个结点的左孩子或右孩子结点。） （参见：P229-图9.8）
动态查找表 二叉排序树的插入算法(查找算法) Status SearchBST(BiTree T, Key Type key, BiTree f, BiTree &p) f if(( t)p=f return FALSE; else if (EQ(key, T->data key))ip=T; return TRUE; 1 else if (Lt(key, T->data key)) return(SearchBST(T->lchild, ey,T, p) else return( SearchBST(T->rchild, key, T, p)) 其中:T是将要生成的二叉排序树; f是指向T的双亲指针,初始调用值为NULL: p是指向数据元素结点的指针
动态查找表 ◼ 二叉排序树的插入算法(查找算法) Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) { if ((! T) {p=f; return FALSE; } else if (EQ(key, T->data.key)) {p=T; return TRUE; } else if (LT(key, T->data.key)) return(SearchBST(T->lchild, key,T, p)); else return(SearchBST(T->rchild, key,T, p)); } 其中：T是将要生成的二叉排序树； f是指向T的双亲指针，初始调用值为NULL； p是指向数据元素结点的指针