天天看點
傳回

二叉搜尋樹(Binary Search Tree)（Java實作）

@

目錄

  • 1、二叉搜尋樹
    • 1.1、 基本概念
    • 1.2、樹的節點（BinaryNode）
    • 1.3、構造器和成員變量
    • 1.3、公共方法（public method）
    • 1.4、比較函數
    • 1.5、contains 函數
    • 1.6、findMin
    • 1.7、findMax
    • 1.8、insert
    • 1.9、remove
  • 二、完整代碼實作（Java）

1、二叉搜尋樹

1.1、 基本概念

二叉樹的一個性質是一棵平均二叉樹的深度要比節點個數N小得多。分析表明其平均深度為\(\mathcal{O}(\sqrt{N})\),而對于特殊類型的二叉樹，即二叉查找樹(binary search tree),其深度的平均值為\(\mathcal{O}(log N)\)。

二叉查找樹的性質： 對于樹中的每個節點X，它的左子樹中所有項的值小于X中的項，而它的右子樹中所有項的值大于X中的項。

由于樹的遞歸定義，通常是遞歸地編寫那些操作的例程。因為二叉查找樹的平均深度為\(\mathcal{O}(log N)\)，是以一般不必擔心棧空間被用盡。

1.2、樹的節點（BinaryNode）

二叉查找樹要求所有的項都能夠排序，有兩種實作方式；

  1. 對象實作接口 Comparable, 樹中的兩項使用compareTo方法進行比較；
  2. 使用一個函數對象，在構造器中傳入一個比較器；

本篇文章采用了構造器重載，并定義了myCompare方法，使用了泛型，是以兩種方式都支援，在後續的代碼實作中可以看到。

節點定義：

/**
     * 節點
     *
     * @param <AnyType>
     */
    private static class BinaryNode<AnyType> {
        BinaryNode(AnyType theElement) {
            this(theElement, null, null);
        }

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

        AnyType element; // the data in the node
        BinaryNode<AnyType> left; // Left child
        BinaryNode<AnyType> right; // Right child
    }

1.3、構造器和成員變量 

private BinaryNode<AnyType> root;
    private Comparator<? super AnyType> cmp;

    /**
     * 無參構造器
     */
    public BinarySearchTree() {
        this(null);
    }

    /**
     * 帶參構造器，比較器
     *
     * @param c 比較器
     */
    public BinarySearchTree(Comparator<? super AnyType> c) {
        root = null;
        cmp = c;
    }

關于比較器的知識可以參考下面這篇文章：

Java中Comparator的使用

關于泛型的知識可以參考下面這篇文章：

如何了解 Java 中的 <T extends Comparable<? super T>>

1.3、公共方法（public method）

主要包括插入，删除，找到最大值、最小值，清空樹，檢視元素是否包含；

/**
     * 清空樹
     */
    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public boolean contains(AnyType x){
        return contains(x,root);
    }

    public AnyType findMin(){
        if (isEmpty()) throw new BufferUnderflowException();
        return findMin(root).element;
    }

    public AnyType findMax(){
        if (isEmpty()) throw new BufferUnderflowException();
        return findMax(root).element;
    }

    public void insert(AnyType x){
        root = insert(x, root);
    }

    public void remove(AnyType x){
        root = remove(x,root);
    }

1.4、比較函數

如果有比較器，就使用比較器，否則要求對象實作了Comparable接口；

private int myCompare(AnyType lhs, AnyType rhs) {
        if (cmp != null) {
            return cmp.compare(lhs, rhs);
        } else {
            return lhs.compareTo(rhs);
        }
    }

1.5、contains 函數

本質就是一個樹的周遊；

private boolean contains(AnyType x, BinaryNode<AnyType> t) {
        if (t == null) {
            return false;
        }

        int compareResult = myCompare(x, t.element);
        if (compareResult < 0) {
            return contains(x, t.left);
        } else if (compareResult > 0) {
            return contains(x, t.right);
        } else {
            return true;
        }
    }

1.6、findMin

因為二叉搜尋樹的性質，最小值一定是樹的最左節點,要注意樹為空的情況。

/**
     * Internal method to find the smallest item in a subtree
     * @param t the node that roots the subtree
     * @return node containing the smallest item
     */
    private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
        if (t == null) {
            return null;
        }
        if (t.left == null) {
            return t;
        }
        return findMin(t.left);
    }

1.7、findMax

最右節點；

/**
     * Internal method to find the largest item in a subtree
     * @param t the node that roots the subtree
     * @return the node containing the largest item
     */
    private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t){
        if (t == null){
            return null;
        }
        if (t.right == null){
            return t;
        }
        return findMax(t.right);
    }

1.8、insert

這個主要是根據二叉搜尋樹的性質，注意當樹為空的情況，就可以加入新的節點了，還有當該值已經存在時，預設不進行操作；

/**
     * Internal method to insert into a subtree
     * @param x the item to insert
     * @param t the node that roots the subtree
     * @return the new root of the subtree
     */
    private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t){
        if (t == null){
            return new BinaryNode<>(x,null,null);
        }
        int compareResult = myCompare(x,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;
    }

1.9、remove

二叉搜尋樹(Binary Search Tree)（Java實作）

注意當空樹時，傳回null；

最後一個三元表達式，是在之前已經排除掉節點有兩個兒子的情況下使用的。

/**
     * Internal method to remove from a subtree
     * @param x the item to remove
     * @param t the node that roots the subtree
     * @return the new root of the subtree
     */
    private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t){
        if (t == null){
            return t; // Item not found ,do nothing
        }
        int compareResult = myCompare(x,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;
    }

二、完整代碼實作（Java） 

/**
 * @author LongRookie
 * @description: 二叉搜尋樹
 * @date 2021/6/26 19:41
 */


import com.sun.source.tree.BinaryTree;

import java.nio.BufferUnderflowException;
import java.util.Comparator;

/**
 * 二叉搜尋樹
 */
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {

    /**
     * 節點
     *
     * @param <AnyType>
     */
    private static class BinaryNode<AnyType> {
        BinaryNode(AnyType theElement) {
            this(theElement, null, null);
        }

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

        AnyType element; // the data in the node
        BinaryNode<AnyType> left; // Left child
        BinaryNode<AnyType> right; // Right child
    }

    private BinaryNode<AnyType> root;
    private Comparator<? super AnyType> cmp;

    /**
     * 無參構造器
     */
    public BinarySearchTree() {
        this(null);
    }

    /**
     * 帶參構造器，比較器
     *
     * @param c 比較器
     */
    public BinarySearchTree(Comparator<? super AnyType> c) {
        root = null;
        cmp = c;
    }

    /**
     * 清空樹
     */
    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public boolean contains(AnyType x){
        return contains(x,root);
    }

    public AnyType findMin(){
        if (isEmpty()) throw new BufferUnderflowException();
        return findMin(root).element;
    }

    public AnyType findMax(){
        if (isEmpty()) throw new BufferUnderflowException();
        return findMax(root).element;
    }

    public void insert(AnyType x){
        root = insert(x, root);
    }

    public void remove(AnyType x){
        root = remove(x,root);
    }




    private int myCompare(AnyType lhs, AnyType rhs) {
        if (cmp != null) {
            return cmp.compare(lhs, rhs);
        } else {
            return lhs.compareTo(rhs);
        }
    }

    private boolean contains(AnyType x, BinaryNode<AnyType> t) {
        if (t == null) {
            return false;
        }

        int compareResult = myCompare(x, t.element);
        if (compareResult < 0) {
            return contains(x, t.left);
        } else if (compareResult > 0) {
            return contains(x, t.right);
        } else {
            return true;
        }
    }

    /**
     * Internal method to find the smallest item in a subtree
     * @param t the node that roots the subtree
     * @return node containing the smallest item
     */
    private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
        if (t == null) {
            return null;
        }
        if (t.left == null) {
            return t;
        }
        return findMin(t.left);
    }

    /**
     * Internal method to find the largest item in a subtree
     * @param t the node that roots the subtree
     * @return the node containing the largest item
     */
    private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t){
        if (t == null){
            return null;
        }
        if (t.right == null){
            return t;
        }
        return findMax(t.right);
    }

    /**
     * Internal method to remove from a subtree
     * @param x the item to remove
     * @param t the node that roots the subtree
     * @return the new root of the subtree
     */
    private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t){
        if (t == null){
            return t; // Item not found ,do nothing
        }
        int compareResult = myCompare(x,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;
    }

    /**
     * Internal method to insert into a subtree
     * @param x the item to insert
     * @param t the node that roots the subtree
     * @return the new root of the subtree
     */
    private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t){
        if (t == null){
            return new BinaryNode<>(x,null,null);
        }
        int compareResult = myCompare(x,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;
    }

}
Java資料結構與算法
上一篇: python中的array函數作用_在Python中內建傳回數組的函數
下一篇: Session與Cookie的筆記

繼續閱讀