如何在Java中实现二叉搜索树（ binary search tree）？

栏目: 编程工具 · 发布时间: 7年前

内容简介：二叉搜索树或BST是一种流行的数据结构，用于保持元素的顺序。二叉搜索树是二叉树，其中左子节点的值小于或等于父节点，右子节点的值大于或等于父节点。由于它是二叉树，它只能有0，1或2个子节点。二叉搜索树之所以与众不同，是因为它能够减少诸如添加、删除和搜索（也称为插入、删除和查找）等基本操作的时间复杂性。在BST中，所有这些操作（插入，删除和查找）都可以在O（log（n））时间内执行。这种速度提高的原因是由于二叉搜索树的独特属性，对于每个节点，左子节点中的数据小于（或等于），右子节点中的数据大于（或等于）到所述节

二叉搜索树或BST是一种流行的数据结构，用于保持元素的顺序。二叉搜索树是二叉树，其中左子节点的值小于或等于父节点，右子节点的值大于或等于父节点。由于它是二叉树，它只能有0，1或2个子节点。二叉搜索树之所以与众不同，是因为它能够减少诸如添加、删除和搜索（也称为插入、删除和查找）等基本操作的时间复杂性。在BST中，所有这些操作（插入，删除和查找）都可以在O（log（n））时间内执行。这种速度提高的原因是由于二叉搜索树的独特属性，对于每个节点，左子节点中的数据小于（或等于），右子节点中的数据大于（或等于）到所述节点中的数据。

在编程面试中，您将看到许多基于二叉搜索树的数据结构和算法问题，例如：检查二叉树是否是BST？或者，编写一个程序来检查BST是否平衡。为了解决这个问题，您必须知道如何在 Java 中实现BST。

在这，我将教您如何在Java中实现二叉搜索树，您可以使用它来解决任何二叉搜索树或基于二叉树的编码问题。

Java中的二叉搜索树

在这里，您将学习如何创建具有整数节点的二叉搜索树。我使用泛型不仅仅是为了使代码简单，如果您愿意，可以将问题扩展到使用泛型，这将允许您创建一个字符串、整数、浮点或双精度的二叉树。记住，确保BST的节点必须实现Comparable接口。这是许多Java程序员在尝试使用泛型实现二叉搜索树时容易忘记的。

这里是Java中的二叉搜索树的实现。这只是一个结构，我们随后将添加方法在二叉搜索树中添加节点，从二叉搜索树中删除节点，并在后续部分中从BST中查找节点。

在这个实现中，我创建了一个Node类，它类似于我们的链表节点类，在向您展示如何在Java中实现链表时创建的。它有一个数据元素，一个整数和一个Node引用，指向二叉树中的另一个节点。

我还创建了四个基本功能，如下所示：

getRoot(), 返回二叉树的根

isEmpty(), 用于检查二叉搜索树是否为空

size(), 查找BST中的节点总数

clear(), 清除BST

以下是使用Java创建二叉搜索树或BST的示例代码，不使用任何第三方库。

<b>import</b> java.util.Stack;

<font><i>/**
 * Java Program to implement a binary search tree. A binary search tree is a
 * sorted binary tree, where value of a node is greater than or equal to its
 * left the child and less than or equal to its right child.
 * 
 * @author WINDOWS 8
 *
 */</i></font><font>
<b>public</b> <b>class</b> BST {

    <b>private</b> <b>static</b> <b>class</b> Node {
        <b>private</b> <b>int</b> data;
        <b>private</b> Node left, right;

        <b>public</b> Node(<b>int</b> value) {
            data = value;
            left = right = <b>null</b>;
        }
    }

    <b>private</b> Node root;

    <b>public</b> BST() {
        root = <b>null</b>;
    }

    <b>public</b> Node getRoot() {
        <b>return</b> root;
    }

    </font><font><i>/**
     * Java function to check if binary tree is empty or not
     * Time Complexity of this solution is constant O(1) for
     * best, average and worst case. 
     * 
     * @return true if binary search tree is empty
     */</i></font><font>
    <b>public</b> <b>boolean</b> isEmpty() {
        <b>return</b> <b>null</b> == root;
    }

    
    </font><font><i>/**
     * Java function to return number of nodes in this binary search tree.
     * Time complexity of this method is O(n)
     * @return size of this binary search tree
     */</i></font><font>
    <b>public</b> <b>int</b> size() {
        Node current = root;
        <b>int</b> size = 0;
        Stack<Node> stack = <b>new</b> Stack<Node>();
        <b>while</b> (!stack.isEmpty() || current != <b>null</b>) {
            <b>if</b> (current != <b>null</b>) {
                stack.push(current);
                current = current.left;
            } <b>else</b> {
                size++;
                current = stack.pop();
                current = current.right;
            }
        }
        <b>return</b> size;
    }


    </font><font><i>/**
     * Java function to clear the binary search tree.
     * Time complexity of this method is O(1)
     */</i></font><font>
    <b>public</b> <b>void</b> clear() {
        root = <b>null</b>;
    }

}
</font>

以上所述就是小编给大家介绍的《如何在Java中实现二叉搜索树（ binary search tree）？》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对码农网的支持！

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

Numerical Recipes 3rd Edition

William H. Press、Saul A. Teukolsky、William T. Vetterling、Brian P. Flannery / Cambridge University Press / 2007-9-6 / GBP 64.99

Do you want easy access to the latest methods in scientific computing? This greatly expanded third edition of Numerical Recipes has it, with wider coverage than ever before, many new, expanded and upd......一起来看看《Numerical Recipes 3rd Edition》这本书的介绍吧!

码农工具

CSS 压缩/解压工具

在线压缩/解压 CSS 代码

JSON 在线解析

在线 JSON 格式化工具