计算机软件基础
1,算法思想首先在整棵树中进行查找，用待查关键字值与根结点的关键字值相比较，若等于根结点的关键字值，则查找成功；若小于根结点的关键字值，则缩小查找范围到左子树；若大于根结点的关键字值，则缩小查找范围到右子树；
在左、右子树中的查找与在整棵树中的查找过程相同。持续上述查找过程，直到找到或查找范围为空。
二叉排序树上的查找和二分查找类似，也是一个逐步缩小查找范围的过程
4.3 二叉排序树的查找
12 8830
82
49
18 62
45
4425
二叉排序树查找过程示例若查找关键字为 30
的结点
p
从根结点开始查找
30<45
到左子树找
12 8830
82
49
18 62
45
4425
二叉排序树查找过程示例若查找关键字为 30
的结点
p
30>18
到右子树找
12 8830
82
49
18 62
45
4425
二叉排序树查找过程示例若查找关键字为 30
的结点p
30=30
查找成功
12 8830
82
49
18 62
45
4425
二叉排序树查找过程示例若查找关键字为 28
的结点
p
从根结点开始查找
28<45
到左子树找
12 8830
82
49
18 62
45
4425
二叉排序树查找过程示例若查找关键字为 28
的结点
p
28>18
到右子树找
12 8830
82
49
18 62
45
4425
二叉排序树查找过程示例若查找关键字为 28
的结点p
28<30
到左子树找
12 8830
82
49
18 62
45
4425
二叉排序树查找过程示例若查找关键字为 28
的结点
p
28>25
到右子树找
12 8830
82
49
18 62
45
4425
二叉排序树查找过程示例若查找关键字为 28
的结点
p=NULL
待查找范围为空查找失败
2,算法描述
bstree *bstsearch(bstree *t,int x)
/*在根结点为 *t的二叉排序树中查找关键字为 x的元素 */
{while(t!=NULL)
{if(x==t->key) return t;
/*查找成功时返回该结点的指针 */
else
{if(x<t->key) t=t->lchild;
/*当待查值小于根结点关键字值时在左子树中查找 */
else t=t->rchild;
}
/*当待查值大于关键字值时在右子树中查找 */
}
return NULL; /*查找失败时返回空指针 */
} /*bstsearch*/
计算机软件基础计算机软件基础
3,算法分析分析,在二叉排序树上进行查找,若查找成功,实际上是从根结点出发走了一条从根到待查结点的路径；若查找不成功,则是从根结点出发走了一条从根到某个叶子的路径 。
结论,在二叉排序树上的查找过程中和关键字的比较次数不会超过树的深度，因此平均查找长度与树的形态（深度）有关。最坏的情况是当二叉排序树为一棵单支树的时候；
最好的情况是二叉排序树为一棵平衡二叉树的时候。