How to implement binary search tree algorithm using java

How to use Java to implement the binary search tree algorithm

The binary search tree (Binary Search Tree, referred to as BST) is a commonly used data structure that can efficiently Implement operations such as insertion, deletion and search. This article will introduce how to use Java to implement a binary search tree and provide corresponding code examples.

1. Definition of binary search tree

Binary search tree is an ordered tree with the following characteristics:

1. Each node has a Unique key value.
2. The key value of the left subtree is smaller than the key value of the node, and the key value of the right subtree is greater than the key value of the node.
3. The left subtree and right subtree are also binary search trees.

2. Implement the node class of the binary search tree

First, we define a node class of the binary search tree, including the key value and the references of the left and right child nodes. The code is as follows:

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

In this node class, we save the key value of the node through the data field, and the left and right fields are saved respectively. References to left and right child nodes.

3. Implement the insertion operation of the binary search tree

Next, we implement the insertion operation of the binary search tree. The insertion operation determines the insertion position of the node by comparing the key value size of the node. If the key value is smaller than the current node, it is inserted into the left subtree, otherwise it is inserted into the right subtree. The code is as follows:

class BinarySearchTree {
    Node root;

    // 插入操作
    public void insert(int key) {
        root = insertRec(root, key);
    }

    private Node insertRec(Node root, int key) {
        // 如果树为空，创建一个新的节点
        if (root == null) {
            root = new Node(key);
            return root;
        }

        // 否则，递归地插入节点到左子树或右子树
        if (key < root.data)
            root.left = insertRec(root.left, key);
        else if (key > root.data)
            root.right = insertRec(root.right, key);

        return root;
    }
}

In the insertion operation, we first determine whether the tree is empty. If it is empty, create a new node as the root node. Otherwise, recursively insert into the left subtree or right subtree by comparing the size relationship between the key value and the current node.

4. Implement the search operation of the binary search tree

The search operation of the binary search tree is relatively simple. It compares the size relationship between the key value and the node step by step until a match or encounter is found. until empty nodes. The code is as follows:

class BinarySearchTree {
    ...

    // 查找操作
    public boolean contains(int key) {
        return containsRec(root, key);
    }

    private boolean containsRec(Node root, int key) {
        // 树为空或者找到匹配节点
        if (root == null || root.data == key)
            return (root != null);

        // 比较键值与当前节点
        if (key < root.data)
            return containsRec(root.left, key);
        else
            return containsRec(root.right, key);
    }
}

In the search operation, we first determine whether the tree is empty or whether the current node matches. Returns true if there is a match, otherwise recursively searches the left or right subtree by comparing the size of the key value with the current node.

5. Code for testing the binary search tree

Finally, we write code to test the binary search tree we implemented. The code is as follows:

public class Main {
    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();

        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        System.out.println(tree.contains(30));
        System.out.println(tree.contains(90));
    }
}

The running result is:

true
false

Here we insert some nodes into the tree by calling the insert operation. Then, we call the find operation to find nodes with key values ​​30 and 90 respectively. The result returned is whether the insertion operation was successful.

Through the above steps, we successfully implemented the binary search tree algorithm using Java and implemented the insertion and search operations. In practical applications, binary search trees can also support functions such as deletion operations, pre-order, in-order and post-order traversal. Readers can further expand the implementation according to specific needs.

The above is the detailed content of How to implement binary search tree algorithm using java. For more information, please follow other related articles on the PHP Chinese website!