Java实现二叉搜索树示例

什么是二叉搜索树

二叉搜索树（Binary Search Tree），又称为二叉查找树，是一种非常实用的数据结构。它具有以下特点：对于树中的每个节点X，它的左子树中所有项的值均小于X中的项，而它的右子树中所有项的值均大于X中的项。这种特性使得二叉搜索树在查找、插入和删除操作上具有很高的效率，平均时间为$O(logN)$。

使用Java实现一个基本的二叉搜索树

下面我们将通过Java代码示例来实现一个基本的二叉搜索树。

首先定义节点类BinaryNode：

private static class BinaryNode<AnyType> {
    AnyType element; // 节点的数据元素
    BinaryNode<AnyType> left; // 左子节点
    BinaryNode<AnyType> right; // 右子节点

    BinaryNode(AnyType theElement) {
        this(theElement, null, null);
    }

    BinaryNode(AnyType theElement, BinaryNode<AnyType> left, BinaryNode<AnyType> right) {
        element = theElement;
        this.left = left;
        this.right = right;
    }
}

接下来是二叉搜索树的主要操作实现，包括插入、查找和删除：

public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
    private BinaryNode<AnyType> root; // 树的根节点

    public BinarySearchTree() {
        this.root = null;
    }

    // 插入操作
    public void insert(AnyType x) {
        root = insert(x, root);
    }

    private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
        if (t == null) {
            return new BinaryNode<>(x, null, null);
        }
        int compareResult = x.compareTo(t.element);
        if (compareResult < 0) {
            t.left = insert(x, t.left);
        } else if (compareResult > 0) {
            t.right = insert(x, t.right);
        } else {
            // Duplicate; do nothing
        }
        return t;
    }

    // 查找操作
    public boolean contains(AnyType x) {
        return contains(x, root);
    }

    private boolean contains(AnyType x, BinaryNode<AnyType> t) {
        if (t == null) {
            return false;
        }
        int compareResult = x.compareTo(t.element);
        if (compareResult < 0) {
            return contains(x, t.left);
        } else if (compareResult > 0) {
            return contains(x, t.right);
        } else {
            return true;
        }
    }

    // 删除操作
    public void remove(AnyType x) {
        root = remove(x, root);
    }

    private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
        if (t == null) {
            return t; // Item not found; do nothing
        }
        int compareResult = x.compareTo(t.element);
        if (compareResult < 0) {
            t.left = remove(x, t.left);
        } else if (compareResult > 0) {
            t.right = remove(x, t.right);
        } else if (t.left != null && t.right != null) {
            // Two children
            t.element = findMin(t.right).element;
            t.right = remove(t.element, t.right);
        } else {
            t = (t.left != null) ? t.left : t.right;
        }
        return t;
    }

    private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
        if (t == null) {
            return null;
        }
        if (t.left == null) {
            return t;
        }
        return findMin(t.left);
    }
}

上面的代码中，我们实现了二叉搜索树的基本功能。插入操作利用了二叉搜索树的性质，即新节点的值小于当前节点则插入左子树，否则插入右子树。查找操作同样递归地在左子树或右子树中查找目标值。删除操作较为复杂，需要考虑待删除节点的子节点情况：无子节点、一个子节点和两个子节点。对于有两个子节点的情况，我们采用将待删除节点替换为其右子树的最小值，然后递归删除该最小值节点。

使用示例

public static void main(String[] args) {
    BinarySearchTree<Integer> bst = new BinarySearchTree<>();
    bst.insert(5);
    bst.insert(3);
    bst.insert(7);
    bst.insert(1);
    bst.insert(9);

    System.out.println(bst.contains(7)); // true
    System.out.println(bst.contains(8)); // false

    bst.remove(5);
    System.out.println(bst.contains(5)); // false
}

这段代码创建了一个二叉搜索树，并进行了插入、查找和删除操作。

总结

二叉搜索树在很多场景中都非常有用，例如快速查找和排序数据。然而，需要注意的是，如果数据插入的顺序不佳，可能会导致树退化成链表，从而失去高效的性能优势。因此，在实际应用中，可能需要考虑使用自平衡二叉搜索树（如AVL树或红黑树）来保证树的平衡性，维持高效的查找性能。

全文完。

原文地址：https://blog.csdn.net/zhuzi8849/article/details/142431714

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！