挑战：编写Java实现复杂算法示例

原创阳光穿透心脏的1/2处 2024-10-18 17:42 32阅读 0赞

这是一个使用Java实现二叉搜索树(Binary Search Tree, BST)的例子，其中包含了插入、查找和删除等复杂操作。

```java
public class BinarySearchTree {

// Node class to store data and reference to child node
    private static class Node {
        int value;
        Node left;
        Node right;

Node(int value) {
            this.value = value;
        }
    }

// Root of BST
    private Node root;

// Method to insert a new node with given value into the BST
    public void insert(int value) {
        root = insertRecursive(root, value);
    }

// Recursive helper function to insert a node
    private Node insertRecursive(Node node, int value) {
        // Base case: If the tree is empty, create a new root node
        if (node == null) {
            return new Node(value);
        }

// Decide whether to insert the value on the left or right subtree
        if (value < node.value) {
            node.left = insertRecursive(node.left, value));
        } else if (value > node.value) {
            node.right = insertRecursive(node.right, value));
        }

return node;
    }

// Method to search for a given value in the BST. Returns true if found, false otherwise.
    public boolean search(int value) {
        return searchRecursive(root, value);
    }

// Recursive helper function to search for a value
    private boolean searchRecursive(Node node, int value) {
        // Base case: If the tree is empty or the searched value is not present in any subtree, return false.
        if (node == null || node.value != value) {
            return false;
        }

// If the current node matches the searched value and both its children are also non-null, return true. This means we have found a match.
        return true;
    }

// Method to delete a given value from the BST. Returns true if deleted, false otherwise.
    public boolean delete(int value) {
        root = deleteRecursive(root, value));
        return search(value);  // Check if value is still present in the tree
    }

// Recursive helper function to delete a value
    private Node deleteRecursive(Node node, int value) {
        // Base case: If the tree is empty or the searched value is not present in any subtree, simply return null.
        if (node == null || node.value != value) {
            return null;
        }

// If the current node matches the searched value and both its children are also non-null, delete this node from the tree. For a binary search tree, deleting a node means adjusting the tree structure to maintain the property that each node's value is greater than or equal to any node in its left subtree.
        Node left = node.left;
        Node right = node.right;

// If the current node has only one child (left or right), replace the current node with its child. This ensures that the deleted node's parent takes over as the new child of the deleted node's parent.
        if (left != null) {
            node = left;  // Update the root to point to the left child
        } else if (right != null) {
            node = right;  // Update the root to point to the right child
        }

return node;
    }
}
```

这个例子中，我们实现了一个简单的二叉搜索树(BST)，并包含了插入、查找和删除等复杂操作。