二叉排序树的查找算法

二叉排序树的查找算法可以分为递归算法和非递归算法两种实现方式。

1. 递归算法实现：

首先将待查关键字key与根节点关键字t进行比较：

a. 如果key = t，则返回根节点指针。

b. 如果key < t，则进一步查找左子树。

c. 如果key > t，则进一步查找右子树。

重复以上步骤，直到找到关键字为止，或者查找到空节点，此时返回NULL。

递归算法实现的代码如下所示：

def search_bst(root, key):
    if not root or root.val == key:
        return root
    elif root.val > key:
        return search_bst(root.left, key)
    else:
        return search_bst(root.right, key)

2. 非递归算法实现：

非递归算法实现的思路与递归算法类似，只是使用循环代替递归实现。

具体实现过程如下：

a. 将待查关键字key与根节点关键字t进行比较。

b. 如果key = t，则返回根节点指针。

c. 如果key < t，则进一步查找左子树。

d. 如果key > t，则进一步查找右子树。

e. 重复以上步骤，直到找到关键字为止，或者查找到空节点，此时返回NULL。

非递归算法实现的代码如下所示：

def search_bst(root, key):
    while root:
        if root.val == key:
            return root
        elif root.val > key:
            root = root.left
        else:
            root = root.right
    return None