二叉排序树的递归查找 定义 一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树； 【注1】：以上的三种定义在不同的数据结构教材中均有不同的定义方式，但是都是正确的。在开发时需要根据不同的需求进行选择。 【注2】：没有键值相等的结点。 性质 中序遍历非空的二叉排序树所得的数据序列是一个按关键字排列的递增有序序列。 算法思想 （1）若二叉排序树为空，则查找失败，返回空指针。 （2）若二叉排序树非空，将给定值key与根结点的关键字 T->data.key进行比较： 若key等于T->data.key,则查找成功，返回根结点地址； @若key小于T->data.key,则进一步查找左子忄对；若key大于T->data.key,则进一步查找右子树。 递归算法代码 查找分析 步骤： 1、若根结点的关键字值等于查找的关键字，成功。 2、否则，若小于根结点的关键字值，递归查左子树。 3、若大于根结点的关键字值，递归查右子树。 4、若子树为空，查找不成功。 平均情况分析（在成功查找两种的情况下）： 在一般情况下，设 P（n，i）为它的左子树的结点个数为 i 时的平均查找长度。结点个数为 n = 6 且 i = 3;，则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6 注意： 这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。 在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。平均查找长度= 每个结点的深度的总和 / 总结点数（二叉树图中应为左子树P(3)，右子树P(2)）。 P(3) = （1+2+2）/ 3 = 5/3； P(2) = （1+2）/ 2 = 3/2； ∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n； ∴ P（n）= P（n,i）/ n <= 2(1+I/n)lnn； 因为 2(1+I/n)lnn≈1.38logn，故P(n)=O(logn)。 
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/87371.html
