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);
}
           

结果：