如何在Java中实现二叉搜索树( binary search tree)?

19-02-22 jdon
         

二叉搜索树或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的示例代码,不使用任何第三方库。

import java.util.Stack;

/**
 * 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
 *
 */
public class BST {

    private static class Node {
        private int data;
        private Node left, right;

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

    private Node root;

    public BST() {
        root = null;
    }

    public Node getRoot() {
        return root;
    }

    /**
     * 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
     */
    public boolean isEmpty() {
        return null == root;
    }

    
    /**
     * 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
     */
    public int size() {
        Node current = root;
        int size = 0;
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || current != null) {
            if (current != null) {
                stack.push(current);
                current = current.left;
            } else {
                size++;
                current = stack.pop();
                current = current.right;
            }
        }
        return size;
    }


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

}