[数据结构与算法]二叉树和二叉搜索树的java实现

二叉树的实现

原本的内容都放在二叉搜索树（BinarySearchTree）里面，今日重新看了一遍，强迫症让我把它分开了…以下~

package com.ssy.data_structure.tree;

import java.util.LinkedList;
import java.util.Queue;
/**
 * @Author 苏尔伯特
 * @Date 2021/11/28 22:17
 */
public abstract class BinaryTree<E> implements Tree<E> {

    protected Node<E> root;

    protected int size;

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        root = null;
        size = 0;
    }

    @Override
    public abstract void add(E e);

    @Override
    public abstract void remove(E e);

    protected void elementNotNullCheck(E e) {
        if (e == null) {
            throw new IllegalArgumentException("element must be not null");
        }
    }

    /**
     * 前序遍历
     */
    protected void preorderTraversal(BST.Visitor<E> visitor) {
        if (visitor == null) return;
        preorderTraversal(root, visitor);
    }

    /**
     * 以指定节点为根节点，前序遍历
     *
     * @param node 当前节点
     */
    private void preorderTraversal(Node<E> node, BST.Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        preorderTraversal(node.left, visitor);
        preorderTraversal(node.right, visitor);
    }

    /**
     * 中序遍历
     * 对于二叉搜索树而言，中序遍历要么是升序的，要么是降序的
     */
    protected void inorderTraversal(BST.Visitor<E> visitor) {
        if (visitor == null) return;
        inorderTraversal(root, visitor);
    }

    /**
     * 指定节点为根节点的中序遍历
     *
     * @param node 当前节点
     */
    private void inorderTraversal(Node<E> node, BST.Visitor<E> visitor) {
        // 此处的visitor.stop是用来终止递归的
        if (node == null || visitor.stop) return;
        inorderTraversal(node.left, visitor);

        // 若在上一行代码中，visitor.stop被赋值为true,就需要终止下面的过程
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        inorderTraversal(node.right, visitor);
    }


    /**
     * 后序遍历
     */
    protected void postorderTraversal(BST.Visitor<E> visitor) {
        if (visitor == null) return;
        postorderTraversal(root, visitor);
    }

    /**
     * 以指定节点为根节点，后序遍历
     *
     * @param node 当前节点
     */
    private void postorderTraversal(Node<E> node, BST.Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        postorderTraversal(node.left, visitor);
        postorderTraversal(node.right, visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
    }

    /**
     * 层序遍历,使用队列实现
     */
    protected void levelOrderTraversal(BST.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();
            boolean stop = visitor.visit(node.element);
            if (stop) return;

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    /**
     * 完全二叉树的判定：
     * 1. 度为1的节点只有左子树
     * 2. 度为1的节点个数要么是0，要么是1
     * 可以使用层序遍历
     */
    protected boolean isComplete() {
        if (root == null) {
            return false;
        }

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        boolean shouldBeLeaf = false;

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();

            if (shouldBeLeaf && !node.isLeaf()) return false;

            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                return false;
            }

            if (node.right != null) {
                queue.offer(node.right);
            } else {
                // 但凡是右子节点为空，那么接下来的节点必然是叶子节点
                shouldBeLeaf = true;
            }
        }
        return true;
    }

    /**
     * @return 二叉树高度
     */
    protected int height() {
        return height(root);
    }

    private int height(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    /**
     * 获取一个节点的前驱节点【中序遍历时的前一个节点】
     *
     * @param node 当前节点
     * @return 前驱节点
     */
    protected Node<E> predecessor(Node<E> node) {
        if (node == null) return null;
        Node<E> predecessor = node.left;
        // 前驱节点在左子树当中
        if (predecessor != null) {
            while (predecessor.right != null) {
                predecessor = predecessor.right;
            }
            return predecessor;
        }

        // 当前节点在祖辈节点的右子树中
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

        // 循环结束的两种情况,其需要返回的内容都等于node.parent
        return node.parent;
    }

    /**
     * 获取一个节点的后继节点【中序遍历时的后一个节点】
     *
     * @param node 当前节点
     * @return 后继节点
     */
    protected Node<E> successor(Node<E> node) {
        if (node == null) return null;
        Node<E> successor = node.right;
        if (successor != null) {
            while (successor.left != null) {
                successor = successor.left;
            }
            return successor;
        }
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }
        return node.parent;
    }

    /**
     * 访问器：在外部使用者调用遍历方法时，想对元素做什么操作，可以实现该接口
     */
    protected static abstract class Visitor<E> {

        /**
         * 当前访问器是否需要停止访问
         */
        boolean stop;

        abstract boolean visit(E e);
    }


    /**
     * 二叉搜索树底层的最小存储单元结构
     *
     * @param <E>
     */
    protected static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        /**
         * 在创建时，除了根节点外，其他节点必然存在父节点，但不会存在子节点。
         * 也就是说，BST添加元素的实质就是在寻找parent
         * 找到parent之后，看看该元素是parent.left还是parent.right
         *
         * @param element 元素
         * @param parent  父节点
         */
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        /**
         * 左右子节点都为空的节点是叶子节点
         *
         * @return 是否是叶子节点
         */
        public boolean isLeaf() {
            return left == null && right == null;
        }

        /**
         * 获取节点的(宽)度
         */
        public int width() {
            return (left == null ? 0 : 1) + (right == null ? 0 : 1);
        }
    }
}

二叉搜索树的实现

package com.ssy.data_structure.tree;

import java.util.Comparator;

/**
 * 二叉搜索树
 *
 * @author 苏尔伯特
 * @date 2021/9/5 9:13
 */
public class BST<E> extends BinaryTree<E> {

    /**
     * 比较器，用来指定比较大小的规则
     */
    private Comparator<E> comparator;

    /**
     * 没有比较器，但对于添加的元素需要做检查，必须实现Comparable接口
     */
    public BST() {
    }

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

    public void add(E e) {
        elementNotNullCheck(e);
        if (root == null) {
            root = new Node<>(e, null);
        } else {
            Node<E> parent = parentNode(e);
            Node<E> currentNode = new Node<>(e, parent);
            linkNode(currentNode, parent);
        }
        size++;
    }

    /**
     * 父节点指定子节点的左右位置
     *
     * @param currentNode 当前节点【子节点】
     * @param parent      父节点
     */
    private void linkNode(Node<E> currentNode, Node<E> parent) {
        int result = compareNode(currentNode, parent);
        if (result < 0) {
            parent.left = currentNode;
        } else if (result > 0) {
            parent.right = currentNode;
        } else {
            parent.element = currentNode.element;
        }
    }

    /**
     * 找到元素的父节点
     *
     * @param e 元素
     * @return 父节点
     */
    private Node<E> parentNode(E e) {
        Node<E> node = root;
        Node<E> parent = root;
        while (node != null) {
            int result = compareElement(e, node.element);
            parent = node;
            if (result < 0) {
                node = parent.left;
            } else if (result > 0) {
                node = parent.right;
            } else {
                break;
            }
        }
        return parent;
    }

    /**
     * 比较两个元素大小
     * 若初始化时规定了比较器，那么就按照比较器来比较；
     * 若没有比较器，则按照元素自身的compareTo规则比较；若此时的对象没有实现Comparable接口就让它报错
     *
     * @param node1 节点1
     * @param node2 节点2
     * @return result = 0,则node1=node2; result < 0,则node1<node2; result > 0,则node1>node2
     */
    private int compareNode(Node<E> node1, Node<E> node2) {
        E e1 = node1.element;
        E e2 = node2.element;
        return compareElement(e1, e2);
    }

    /**
     * 比较元素大小
     *
     * @return 默认元素实现Comparable接口，否则抛异常
     */
    @SuppressWarnings("unchecked")
    private int compareElement(E e1, E e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        } else {
            return ((Comparable<E>) e1).compareTo(e2);
        }
    }

    public void remove(E e) {
        remove(node(e));
    }

    /**
     * 删除当前节点
     */
    private void remove(Node<E> node) {
        if (node == null) return;
        if (node.width() == 2) {
            // 这里有两种方案，取前驱节点或者后继节点来代替当前被删除的节点。这里选择后继节点
            Node<E> succ = successor(node);
            // 将后继节点的值赋给当前节点，那么需要删除的节点就变成了后继节点
            node.element = succ.element;
            // 变量node原本存储的是当前节点，但为了后续操作的通用，将succ的引用copy给node
            node = succ;
        }
        // 此时的node度必然是1或0.
        // 如果node度为1，那么其子节点将代替自己。如果度为0，那么自己将被置为null
        Node<E> childNode = node.left != null ? node.left : node.right;
        if (childNode != null) {
            // 要删除的节点是度为1的节点：
            // 1. 修改parent指向
            childNode.parent = node.parent;
            // 2. 修改parent的子节点指向【这取决于node是其parent节点的左子节点还是右子节点】
            if (node.parent == null) {
                // node是度为1的根节点
                root = childNode;
            } else if (node == node.parent.left) {
                node.parent.left = childNode;
            } else {
                node.parent.right = childNode;
            }
        } else if (node.parent == null) {
            // 当前节点是度为0的根节点
            root = null;
        } else {
            // 当前节点是叶子节点，但不是根节点.
            if (node == node.parent.left) {
                node.parent.left = null;
            } else {
                node.parent.right = null;
            }
        }
        size--;
    }

    private Node<E> node(E e) {
        Node<E> node = root;
        while (node != null) {
            int result = compareElement(e, node.element);
            if (result == 0) return node;
            node = result < 0 ? node.left : node.right;
        }
        return null;
    }
    
    public boolean contains(E e) {
        return node(e) != null;
    }
}