7.3动态查找表ADT DynamicSearchTable:数据对象：D是具有相同特性的元素集合数据关系：同属集合关系。基本操作：-InitDSTable（&DT）- DestroyDSTable （&DT)- SearchDSTable （DT , kval )*- InsertDSTable （&DT,e)*- DeleteDSTable (&DT,kval )-TraverseDSTable （DT,VisitO)ADT DynamicSearchTable:11中国科学技术大学ypb@ustc.edu.cn
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;
>二叉查找树（检索树）·查找树、二叉查找树一通过和根结点的关键字进行比较可以将继续查找的范围缩小到某一颗子树中，具有该特性的树称查找树。二叉排序树又称二叉查找树。·例二叉查找树的查询过程。算法8.4 bool Search BST(BiTree T,KeyType kval, BiTree&p,BiTree &f)二叉查找树的插入算法- 算法8.5 bool Insert BST(BiTree &T, KeyType kval)品12中国科学技术大学ypb@ustc.edu.cn
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)
二叉查找树查找算法BoolBinSrTree(BiTreeBT,KeyTypekval,BiTree&p,BiTree&f)(/*查找关键字为kval的记录。若找到，则指针p指向该记录并返回TRUE：否则，返回FALSE。指针指向p所指记录的双亲记录；若查找失败则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;1Ⅱ未查找到return FALSE;//BinSrTree13vpb@ustc.edu.cn中国科学技术大学
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
二叉查找树的插入算法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->IChild = t->rChild = NULL;//空树时为根结点if (!f) BT = t;else if (kval < f->data.key)//为左孩子f->IChild = t;l/为右孩子else f->rChild = t;return TURE;//BinSrTreeIns14vpb@ustc.edu.cn中国科学技术大学
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+C15中国科学技术大学ypb@ustc.edu.cn
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