欢迎访问宙启技术站
智能推送

“Java函数实现二叉树的插入、查询和删除操作”

发布时间:2023-10-08 04:34:24

二叉树是一种常用的数据结构,它以树的形式组织数据,每个节点最多有两个子节点。在Java中,我们可以使用类来实现二叉树的插入、查询和删除操作。

首先,我们需要定义一个二叉树节点类:

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

接下来,我们可以定义一个二叉树类,并在其中实现插入、查询和删除操作。

class BinaryTree {
    Node root;

    public BinaryTree() {
        root = null;
    }

    public void insert(int value) {
        root = insertRecursive(root, value);
    }

    private Node insertRecursive(Node current, int value) {
        if (current == null) {
            return new Node(value);
        }

        if (value < current.value) {
            current.left = insertRecursive(current.left, value);
        } else if (value > current.value) {
            current.right = insertRecursive(current.right, value);
        }

        return current;
    }

    public boolean contains(int value) {
        return containsRecursive(root, value);
    }

    private boolean containsRecursive(Node current, int value) {
        if (current == null) {
            return false;
        }

        if (value == current.value) {
            return true;
        }

        return value < current.value
                ? containsRecursive(current.left, value)
                : containsRecursive(current.right, value);
    }

    public void delete(int value) {
        root = deleteRecursive(root, value);
    }

    private Node deleteRecursive(Node current, int value) {
        if (current == null) {
            return null;
        }

        if (value == current.value) {
            // Case 1: No child
            if (current.left == null && current.right == null) {
                return null;
            }

            // Case 2: Single child
            if (current.right == null) {
                return current.left;
            }

            if (current.left == null) {
                return current.right;
            }

            // Case 3: Two children
            int smallestValue = findSmallestValue(current.right);
            current.value = smallestValue;
            current.right = deleteRecursive(current.right, smallestValue);
            return current;
        }

        if (value < current.value) {
            current.left = deleteRecursive(current.left, value);
            return current;
        }

        current.right = deleteRecursive(current.right, value);
        return current;
    }

    private int findSmallestValue(Node root) {
        return root.left == null ? root.value : findSmallestValue(root.left);
    }
}

现在,我们可以使用这个二叉树类来进行插入、查询和删除操作了:

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

        tree.insert(5);
        tree.insert(2);
        tree.insert(8);
        tree.insert(1);
        tree.insert(7);

        System.out.println(tree.contains(1)); // true
        System.out.println(tree.contains(3)); // false

        tree.delete(2);
        System.out.println(tree.contains(2)); // false
    }
}

以上就是使用Java函数实现二叉树的插入、查询和删除操作的内容。通过这些函数,我们可以方便地操作二叉树的数据。