|
() 二叉排序树上的查找 ①查找递归算法 在二叉排序树上进行查找和二分查找类似也是一个逐步缩小查找范围的过程 递归的查找算法 BSTNode *SearchBST(BSTree TKeyType key) { //在二叉排序树T上查找关键字为key的结点成功时返回该结点位置否则返回NUll if(T==NULL||key==T>key) //递归的终结条件 return T; //T为空查找失败;否则成功返回找到的结点位置 if(keykey) return SearchBST(T>lchildkey); else return SearchBST(T>rchildkey);//继续在右子树中查找 } //SearchBST ②算法分析 在二叉排序树上进行查找时若查找成功则是从根结点出发走了一条从根到待查结点的路径若查找不成功则是从根结点出 发走了一条从根到某个叶子的路径 () 二叉排序树查找成功的平均查找长度 在等概率假设下下面(a)图中二叉排序树查找成功的平均查找长度为 在等概率假设下(b)图所示的树在查找成功时的平均查找长度为 ASL b =(+++++++++)/= 注意 与二分查找类似和关键字比较的次数不超过树的深度 |
