③83动态查找表 ADT DynamicSearchTablet 数据对象:D是具有相同特性的元素集合。 数据关系:同属集合关系。 基本操作: InitDS Table(&Dt Destroy Table(&Dt SearchDSTable(dt, kval InsertDSTable(&DTe DeleteDSTable(&dt, kval )* TraverseDSTable(dT, VisitO JADT Dynamic Search Table pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 11 中国科学技术大学 8.3动态查找表 ADT DynamicSearchTable{ 数据对象：D是具有相同特性的元素集合。 数据关系：同属集合关系。 基本操作： – InitDSTable（&DT） – DestroyDSTable（&DT） – SearchDSTable（DT，kval） – InsertDSTable（&DT,e） * – DeleteDSTable（&DT,kval） * – TraverseDSTable（DT,Visit()） }ADT DynamicSearchTable;
8.3.1二叉查找树(检索树) 查找树、二叉查找树 通过和根结点的关键字进行比较可以将继续查找的范 围缩小到某一颗子树中,具有该特性的树称查找树。 二叉排序树又称二叉查找树。 例二叉查找树的查询过程。 算法84 bool search bst( BiTree T, Key Type kval, Bitree &p, BiTree &f) 二叉查找树的插入算法 算法85bo0 nsert BST(BiTree&r, Key type kval pboustc. edu. cn 12 中国科学技术大学
ypb@ustc.edu.cn 12 中国科学技术大学 8.3.1二叉查找树（检索树） • 查找树、二叉查找树 – 通过和根结点的关键字进行比较可以将继续查找的范 围缩小到某一颗子树中，具有该特性的树称查找树。 二叉排序树又称二叉查找树。 • 例二叉查找树的查询过程。 算法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) {查找关键字为kva的记录。若找到,则指针p指向该记录并返 回TRUE;否则,返回 FALSE。指针璀指向p所指记录的双亲记 录;若查找失败则p为空指针,恻为这个空指针的双亲。 p=BT; while(p)i if(p> data. key==kva) return TRUE;∥查找成功 else f= p if(p> data. key>kva)p=p>Chid;∥查找左子树 else p=p->rChild ∥找右子树 return False ∥查找到 ∥/ BinSrtree pboustc. 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
③二叉查找树的插入算法 Bool BinSrtree Ins bitree &bt, key type kval) {(当二叉查找树BT中不存在关键字为kval的记录时,插入 之并返回TRUE;否则,不进行插入操作并返回 FALSE。 f= NUll: if( BinSrtree(BT,kwa,p,f) return FalsE;∥不插入 t= new binode: 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 J//BinSrTree Ins pboustc. 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