Java資料結構-二分搜尋樹的實作

二分搜尋樹是一種特殊的二叉樹，以放整型資料為例，左子樹放的元素都比根小，右子樹的元素都比根大，是以在查詢時效率是非常高的。需要利用二分搜尋樹進行存儲時要求存儲的對象是可比較的，是以需要繼承

Comparable

接口。接下來看下實作二分搜尋樹所需要的方法：

BST()

無參構造

size()

傳回二分搜尋樹的元素個數

isEmpty()

判斷是否為空

add(E e)

使用者當使用這個二分搜尋樹時調用的添加元素的方法

add(Node node,E e)

實際添加元素的方法，傳入需要添加元素的根節點和添加的元素

contains(E e)

使用者當使用這個二分搜尋樹時判斷是否包含某元素的方法

contains(E e,Node node)

實際判斷某樹是否包含某元素的方法

preOrder()

使用者調用先序周遊的方法

preOrder(Node node)

實際的先序周遊方法

inOrder()

使用者調用中序周遊的方法

inOrder(Node node)

實際調用的中序周遊的方法

postOrder()

使用者調用後序周遊的方法

postOrder(Node node)

實際調用中序周遊的方法

generateBSTString(Node node, int depth, StringBuilder res)

展示二分搜尋樹時需要調用的方法

generateDepthString(int depth)

展示二分搜尋樹時需要調用的方法

toString()

二分搜尋樹還需要使用一個節點類，這裡把節點類以内部類的形式放在了樹中。代碼如下：

/**
 * @Author: Cui
 * @Date: 2020/7/13
 * @Description:
 */
public class BST<E extends Comparable<E>> {

    private class Node{
        E e;
        Node left,right;

        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
        }
    }

    //根節點
    private Node root;
    //記錄結點個數
    private int size;

    public BST(){
        root = null;
        size = 0;
    }

    //擷取樹中結點的個數
    public int size(){
        return size;
    }

    //判斷是否為空
    public boolean isEmpty(){
        return size == 0;
    }

    //添加元素
    public void add(E e){
        root = add(root,e);
    }

    private Node add(Node node,E e){
        if(node == null){
            size++;
            return new Node(e);
        }
        if(e.compareTo(node.e) < 0){
            node.left = add(node.left, e);
        }else {
            node.right = add(node.right, e);
        }
        return node;
    }

    //判斷是否包含元素e
    public boolean contains(E e){
        return contains(root,e);
    }

    private boolean contains(Node node,E e){
        if(node == null){
            return false;
        }
        if(e.compareTo(node.e) == 0){
            return true;
        }else if(e.compareTo(node.e) < 0){
            return contains(node.left, e);
        }else {
            return contains(node.right,e);
        }
    }

    //先序周遊
    public void preOrder(){
        preOrder(root);
    }

    public void preOrder(Node node){

        if(node != null){
            System.out.println(node.e);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    //中序周遊
    public void inOrder(){
        inOrder(root);
    }

    private void inOrder(Node node) {
        if(node != null) {
            inOrder(node.left);
            System.out.println(node.e);
            inOrder(node.right);
        }
    }
    //後序周遊
    public void postOrder(){
        postOrder(root);
    }
    private void postOrder(Node node){
        if(node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.e);
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateBSTString(root,0,res);
        return res.toString();
    }

    private void generateBSTString(Node node, int depth, StringBuilder res) {
        if(node == null){
            res.append(generateDepthString(depth)+"null\n");
            return;
        }
        res.append(generateDepthString(depth) + node.e +"\n");
        generateBSTString(node.left,depth+1,res);
        generateBSTString(node.right,depth+1,res);
    }

    private String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < depth; i++){
            res.append("--");
        }
        return res.toString();
    }
}
           

測試

public static void main(String[] args) {
        BST<Integer> bst = new BST<>();
        int[] nums = {5,3,6,8,4,2};
        for(int num : nums){
            bst.add(num);
        }
        System.out.println("    5");
        System.out.println("   / \\");
        System.out.println("  3    6");
        System.out.println(" / \\    \\");
        System.out.println("2   4    8");
        System.out.println("先序周遊：");
        bst.preOrder();
        System.out.println("\n中序周遊：");
        bst.inOrder();
        System.out.println("\n後序周遊：");
        bst.postOrder();
        System.out.println();
        System.out.println(bst);
}
           

結果：