二叉排序树的递归查找
时间: 2023-08-27 10:10:40 浏览: 42
二叉排序树(Binary Search Tree,BST)是一种特殊的二叉树,它满足以下两个条件:
1. 左子树上所有节点的值均小于它的根节点的值;
2. 右子树上所有节点的值均大于它的根节点的值。
因此,我们可以使用递归的方法来查找二叉排序树中的某个节点。具体步骤如下:
1. 如果当前节点为空,返回空;
2. 如果当前节点的值等于要查找的值,返回当前节点;
3. 如果当前节点的值大于要查找的值,递归查找左子树;
4. 如果当前节点的值小于要查找的值,递归查找右子树。
下面是递归查找的代码实现:
```c++
Node* search(Node* root, int value) {
if (root == nullptr || root->val == value) {
return root;
}
if (root->val > value) {
return search(root->left, value);
}
else {
return search(root->right, value);
}
}
```
其中,`root` 表示当前节点,`value` 表示要查找的值。如果找到了对应的节点,返回该节点的指针;否则返回空指针。
相关问题
二叉排序树的查找递归算法
二叉排序树的查找递归算法可以通过比较待查关键字与根节点关键字的大小来进行查找。具体步骤如下:
1. 如果树为空,则返回空指针。
2. 如果待查关键字等于根节点关键字,则返回指向该节点的指针,表示查找成功。
3. 如果待查关键字小于根节点关键字,则在左子树中继续递归查找。
4. 如果待查关键字大于根节点关键字,则在右子树中继续递归查找。
5. 重复步骤2、3、4,直到找到待查关键字或者查找到叶子节点为止。
以下是二叉排序树的查找递归算法的实现代码:
```c
BSTree SearchBST(BSTree bst, KeyType key) {
if (!bst) return NULL;
else if (bst->key == key) return bst; // 查找成功
else {
if (bst->key > key)
return SearchBST(bst->lchild, key); // 在左子树继续查找
else
return SearchBST(bst->rchild, key); // 在右子树继续查找
}
}
```
以上是二叉排序树的递归查找算法的实现,通过逐层比较待查关键字与节点关键字的大小,最终可以找到对应的节点或者确定节点不存在于树中。
二叉排序树的非递归查找
二叉排序树的非递归查找可以通过循环来实现。具体步骤如下:
1. 从根节点开始,将要查找的值与当前节点的值进行比较。
2. 如果要查找的值等于当前节点的值,则找到了目标节点,返回该节点。
3. 如果要查找的值小于当前节点的值,则将当前节点指向其左子节点,并继续比较。
4. 如果要查找的值大于当前节点的值,则将当前节点指向其右子节点,并继续比较。
5. 如果当前节点为空,则表示未找到目标节点,返回空。
以下是一个示例代码来演示二叉排序树的非递归查找:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def searchBST(root, val):
while root:
if val == root.val:
return root
elif val < root.val:
root = root.left
else:
root = root.right
return None
# 创建一个二叉排序树
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
# 在二叉排序树中查找值为2的节点
target = searchBST(root, 2)
if target:
print("找到了目标节点,值为:", target.val)
else:
print("未找到目标节点")
```
输出结果为:
```
找到了目标节点,值为: 2
```