6-7 二叉排序树查找操作

二叉排序树是一种特殊的二叉树，它的左子树中所有节点的值都小于它的根节点的值，而右子树中所有节点的值都大于它的根节点的值。因此，对于一棵二叉排序树来说，我们可以通过比较要查找的值和当前节点的值的大小关系，来决定是继续在左子树中查找还是在右子树中查找，直到找到该节点或者遍历到空节点为止。

具体的查找操作可以分为以下几步：

1. 初始化：将当前节点指向根节点。
2. 比较：将要查找的值与当前节点的值进行比较。
- 如果相等，则返回当前节点，查找成功。
- 如果比当前节点的值小，则将当前节点指向左子节点，继续进行比较操作。
- 如果比当前节点的值大，则将当前节点指向右子节点，继续进行比较操作。
3. 重复步骤 2 直到找到该节点或者遍历到空节点为止。
4. 如果遍历到空节点，则表示没有找到该节点，查找失败。

总的来说，二叉排序树的查找操作的时间复杂度为 O(log n)，其中 n 表示树中节点的个数。

相关问题

6-2 二叉排序树查找操作

二叉排序树（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表示右子节点的指针。

PTA6-2 查找二叉排序树

题目描述：

给定一棵二叉排序树和一个值，求该值在树中出现的次数。

输入格式：

第一行包含整数 n，表示树中节点个数。

接下来 n 行，每行包含一个整数，表示当前节点的值。

最后一行包含一个整数x，表示需要统计出现次数的值。

输出格式：

共一行，包含一个整数，表示该值在树中出现的次数。

输入样例：

5
2
1
2
3
4
2

输出样例：

2

算法1：

递归遍历，统计值出现的次数。

时间复杂度

平均时间复杂度为O(logn)，最坏时间复杂度为O(n)。

参考文献

Python 代码

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):

    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: bool
        """
        if not root:
            return 0

        if val == root.val:
            return 1 + self.searchBST(root.left, val) + self.searchBST(root.right, val)
        elif val < root.val:
            return self.searchBST(root.left, val)
        else:
            return self.searchBST(root.right, val)

算法2：

迭代遍历，统计值出现的次数。

时间复杂度

平均时间复杂度为O(logn)，最坏时间复杂度为O(n)。

参考文献

Python 代码

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):

    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: bool
        """
        if not root:
            return 0

        count = 0
        stack = [root]

        while stack:
            node = stack.pop()
            if node.val == val:
                count += 1
            if node.left and node.val >= val:
                stack.append(node.left)
            if node.right and node.val <= val:
                stack.append(node.right)

        return count