中国科学技术大学：《数据结构及算法》课程教学资源（PPT课件讲稿）第7章 查找表

7.3动态查找表 ADT DynamicSearchTable 数据对象：D是具有相同特性的元素集合。 数据关系：同属集合关系。 基本操作： InitDSTable (&DT DestroyDSTable (&DT -SearchDSTable DT,kval InsertDSTable &DT,e DeleteDSTable (&DT,kval ) TraverseDSTable (DT,Visit()) ADT DynamicSearchTable; ypb@ustc.edu.cn 11 中国科学技术大学

ypb@ustc.edu.cn 11 中国科学技术大学 7.3动态查找表 ADT DynamicSearchTable{ 数据对象：D是具有相同特性的元素集合。 数据关系：同属集合关系。 基本操作： – InitDSTable（&DT） – DestroyDSTable（&DT） – SearchDSTable（DT，kval） – InsertDSTable（&DT,e） * – DeleteDSTable（&DT,kval） * – TraverseDSTable（DT,Visit()） }ADT DynamicSearchTable;

S >二叉查找树（检索树） 查找树、二叉查找树 一通过和根结点的关键字进行比较可以将继续查找的范 围缩小到某一颗子树中，具有该特性的树称查找树。 二叉排序树又称二叉查找树。 ·例二叉查找树的查询过程。 8.4 bool Search BST(BiTree T,KeyType kval,BiTree &p,BiTree &f) ·二叉查找树的插入算法 8.5 bool Insert BST(BiTree &T,KeyType kval) ypb@ustc.edu.cn 12 中国科学技术大学

ypb@ustc.edu.cn 12 中国科学技术大学 ➢ 二叉查找树（检索树） • 查找树、二叉查找树 – 通过和根结点的关键字进行比较可以将继续查找的范 围缩小到某一颗子树中，具有该特性的树称查找树。 二叉排序树又称二叉查找树。 • 例二叉查找树的查询过程。 算法8.4 bool Search_BST(BiTree T,KeyType kval, BiTree &p,BiTree &f) • 二叉查找树的插入算法 – 算法8.5 bool Insert_BST(BiTree &T, KeyType kval)

二叉查找树查找算法 Bool BinSrTree(BiTree BT,KeyType kval,BiTree &p,BiTree &f) {U~查找关键字为kval的记录。若找到，则指针p指向该记录并返 回TRUE;否则，返回FALSE。指针指向p所指记录的双亲记 录；若查找失败则为空指针，则为这个空指针的双亲。*/ p=BT; while (p){ if (p->data.key==kval)return TRUE; ∥查找成功 else f=p; if(p->data.key>kval)p=p->IChild;/∥查找左子树 else p=p->rChild; ∥查找右子树 return FALSE; ∥未查找到 }/∥BinSrTree ypb@ustc.edu.cn 13 中国科学技术大学

ypb@ustc.edu.cn 13 中国科学技术大学 二叉查找树查找算法 Bool BinSrTree(BiTree BT, KeyType kval, BiTree &p, BiTree &f) {/* 查找关键字为kval的记录。若找到，则指针p指向该记录并返 回TRUE；否则，返回FALSE。指针f指向p所指记录的双亲记 录;若查找失败则p为空指针，f则为这个空指针的双亲。*/ p = BT; while (p) { if (p->data.key == kval) return TRUE; // 查找成功 else { f = p; if (p->data.key > kval) p = p->lChild;// 查找左子树 else p = p->rChild; // 查找右子树 } } return FALSE; // 未查找到 }// BinSrTree

S 二叉查找树的插入算法 Bool BinSrTree Ins(BiTree &BT,KeyType kval) {I*当二叉查找树BT中不存在关键字为kwal的记录时，插入 之并返回TUE;否则，不进行插入操作并返回 FALSE。*/ f=NULL; if(BinSrTree(BT,kwal,p,fD)return FALSE;∥不插入 t=new BiTNode; t->data.key kval;t->IChild t->rChild NULL; if (!f)BT=t; ∥空树时为根结点 else if (kval f->data.key) f->IChild t; ∥为左孩子 else f->rChild t; 川为右孩子 return TURE; //BinSrTree_Ins ypb@ustc.edu.cn 14 中国科学技术大学

ypb@ustc.edu.cn 14 中国科学技术大学 二叉查找树的插入算法 Bool BinSrTree_Ins(BiTree &BT, KeyType kval) {/* 当二叉查找树BT中不存在关键字为kval的记录时，插入 之并返回TRUE； 否则，不进行插入操作并返回 FALSE。 */ f = NULL; if (BinSrTree(BT, kval, p, f)) return FALSE; // 不插入 t = new BiTNode; t->data.key = kval; t->lChild = t->rChild = NULL; if (!f) BT = t; // 空树时为根结点 else if (kval < f->data.key) f->lChild = t; // 为左孩子 else f->rChild = t; // 为右孩子 return TURE; }//BinSrTree_Ins

删除结点的处理方法 1)若是叶子结点，直接删除 2)只有一个孩子，则将其子树直接挂到其双亲上。 3)有两个孩子，找左子树中最大的一个元素，代替被 删除结点，最大元素肯定只有一个孩子，按2)处 理删除最大元素 8.6 bool Delete BST(BiTree &T,KeyType kval) ·二叉查找树的平均查找长度 p (n)=2 (n+1)/n *logn+C ypb@ustc.edu.cn 15 中国科学技术大学

ypb@ustc.edu.cn 15 中国科学技术大学 • 删除结点的处理方法 1)若是叶子结点，直接删除 2)只有一个孩子，则将其子树直接挂到其双亲上。 3)有两个孩子，找左子树中最大的一个元素，代替被 删除结点，最大元素肯定只有一个孩子，按2）处 理删除最大元素 – 算法8.6 bool Delete_BST(BiTree &T, KeyType kval) • 二叉查找树的平均查找长度 p（n）＝2（n＋1）/n *logn+C