数据结构之树（搜索树中的值）

这是我参与更文挑战的第28天，活动详情查看：更文挑战

通常来讲，在树中会有三种搜索类型：

• 搜索最小值
• 搜索最大值
• 搜索特定的值

我们都知道二叉树左侧的子节点值父节点，右侧的子节点值大于等于父节点。所以要搜索最小值就是遍历左侧树，找到最小值，同样的搜索最大值就是遍历右侧树，找到最大值。

搜索最小值

function BinarySearchTree () {
    // 初始化根节点为null
    let root = null
    // 声明节点Node类，用于创建多个独立的节点
    let Node = function (key) {
        this.key = key
        this.left = null
        this.right = null
    }
    
    // 搜索最小值方法,暴漏一个查找最小节点的方法
    this.min = function () {
        return minNode(root); 
    } 
    let minNode = function (node) {
        let current = node;
        // 迭代节点，
        while (current != null && current.left != null) { 
            current = current.left; 
        }
        return current.key; 
    }
    
}
复制代码

搜索最大值

function BinarySearchTree () {
    // 初始化根节点为null
    let root = null
    // 声明节点Node类，用于创建多个独立的节点
    let Node = function (key) {
        this.key = key
        this.left = null
        this.right = null
    }
    
    this.max = function () {
        return minNode(root); 
    } 
    let maxNode = function (node) {
        let current = node;
        // 迭代节点，
        while (current != null && current.right != null) { 
            current = current.right; 
        }
        return current.key; 
    }
    
}
复制代码

搜索特定的值

function BinarySearchTree () {
    // 初始化根节点为null
    let root = null
    // 声明节点Node类，用于创建多个独立的节点
    let Node = function (key) {
        this.key = key
        this.left = null
        this.right = null
    }
    
    // 搜索特定值
    this.search = function (key) {
        return searchNode(root, key); 
    } 
    // 辅助函数，递归实现，用来查找一颗树或者它的任意子树的一个特定的值
    let searchNode = function (node, key) {
        // 首先判断参数node是否存在，存在才可以进行接下来的查找操作，否则直接返回false，表示未找到
        if (!node) {
            return false
        }
        // 如果要找的键key比当前的节点node的键key小，那么继续在左侧子树上递归查找
        if (key < node.key) {
            return searchNode(node.left, key)
        } else if(key > node.key) {
        // 如果要找的键key比当前节点node的键key大的话，则在右侧子树上递归查找
            return searchNode(node.right, key)
        } else {
        // 否则，相等的话就说明找到了这个键key，返回true表示找到了
            return true
        }
    }
    
}
复制代码

总结

从上述三种查找方法，我们可以看到：在调用方法查找的过程中，严格遵循了二叉搜索树（BST）的定义，即左侧子节点存放值小于父节点的数据，右侧子节点存放值大于等于父节点的数据。根据这个规则，我们就可以清除的知道是该在左子树中查找还是在右子树中查找。