基本思路

package com.mao.dataStructure.tree;

import com.mao.dataStructure.tree.printer.BinaryTreeInfo;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @ClassName: BinarySearchTree
 * @Description: 二叉搜索树
 * @Author 毛毛
 * @CreateDate 2021/07/21/周三 16:00
 * @Version: v1.0
 */
public class BinarySearchTree<E> { // E extends Comparable<E> 节点存放的元素必须实现 Compareable接口
    /**
     * @param size 节点的个数
     */
    private int size;
    /**
     * @param root 根节点
     */
    private Node<E> root;

    /**
     * 定制比较 如果需要定制比较，则传递这个参数
     */
    private Comparator<E> comparator;


    public BinarySearchTree() {
    }

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    // 元素的数量
    public int size() {
        return size;
    }

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

    // 清空所有元素
    public void clear() {
        root = null;
        size = 0;
    }

    // 添加元素
    public void add(E element) {
        // 检查元素是否为null
        elementNotNullCheck(element);
        // root为null则为第一次插入节点
        if (root == null) {
            // 根节点的父亲是null
            root = new Node<>(element, null);
            return;
        }
        // 不是第一次添加节点
        /*
         * 那么需要找到当前要插入节点的父亲节点
         * 使用迭代法
         * */
        Node<E> node = root;
        // 当前插入节点的父节点
        Node<E> parent = root; // 默认情况下根节点就是父节点
        int cmp = 0; // 记录需要插入的位置
        while (node != null) {
            cmp = compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                // 当前插入的节点大于父节点
                node = node.right;
            } else if (cmp < 0) {
                // 当前插入的节点小于父节点
                node = node.left;
            } else {
                // 节点相同
                // 节点相同时：建议覆盖
                node.element = element;
                return; // 不需要插入了
            }
        }
        //    要插入的节点
        Node<E> curr = new Node<>(element, parent);
        //    查看到底插入到父节点的那个位置
        if (cmp > 0) {
            // 插入到父节点的右子节点
            parent.right = curr;
        } else if (cmp < 0) {
            // 插入到父节点的左子节点
            parent.left = curr;
        } //else{
        // 要插入的节点和父节点相同
        //}
        // 元素个数加一
        size++;
    }

    /**
     * 根据元素删除节点
     *
     * @param element
     */
    // 删除元素
    public void remove(E element) {
        remove(getNode(element));
    }

    /**
     * 移出指定的节点
     *
     * @param node
     */
    private void remove(Node<E> node) {
        // 节点不存在，直接返回
        if (node == null) return;
        // 链表长度减一
        size--;
        // 左右子树都存在，说明这个节点的度为2
        if (node.hasTowChildren()) {
            // 找到当前节点的前驱节点或者后继节点，取其中的值（element）来取代要删除节点的值
            // 这里使用找后继节点
            Node<E> successor = successor(node);
            // 用后继节点的值覆盖当前节点（度为2）的值
            node.element = successor.element;
            // 删除后继节点，我们让node节点指向后继节点successor
            node = successor;
            // 我们最后让node直接赋值为它的后继节点，这样node的度也变成了1或者0，和下面的处理方式一样了
        }

        // 删除node节点（node的度必然是1或者0）
        // 如果node现在是叶子节点，度为0 则左右子树都不存在 都为null
        // 如果node是度为1的节点，左子树存在，或者右子树存在，赋值不为空的子树
        Node<E> replacement = node.left != null ? node.left : node.right;

        // 进入if语句 说明node节点度为1
        if (replacement != null) {
            // 删除度为1的节点，就是让子节点取代自己

            // 更改parent
            replacement.parent = node.parent;

            if (node.parent == null) {
                // 要删除的度为1的节点刚好是根节点
                root = replacement;
            }
            // 更改parent的left和right
            // 判断要删除的node节点是node父节点的左子树还是右子树
            else if (node == node.parent.left) {
                node.parent.left = replacement;
            }
            // 下面的if条件可以省略。可以直接else
            else if (node == node.parent.right) {
                node.parent.right = replacement;
            }
        }
        // node是叶子节点  也是根节点
        else if (node.parent == null) {
            // 要删除的节点没有父节点，且这节点还是叶子节点，说明要删除的节点就是根节点
            root = null;
        }
        // node是叶子节点  不是根节点
        else {
            // 判断当前要删除的节点是父节点的左子树还是右子树
            if (node == node.parent.left) {
                node.parent.left = null;
            } else {
                node.parent.right = null;
            }
        }
    }

    /**
     * 根据元素获取所在的节点
     *
     * @param element
     * @return
     */
    private Node<E> getNode(E element) {
        Node<E> node = root;
        while (node != null) {
            int cmp = compare(element, node.element);
            if (cmp > 0) {
                // 要删除的节点在当前节点的右子树上
                node = node.right;
            } else if (cmp < 0) {
                // 要删除的节点在当前节点的左子树上
                node = node.left;
            } else {
                // 当前节点就是要删除的节点
                return node;
            }
        }
        // node = null 说明没找到，这个元素不存在
        return null;
    }

    // 是否包含某元素
    public boolean contains(E element) {
        return getNode(element) != null;
    }


    public void preorderTraversal() {
        preorderTraversal(root);
    }

    /**
     * 前序遍历 先访问根节点，然后左子节点，然后右子节点
     *
     * @param node 当前遍历树的根节点
     */
    private void preorderTraversal(Node<E> node) {
        if (node == null) return;
        // 递归方式遍历
        System.out.println(node.element);
        preorderTraversal(node.left);
        preorderTraversal(node.right);
        //    迭代方式遍历
        // while (node!=null){
        //     System.out.println(node.element);
        //
        // }
    }

    public void preorderTraversal(Visitor<E> visitor) {
        if (root == null || visitor == null) return;
        preorderTraversal(root, visitor);
    }

    private void preorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null) return;
        // 递归方式遍历
        visitor.visit(node.element);
        preorderTraversal(node.left);
        preorderTraversal(node.right);
        //    迭代方式遍历
        // while (node!=null){
        //     System.out.println(node.element);
        //
        // }
    }

    /**
     * 中序遍历
     */
    public void inorderTraversal() {
        inorderTraversal(root);
    }

    /**
     * 中序遍历
     *
     * @param node
     */
    private void inorderTraversal(Node<E> node) {
        if (node == null) return;
        inorderTraversal(node.left);
        System.out.println(node.element);
        inorderTraversal(node.right);
    }

    /**
     * 后序遍历
     */
    public Queue<E> postorderTraversal() {
        Queue<E> queue = new LinkedList<>();
        postorderTraversal(root, queue);
        return queue;
    }

    /**
     * 后序遍历
     *
     * @param node
     */
    private void postorderTraversal(Node<E> node, Queue<E> queue) {
        if (node == null) return;
        // postorderTraversal(node.left);
        // postorderTraversal(node.right);
        // System.out.println(node.element);
        Stack<Node<E>> stack = new Stack<>();
        Node<E> curr = root;
        while (curr != null || !stack.isEmpty()) {
            //    左子树入栈
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            //    获取当前栈顶元素
            Node<E> top = stack.peek();
            if (top.right == null) {
                // 没有右子树，则当前元素遍历到最后了，可以入队
                queue.add(stack.pop().element);
            } else {
                // 有右子树，则先保存当前结点的右子节点并把当前结点的右子节点置为null
                // (下次查看当前结点时就会知道右子节点已经遍历过，就可以将其加入结果集了),遍历当前结点右子树
                curr = top.right;
                top.right = null;
            }
        }
    }

    /**
     * 层序遍历 使用队列的思维
     *
     * @return
     */
    public Queue<E> LevelOrderTraversal() {
        if (root == null) return null;
        Queue<E> result = new LinkedList<>();
        Queue<Node<E>> queue = new LinkedList<>();
        // 根节点入队
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 出队
            Node<E> node = queue.poll();
            result.offer(node.element);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        return result;
    }

    /**
     * 按照指定的需要，对存储的数据进行操作
     *
     * @param visitor 具体的操作逻辑实现类
     */
    public void levelOrder(Visitor<E> visitor) {
        if (root == null || visitor == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 出队
            Node<E> node = queue.poll();
            // 执行用户需要的操作逻辑
            visitor.visit(node.element);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

    }

    /**
     * 获取当前二叉搜索树的高度
     *
     * @return
     */
    public int getTreeHeight() {
        return getNodeHeight(root);
    }

    public int getTreeHeight(boolean isIteration) {
        // 递归调用
        if (!isIteration) return getNodeHeight(root);
        // 迭代调用
        return getNodeHeightByIteration(root);

    }

    /**
     * 获取某个节点的高度  递归获取
     *
     * @return
     */
    private int getNodeHeight(Node<E> node) {
        // 当前节点为null 直接返回 0
        if (node == null) return 0;
        // 当前节点的高度为其左右子树中较高的加一
        return Math.max(getNodeHeight(node.left), getNodeHeight(node.right)) + 1;
    }

    /**
     * 获取某个节点的高度  迭代获取（层序遍历的思想）
     *
     * @return
     */
    private int getNodeHeightByIteration(Node<E> node) {
        // 当前节点为null 直接返回 0
        if (node == null) return 0;
        // 存储每层元素的个数 （默认根节点不为空，也就是一层，为空的情况已经考虑了）
        // 当这层的元素个数变为 0  的时候，这一层也就被访问完了
        int levelSize = 1;
        // 当前节点的高度为其左右子树中较高的加一
        int height = 0;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<E> curr = queue.poll();
            levelSize--;
            if (curr.left != null) queue.offer(curr.left);
            if (curr.right != null) queue.offer(curr.right);
            // 如果当前层数的元素 levelSize=0，也就是当前层访问完了
            // 那也就会进入下一层，下一层的元素个数也就是当前队列的长度
            if (levelSize == 0) {
                // 进入下一层，高度加一
                height++;
                // 该层的元素个数也就是当前队列的长度
                levelSize = queue.size();
            }
        }
        return height;
    }

    /**
     * 判断当前平衡二叉树是否是完全二叉树
     * 什么是完全二叉树： 叶子节点只会出现最后 2 层，且最后 1 层的叶子结点都靠左对齐
     *
     * @return
     */
    public boolean isComplete() {
        // 空树 不是完全二叉树
        if (root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        // 是否要求当前节点开始都为叶子节点
        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> curr = queue.poll();
            // 如果当前节点需要是叶子节点，但是当前节点却不是叶子节点，则肯定不是完全二叉树
            if (leaf && !curr.isLeaf()) return false;
            // 节点的度为 2 则按照顺序入队  左右子节点均存在
            // if (curr.left != null && curr.right != null) {
            if (curr.hasTowChildren()) { // 左子节点存在 右子节点存在并不会入队
                queue.offer(curr.left);
                queue.offer(curr.right);
            }
            // 存在度为1的节点，则一定不为完全二叉树
            // 存在右子树，没有左子树，肯定不是完全二叉树
            else if (curr.left == null && curr.right != null) {
                return false;
            }
            // 存在左子树，不存在右子树 则该节点后面的所有节点，全都是叶子节点
            // if (curr.left != null && curr.right == null)
            // 当前节点 没有左子树和右子树，则当前节点以及后面的所有节点，都是叶子节点
            // if(curr.left==null && curr.right==null)

            // 上面两种情况进行了合并（总共就四种可能性）
            else {
                // 接下来的所有节点都必须是叶子节点
                leaf = true;
                // 如果当前节点的左子节点存在，则入队
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
            }
        }
        return true;
    }

    /**
     * 判断是否为完全二叉树的代码整理(减少了重复判断)
     *
     * @return
     */
    public boolean isComplete2() {
        // 空树 不是完全二叉树
        if (root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        // 是否要求当前节点开始都为叶子节点
        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> curr = queue.poll();
            // 如果当前节点需要是叶子节点，但是当前节点却不是叶子节点，则肯定不是完全二叉树
            if (leaf && !curr.isLeaf()) return false;
            // 存在左子树 直接入队
            if (curr.left != null) {
                queue.offer(curr.left);
            } else if (curr.right != null) { // curr.left == null 了
                // 左子树为空 右子树不为空，不可能是完全二叉树
                return false;
            }
            // 存在右子树 直接入队
            if (curr.right != null) {
                queue.offer(curr.right);
            } else {
                // 来到这里说明 右子节点为null 左子节点存在或者不存在
                // 则要求当前节点开始的后面的所有节点都为叶子节点
                leaf = true;
            }

        }
        return true;
    }

    /**
     * 获取当前节点的前驱节点
     * 前驱节点: 中序遍历时的当前节点的前一个节点
     * 二叉搜索树中，前驱节点就是前一个比它小的节点
     *
     * @param node
     * @return
     */
    private Node<E> predecessor(Node<E> node) {
        // 空树 直接返回
        if (node == null) return null;
        // 有左子树，前驱节点肯定在左子树上的最右的那个右子树
        Node<E> p = node.left;
        if (p != null) { // left.right.right....
            while (p.right != null) {
                p = p.right;
            }
            // p.right 为null
            return p;
        }
        // 左子树为null，则从父节点，祖父节点。。。中寻找前驱节点
        // 如果存在父节点，且当前节点是父节点的左子节点，则一直循环
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }
        // 来到这里，则不存在父节点 或者当前节点不是父节点的左子节点（也就是右子节点）
        // node.parent == null  || node != node.parent.left (node == node.parent.right)
        return node.parent;
    }

    /**
     * 找到当前节点的后继节点
     *
     * @param node
     * @return
     */
    private Node<E> successor(Node<E> node) {
        if (node == null) return null;
        // 右子树存在，则后继节点就是右子树的最左的那个左子节点
        // right.left.left.left...
        if (node.right != null) {
            Node<E> curr = node.right;
            while (curr.left != null) {
                curr = curr.left;
            }
            // 左子节点为null，直接返回当前节点，就是后继节点了
            return curr;
        }
        // 右子树不存在，找其父节点，如果父节点存在且当前节点是父节点的左子树
        // 则该父节点就是当前节点的后继节点
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }
        return node.parent;
    }


    /**
     * 参数不能为null的检查
     *
     * @param element
     */
    private void elementNotNullCheck(E element) {
        if (element == null) throw new IllegalArgumentException("参数不能为null element must not be null");
    }

    /**
     * 判断节点大小关系的方法
     *
     * @param ele1
     * @param ele2
     * @return 返回值为0 一样大 返回值小于 0 则 ele1 < ele2 返回值大于0 ele1>ele2
     */
    private int compare(E ele1, E ele2) {
        // 有比较器，则优先使用比较器的逻辑
        if (comparator != null) {
            return comparator.compare(ele1, ele2);
        }
        // 如果E这个类实现了 Comparable 接口，则调用实现类的具体比较逻辑
        // 强制转换为这个接口的实现类

        return ((Comparable<E>) ele1).compareTo(ele2);
    }


    /**
     * 访问器接口 提供一个外界对树上节点里存储的数据的操作的接口
     */
    public static interface Visitor<E> {
        void visit(E element);
    }


    /**
     * 内部类 树上的节点
     *
     * @param <E>
     */
    private static class Node<E> {
        // 节点存储的数据
        private E element;
        //    左子节点
        private Node<E> left;
        //    右子节点
        private Node<E> right;
        //    父节点
        private Node<E> parent;

        public Node(E element, Node<E> left, Node<E> right, Node<E> parent) {
            this.element = element;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }

        // 默认新节点的左子节点和右子节点都不存在
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public Node() {
        }

        /**
         * 当前节点是否是叶子节点
         *
         * @return
         */
        private boolean isLeaf() {
            return left == null && right == null;
        }

        /**
         * 当前节点是否有两个子节点
         *
         * @return
         */
        private boolean hasTowChildren() {
            return left != null && right != null;
        }
    }

}