In general, there are three types of searches in a tree:

  • Search minimum
  • Search maximum
  • Search for a specific value

We all know that the child on the left of the binary tree is worth the parent, and the child on the right is greater than or equal to the parent. So the way to find the minimum is to go through the left tree and find the minimum, and the same way to find the maximum is to go through the right tree and find the maximum.

Search minimum

function BinarySearchTree () {
    // Initialize the root node to null
    let root = null
    The Node class is used to create multiple independent nodes
    let Node = function (key) {
        this.key = key
        this.left = null
        this.right = null
    }
    
    // Find the minimum method, exposing a method to find the smallest node
    this.min = function () {
        return minNode(root); 
    } 
    let minNode = function (node) {
        let current = node;
        // Iteration node,
        while(current ! =null&& current.left ! =null) { 
            current = current.left; 
        }
        returncurrent.key; }}Copy the code

Search maximum

function BinarySearchTree () {
    // Initialize the root node to null
    let root = null
    The Node class is used to create multiple independent nodes
    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;
        // Iteration node,
        while(current ! =null&& current.right ! =null) { 
            current = current.right; 
        }
        returncurrent.key; }}Copy the code

Search for a specific value

function BinarySearchTree () {
    // Initialize the root node to null
    let root = null
    The Node class is used to create multiple independent nodes
    let Node = function (key) {
        this.key = key
        this.left = null
        this.right = null
    }
    
    // Search for a specific value
    this.search = function (key) {
        return searchNode(root, key); 
    } 
    // An auxiliary function, implemented recursively, that finds a particular value of a tree or any of its subtrees
    let searchNode = function (node, key) {
        // Check whether the node parameter exists. If it does, the search can proceed. Otherwise, return false
        if(! node) {return false
        }
        // If the key is smaller than the key of the current node node, continue the recursive search in the left subtree
        if (key < node.key) {
            return searchNode(node.left, key)
        } else if(key > node.key) {
        // If the key is larger than the key of the current node, search recursively in the right subtree
            return searchNode(node.right, key)
        } else {
        // Otherwise, the key is found. Return true if the key is found
            return true}}}Copy the code

conclusion

From the above three search methods, we can see: in the process of calling method search, the definition of binary search tree (BST) is strictly followed, that is, the left child node stores the data whose value is less than that of the parent node, and the right child node stores the data whose value is greater than or equal to that of the parent node. And by this rule, we can clear up whether we should look in the left subtree or the right subtree.