6-2 二叉排序树查找操作
时间: 2024-02-20 09:02:10 浏览: 31
二叉排序树(Binary Search Tree,简称BST)是一种特殊的二叉树,它的每个节点都包含一个关键字,并且左子树中所有节点的关键字都小于该节点的关键字,右子树中所有节点的关键字都大于该节点的关键字。
在BST中进行查找操作时,可以采用以下步骤:
1. 从根节点开始,比较要查找的值与当前节点的关键字大小关系。
2. 如果要查找的值小于当前节点的关键字,则继续在左子树中查找。
3. 如果要查找的值大于当前节点的关键字,则继续在右子树中查找。
4. 如果要查找的值等于当前节点的关键字,则查找成功。
5. 如果查找到空节点(即没有找到要查找的值),则查找失败。
具体实现时,可以使用递归或迭代的方式进行查找。递归实现方式如下:
```
// BST查找操作(递归实现)
Node* searchBST(Node* root, int key) {
if (root == NULL || root->val == key) {
return root;
}
if (key < root->val) {
return searchBST(root->left, key);
} else {
return searchBST(root->right, key);
}
}
```
迭代实现方式如下:
```
// BST查找操作(迭代实现)
Node* searchBST(Node* root, int key) {
while (root != NULL && root->val != key) {
if (key < root->val) {
root = root->left;
} else {
root = root->right;
}
}
return root;
}
```
其中,Node为BST的节点类型,包含三个属性:val表示节点的关键字,left表示左子节点的指针,right表示右子节点的指针。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)