YouTip

Binary Search Tree Node Search

\\\\n

Binary search trees don't have indexes, so for the search operation on a binary search tree, we define a contain method here to determine whether the binary search tree contains a certain element, returning a boolean variable. This search operation is also a recursive process. The specific code implementation is as follows:

\\\\n

...

\\\\n

// Check if the binary search tree rooted at node contains a node with key value key, Using recursive algorithm\\\\nprivate boolean contain(Node node, Key key){\\\\n    if( node == null )\\\\n        return false;\\\\n    if( key.compareTo(node.key) == 0 )\\\\n        return true;\\\\n    else if( key.compareTo(node.key) node->key\\\\n        return contain( node.right , key );\\\\n}\\\\n

\\\\n

...

\\\\n

The following example searches for element 43 in a binary search tree

\\\\n

\\\\n

(1) Element 43 is larger than the root node 42, so we need to continue comparing at the right child node.

\\\\n

\\\\n

(2) Element 43 is smaller than 59, so we need to continue comparing at the left child node.

\\\\n

\\\\n

(3) Element 43 is smaller than 51, so we need to continue comparing at the left child node.

\\\\n

\\\\n

(4) Searching the left child node 43 of 51, it matches exactly, search ends.

\\\\n

If you need to find the value corresponding to the key, the code is as follows:

\\\\n

...

\\\\n

// Find the value corresponding to key in the binary search tree rooted at node, Recursive algorithm\\\\n// Ifvaluedoes not exist, then return NULL\\\\nprivate Value search(Node node, Key key){\\\\n    if( node == null )\\\\n        return null;\\\\n    if( key.compareTo(node.key) == 0 )\\\\n        return node.value;\\\\n    else if( key.compareTo(node.key) node->key\\\\n        return search( node.right, key );\\\\n}\\\\n

\\\\n

...

\\\\n

Java Example Code

\\\\n

Source Package Download:

\\\\n

## src/tutorial/binary/BinarySearchTreeSearch.java File Code:\\\\n\\\\npackage tutorial.binary;\\\\n\\\\n/**\\\\n * Binary search tree search\\\\n */\\\\npublic class BinarySearchTreeSearch<Key extends Comparable, Value>{\\\\n    // The nodes in the tree are private classes, The outside world does not need to know the specific implementation of binary search tree nodes\\\\n    private class Node {\\\\n        private Key key;\\\\n        private Value value;\\\\n        private Node left, right;\\\\n        public Node(Key key, Value value){\\\\n            this.key = key;\\\\n            this.value = value;\\\\n            left = right = null;\\\\n        }\\\\n    }\\\\n\\\\n    // Root node\\\\n    private Node root;\\\\n    // Number of nodes in the tree\\\\n    private int count;\\\\n\\\\n    // Constructor, Default construct an empty binary search tree\\\\n    public BinarySearchTreeSearch(){\\\\n        root = null;\\\\n        count = 0;\\\\n    }\\\\n\\\\n    // Return the number of nodes in the binary search tree\\\\n    public int size(){\\\\n        return count;\\\\n    }\\\\n\\\\n    // Return whether the binary search tree is empty\\\\n    public boolean isEmpty(){\\\\n        return count == 0;\\\\n    }\\\\n\\\\n    // Insert a new (key into the binary search tree, value)Key-value pair\\\\n    public void insert(Key key, Value value){\\\\n        root = insert(root, key, value);\\\\n    }\\\\n\\\\n    // Check if key exists in the binary search tree\\\\n    public boolean contain(Key key){\\\\n        return contain(root, key);\\\\n    }\\\\n\\\\n    // Search for the value corresponding to key in the binary search tree. If this value does not exist, then return null\\\\n    public Value search(Key key){\\\\n        return search( root , key );\\\\n    }\\\\n\\\\n    //********************\\\\n    //* Auxiliary function of binary search tree\\\\n    //********************\\\\n    // Into the binary search tree rooted at node, Insert node (key, value), Using recursive algorithm\\\\n    // Return the root of the binary search tree after inserting the new node\\\\n    private Node insert(Node node, Key key, Value value){\\\\n        if( node == null ){\\\\n            count ++;\\\\n            return new Node(key, value);\\\\n        }\\\\n\\\\n        if( key.compareTo(node.key) == 0 )\\\\n            node.value = value;\\\\n        else if( key.compareTo(node.key) node->key\\\\n            node.right = insert( node.right, key, value);\\\\n        re