数据结构-二分搜索树(java语言实现)

// 代码实现过程中使用到 java.util 中的包
import java.util.LinkedList;
import java.util.Queue;

public class BST<E extends Comparable<E>> {  // 二分搜索树中存放的数据是可比较的

    // 定义树的节点，由于使用时不需要关注具体的Node 类，所有使用内部类
    private class Node{
        E e;
        Node left;
        Node right;

        // 内部类的构造方法，默认生成的节点，左右子节点为 null
        public Node(E e){
            this.e = e;
            this.left = null;
            this.right = null;
        }
    }
     
    // 定义根节点
    private Node root;
    private int size;

    // 二叉搜索树的构造方法
    public BST(){
        this.root = null;
        this.size = 0;
    }

    // 获取树的容量
    public int size(){
        return this.size;
    }

    // 判断是否为空
    public boolean isEmpty(){
        return 0 ==  this.size;
    }

    // 添加元素
    public void add(E e){
        if (this.root==null){
            this.root = new Node(e);
            size++;
            return;
        }
        add(root,e);
    }

    // 递归实现添加
    private void add(Node node,E e){

        if (e.compareTo(node.e)==0){
            return;
        }else if (e.compareTo(node.e)<0 && node.left ==null){
            node.left = new Node(e);
            size++;
            return;
        }else if (e.compareTo(node.e)>0 && node.right ==null){
            node.right = new Node(e);
            size++;
            return;
        }

        if (e.compareTo(node.e)<0){
            add(node.left, e);
        }else {
            add(node.right, e);
        }
    }

    public boolean contains(E e){
        return contains(root,e);
    }

    private boolean contains(Node node, E e){

        if (node==null){
            return false;
        }else 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 preTraverse(String type){
        if (type.equals("pre"))
            preTraverse(root);
        else if (type.equals("in"))
            inTraverse(root);
        else if (type.equals("post"))
            postTraverse(root);
    }

    private void preTraverse(Node node){
        if (node==null){
            return;
        }else {
            System.out.println(node.e);
            preTraverse(node.left);
            preTraverse(node.right);
        }
    }

    // 中序
    private void inTraverse(Node node){
        if (node==null){
            return;
        }else {
            preTraverse(node.left);
            System.out.println(node.e);
            preTraverse(node.right);
        }
    }

    // 后序
    private void postTraverse(Node node){
        if (node==null){
            return;
        }else {
            preTraverse(node.left);
            preTraverse(node.right);
            System.out.println(node.e);
        }
    }

    // 层序
    public void levelTraverse(){
        Queue<Node> q = new LinkedList<>();
        ((LinkedList<Node>) q).add(root);
        while (!q.isEmpty()){
            Node cur = q.remove();
            System.out.println(cur.e);

            if (cur.left!=null)
                ((LinkedList<Node>) q).add(cur.left);
            if (cur.right!=null)
                ((LinkedList<Node>) q).add(cur.right);
        }
    }

    // 获取最小元素
    public E min(){
        if (size==0){
            throw new IllegalArgumentException("isEmpty");
        }
        return min(root).e;
    }

    public Node min(Node node){
        if (node.left==null){
            return node;
        }else
            return min(node.left);
    }
    // 获取最大元素
    public E max(){
        if (size==0){
            throw new IllegalArgumentException("isEmpty");
        }
        return max(root).e;
    }

    public Node max(Node node){
        if (node.right==null){
            return node;
        }else
            return min(node.right);
    }

    public E removeMin(){
        E ret = min();
        removeMin(root);
        return ret;
    }

    private Node removeMin(Node node){
        if (node.left==null){
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }

    public E removeMax(){
        E ret = max();
        removeMax(root);
        return ret;
    }

    private Node removeMax(Node node){
        if (node.right==null){
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }

        node.right = removeMin(node.right);
        return node;
    }

    // 删除元素
    public void remove(E e){
        root = remove(root , e);
    }


    private Node remove(Node node, E e){
        if (node==null){
            return null;
        }
        if (e.compareTo(node.e)<0){
            node.left = remove(node.left, e);
            return node;
        }else if (e.compareTo(node.e)>0){
            node.right = remove(node.right, e);
            return node;
        }else {
            if (node.left==null){
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }

            if (node.right==null){
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }

            Node successor = min(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;
            return successor;
        }
    }


    public static void main(String[] args) {
        BST<Integer> integerBST = new BST<>();
        integerBST.add(3);
        integerBST.add(5);
        integerBST.add(2);
        integerBST.add(7);
        integerBST.add(9);
        integerBST.preTraverse("in");
//        integerBST.levelTraverse();
        integerBST.remove(3);
        integerBST.preTraverse("in");
    }
}

数据结构-二分搜索树(java语言实现)

原文：https://www.cnblogs.com/sugare/p/13189468.html