ds06数据结构树-二叉排序树.ppt

回顾:二分查找当线性表中数据元素是按大小顺序排列存放时,可以采用二分法(折半查找)。二分查找是每次在要查找的数据集合中取出中间元素关键字Kmid与要查找的关键字K进行比较,根据比较结果确定是否要进一步查找。当Kmid=K,查找成功;当K<Kmid,将在Kmid的左半部分继续下一步查找当K>Kmid,将在Kmid右半部分继续下一步查找以此类推,每步的查找范围都将是上一次的一半。优点:查找效率高缺点:要求线性表有序,如果是进行动态查找,即需要对线性表进行插入、删除或排序操作,就必须移动大量的记录,当记录数很多时,这种移动的代价很大。第4章树§:左子树的值都比根结点小右子树的值都比根结点大中序遍历判定树得到的是一组有序的序列11个元素的二分查找判定树§,利用树型结构来动态创建查找表呢?第4章树§【定义】一个二叉搜索树是一棵二叉树,它可以为空。如果不为空,它将满足以下性质:非空左子树的所有键值小于其根结点的键值。非空右子树的所有键值大于其根结点的键值。左、右子树都是二叉搜索树。二叉搜索树“二叉搜索树(BST,BinarySearchTree)”也称二叉排序树或二叉查找树,它是一种对排序和查找都很有用的特殊二叉树。18105207223015413350631479510211811个元素二分查找的判定树二叉搜索树的动态查找二叉搜索树作为抽象数据结构的定义与普通二叉树相同,但操作集中多了下列几个特别的函数:PositionFind(ElementTypeX,BinTreeBST):从二叉搜索树BST中查找元素X,返回其所在结点的地址;PositionFindMin(BinTreeBST):从二叉搜索树BST中查找并返回最小元素所在结点的地址;PositionFindMax(BinTreeBST):从二叉搜索树BST中查找并返回最大元素所在结点的地址。第4章树§BinTreeInsert(ElementTypeX,BinTreeBST)BinTreeDelete(ElementTypeX,BinTreeBST)typedefPositionBinTree二叉搜索树的查找操作Find第4章树§,如果树为空,返回NULL,表示未找到关键字为X的结点。若搜索树非空,则根结点关键字和X进行比较,依据比较结果,需要进行不同的处理:若根结点键值小于X,满足条件的结点将不会出现在它的左子树,接下来的搜索只需在右子树中进行;如果根结点的键值大于X,接下来的搜索将在左子树中进行;若两者比较结果是相等,搜索完成,返回指向此结点的指针。二叉搜索树的查找操作Find第4章树§(ElementTypeX,BinTreeBST){if(!BST)returnNULL;//查找失败if(X>BST->Data)returnFind(X,BST->Right);//在右子树中继续查找elseif(X<BST->Data)returnFind(X,BST->Left);//在左子树中继续查找else//X==BST->DatareturnBST;//查找成功,返回找到结点的地址}PositionIterFind(ElementTypeX,BinTreeBST){while(BST){if(X>BST->Data) BST=BST->Right;//向右子树中移动,继续查找elseif(X<BST->Data) BST=BST->Left;//向左子树中移动,继续查找else//X==BST->DatareturnBST;//查找成功,返回结点的找到结点的地址}returnNULL;//查找失败}由于非递归函数的执行效率高,一般采用非递归的迭代来实现查找。很容易将“尾递归”函数改为迭代函数第4章树§查找最大和最小元素第4章树最大元素一定是在树的最右分枝的端结点上最小元素一定是在树的最左分枝的端结点上181015207229最左端点最右端点§§(BinTreeBST){if(!BST)while(BST->Right)BST=BST->Right;//沿右分支继续查找,直到最右叶结点returnBST;}PositionFindMin(BinTreeBST){if(!BST)returnNULL;//空的二叉搜索树,返回NULLelseif(!BST->Left)returnBST;//找到最左叶结点并返回elsereturnFindMin