Java 中从头开始的二叉搜索树-java教程-PHP中文网

Java 中从头开始的二叉搜索树

WBOY

发布： 2024-07-12 11:25:13

转载

352人浏览过

java 中从头开始的二叉搜索树

简介
二叉搜索树 (bst) 是一种二叉树，其中每个节点最多有两个子节点，称为左子节点和右子节点。对于每个节点，左子树仅包含值小于该节点值的节点，右子树仅包含值大于该节点值的节点。 bst 用于高效的搜索、插入和删除操作。

为什么使用二叉搜索树？
bst 有几个优点：

高效搜索：搜索、插入、删除平均时间复杂度为o(log n)。
动态项目集：支持动态操作，与静态数组不同。
有序元素：bst 的中序遍历会产生按排序顺序排列的元素。
构建 bst 的分步指南
步骤一：定义节点结构
第一步是定义树中节点的结构。每个节点将具有三个属性：一个值、对左子节点的引用和对右子节点的引用。

public class treenode {
    int value;
    treenode left;
    treenode right;

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

登录后复制

第2步：使用构造函数创建bst类
接下来，我们创建 bst 类，其中包含对树根的引用以及插入元素的方法。

public class binarysearchtree {
    treenode root;

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

登录后复制

第三步：实现插入方法
要将元素插入 bst，我们需要找到新节点的正确位置。插入方法通常实现为递归函数。

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

private treenode insertrec(treenode root, int value) {
    // base case: if the tree is empty, return a new node
    if (root == null) {
        root = new treenode(value);
        return root;
    }

    // otherwise, recur down the tree
    if (value < root.value) {
        root.left = insertrec(root.left, value);
    } else if (value > root.value) {
        root.right = insertrec(root.right, value);
    }

    // return the (unchanged) node pointer
    return root;
}

登录后复制

可视化
为了更好地理解插入是如何工作的，让我们考虑一个例子。假设我们要在 bst 中插入以下数字序列：50, 30, 70, 20, 40, 60, 80。

登录后复制

  50
 /
30

登录后复制

  50
 /  \
30  70

登录后复制

登录后复制

插入40：

登录后复制

插入60

  50
 /  \
30  70
/ \  /

登录后复制

插入80：

  50
 /  \
30  70
/ \  / \

登录后复制

完整代码
这是创建 bst 和插入元素的完整代码：

public class BinarySearchTree {
    TreeNode root;

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

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

    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) {
            root = new TreeNode(value);
            return root;
        }

        if (value < root.value) {
            root.left = insertRec(root.left, value);
        } else if (value > root.value) {
            root.right = insertRec(root.right, value);
        }

        return root;
    }

    // Additional methods for traversal, search, and delete can be added here

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int value : values) {
            bst.insert(value);
        }

        // Add code to print or traverse the tree
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

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

登录后复制

以上就是Java 中从头开始的二叉搜索树的详细内容，更多请关注php中文网其它相关文章！