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

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

内容简介：二叉搜索树或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）？》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对码农网的支持！

查看所有标签

猜你喜欢:

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

码农书籍

Spring Cloud微服务实战

翟永超 / 电子工业出版社 / 2017-5 / 89

《Spring Cloud微服务实战》从时下流行的微服务架构概念出发，详细介绍了Spring Cloud针对微服务架构中几大核心要素的解决方案和基础组件。对于各个组件的介绍，《Spring Cloud微服务实战》主要以示例与源码结合的方式来帮助读者更好地理解这些组件的使用方法以及运行原理。同时，在介绍的过程中，还包含了作者在实践中所遇到的一些问题和解决思路，可供读者在实践中作为参考。《Sp......一起来看看《Spring Cloud微服务实战》这本书的介绍吧!

码农工具

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

Spring Cloud微服务实战

HTML 压缩/解压工具

JS 压缩/解压工具

MD5 加密