二叉查找树的查找

一 点睛

因为二叉查找树的中序遍历的有序性，所以查找与二分法查找类似，每次都缩小查找范围，查找效率较高。

二 算法步骤

1 若二叉查找树为空，查找失败，则返回空。

2 若二叉查找树非空，则将待查找的关键字 x 与根节点关键字 T.data 进行比较

• 若 x== T.data，查找成功，则返回 T。

• 若 x<T.data，则递归查找左子树。

• 若 x>t.data，则递归查找右子树。

三 图解

1 二叉查找树如下，查找关键字 32

2 第一次查找

3 第二次查找

4 第三次查找

四 代码

// 二叉排序树的递归查找
static public TreeNode search(TreeNode root, int val) {
    // 若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
    if ((root == null) || val == root.val)
        return root;
    else if (val < root.val)
        return search(root.left, val); // 在左子树中继续查找
    else
        return search(root.right, val); // 在右子树中继续查找
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }
}