《计算机软件基础》第四章 查找与排序（4-8）二叉排序树的查找（1/2）

的查找 叉排序树上的查找 和二分查找类似,也 算1.算法思想 是一个逐步缩小查找 范围的过程 首先在整棵树中进行查找,用待查关键字 值与根结点的关键字值相比较,若等于根结点 的关键字值,则查找成功;若小于根结点的关 础|键字值,则缩小查找范围到左子树;若大于根 结点的关键字值,则缩小査找范围到右子树; 在左、右子树中的查找与在整棵树中的查找过 程相同。持续上述查找过程,直到找到或查找 范围为空

计 算 机 软 件 基 础 1. 算法思想 首先在整棵树中进行查找，用待查关键字 值与根结点的关键字值相比较，若等于根结点 的关键字值，则查找成功；若小于根结点的关 键字值，则缩小查找范围到左子树；若大于根 结点的关键字值，则缩小查找范围到右子树； 在左、右子树中的查找与在整棵树中的查找过 程相同。持续上述查找过程，直到找到或查找 范围为空。 二叉排序树上的查找 和二分查找类似，也 是一个逐步缩小查找 范围的过程 4.3 二叉排序树 的查找

45 18 62 若查找关 键字为30 的结点 12 30)(49 88 从根结点 25 44 82 开始查找 30<45 二叉排序树 到左子树找 查找过程示例

12 30 88 82 49 18 62 45 25 44 二叉排序树 查找过程示例 若查找关 键字为30 的结点 p 从根结点 开始查找 30<45 到左子树找

45 p-18 62 若查找关 键字为30 的结点 12 30)(49 88 30>18 25 44 82 到右子树找 二叉排序树 查找过程示例

12 30 88 82 49 18 62 45 25 44 二叉排序树 查找过程示例 若查找关 键字为30 的结点 p 30>18 到右子树找

45 18 62 若查找关 键字为30 的结点 12)p80)(49 88 30=30 25 44 82 查找成功 二叉排序树 查找过程示例

12 30 88 82 49 18 62 45 25 44 二叉排序树 查找过程示例 若查找关 键字为30 的结点 p 30=30 查找成功

45 18 62 若查找关 键字为28 的结点 12 30)(49 88 从根结点 25 44 82 开始查找 28<45 二叉排序树 到左子树找 查找过程示例

12 30 88 82 49 18 62 45 25 44 二叉排序树 查找过程示例 若查找关 键字为28 的结点 p 从根结点 开始查找 28<45 到左子树找

45 p-18 62 若查找关 键字为28 的结点 12 30)(49 88 28>18 25 44 82 到右子树找 二叉排序树 查找过程示例

12 30 88 82 49 18 62 45 25 44 二叉排序树 查找过程示例 若查找关 键字为28 的结点 p 28>18 到右子树找

45 18 62 若查找关 键字为28 的结点 12)p80)(49 88 28<30 25 44 82 到左子树找 二叉排序树 查找过程示例

12 30 88 82 49 18 62 45 25 44 二叉排序树 查找过程示例 若查找关 键字为28 的结点 p 28<30 到左子树找

45 18 62 若查找关 键字为28 的结点 12 30)(49 88 28>25 25 44 82 到右子树找 二叉排序树 查找过程示例

12 30 88 82 49 18 62 45 25 44 二叉排序树 查找过程示例 若查找关 键字为28 的结点 p 28>25 到右子树找

45 18 62 若查找关 键字为28 的结点 12 30)(49 88 NULL 25 44 82 待查找 范围为空 查找失败 二叉排序树 查找过程示例

12 30 88 82 49 18 62 45 25 44 二叉排序树 查找过程示例 若查找关 键字为28 的结点 p=NULL 待查找 范围为空 查找失败

bstree *bstsearch(bstree *t, int x) /在根结点为*t的二叉排序树中查找关键字为x的元素* While(t!=NULL Rif(x==t->key) return t 算机软件基础 /查找成功时返回该结点的指针* else Rif(xkey)t=t->lchild; 当待査值小于根结点关键字值时在左子树中查找* else t=t->rchild /当待查值大于关键字值时在右子树中查找* return NULL;/查找失败时返回空指针* 3/*bstsearch*/

2. 算法描述 bstree *bstsearch(bstree *t, int x) /*在根结点为*t的二叉排序树中查找关键字为x的元素*/ {while(t!=NULL) {if(x==t->key) return t; /*查找成功时返回该结点的指针*/ else {if(xkey) t=t->lchild; /*当待查值小于根结点关键字值时在左子树中查找*/ else t=t->rchild; } /*当待查值大于关键字值时在右子树中查找*/ } return NULL; /*查找失败时返回空指针*/ } /*bstsearch*/ 计 算 机 软 件 基 础