构造二叉排序树_二叉排序树的构造过程_二叉排序树怎么构造

半查找来实现。 先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记 录为止。二、折半查找的查找实现 int Search_Bin(SSTable ST,KeyType key){ low=1;high=ST.length; while(low<=high){mid=(low+high)/2; if EQ(key,ST.elem[mid].key) return mid; else if LT(key,ST.elem[mid].key) high=mid -1; else low=mid +1 ; } return 0; }//Search_Bin; 三、折半查找的性能分析 折半查找在查找成功时和给定值进行比较的关键字个数至多为 回目录 上一课 下一课第三十一课： 第三十一课：动态查找表本课主题： 本课主题： 动态查找表 教学目的： 教学目的： 掌握二叉排序树的实现方法 教学重点： 教学重点： 二叉排序树的实现 教学难点： 教学难点： 构造二叉排序树的方法 授课内容： 授课内容：一、动态查找表的定义 动态查找表的特点是：表结构本身是在查找过程中动态生成的，即对于给定值 key,若表中存在其关键 字等于 key 的记录，则查找成功返回，否则插入关键字等于 key 的记录。构造二叉排序树

以政是 动态查找表的定义： ADT DymanicSearchTable{ 数据对象Ｄ：Ｄ是具有相同特性的数据元素的集合。各个数据元素均含有类型相 同，可唯一标识数据元素的关键字。构造二叉排序树 数据关系Ｒ：数据元素同属一个集合。 基本操作Ｐ： InitDSTable(&DT); DestroyDSTable(&DT); SearchDSTable(DT,key); InsertDSTable(&DT,e); DeleteDSTable(&DT,key); TraverseDSTable(DT,Visit()); }ADT DynamicSearchTable 二、二叉排序树及其查找过程 二叉排序树或者是一棵空树；或者是具有下列性质的二叉树： １、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； ２、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； ３、它的左、右子树了分别为二叉排序树。如果取二叉链表作为二叉排序树的存储结构，则上述查找过程如下： 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)); }//SearchBST 三、二叉排序树的插入和删除 二叉排序树是一种动态树表，其特点是，树的结构通常不是一资生成的，面是在 查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。

新插入的结 点一定是一个新添加的叶子结点， 并且是查找不成功时查找路径问的最后一 个结点的左孩子或右孩子结点。 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) SearchBsT(T->lchild,key,T,p); else SearchBST(T->rchild,key,T,p); }//SearchBST 插入算法： Status InsertBST(BiTree &T,ElemType e){ if(!SearchBST(T,e.key,NULL,p){s=(BiTree)mallo

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-36021-1.html