GitHub源码分享

我的项目主页：https://github.com/gozhuyinglong/blog-demos
本文源码：https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures

1. 二叉查找树（Binary Search Tree）

二叉查找树又叫二叉排序树（Binary Sort Tree），或叫二叉搜寻树，简称BST。BST是一种节点值之间有秩序的二叉树。其个性是：

  • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
  • 任意节点的左、右子树也别离为二叉查找树；

二叉查找树相比于其余数据结构的劣势在于查找、插入的工夫复杂度较低，为$O(logN)$。用大$O$符号示意的工夫复杂度：

算法均匀最差
空间$O(N)$$O(N)$
搜寻$O(logN)$$O(N)$
插入$O(logN)$$O(N)$
删除$O(logN)$$O(N)$

2. BST的实现

二叉查找树要求所有的节点元素都可能排序，所以咱们的Node节点类须要实现Comparable接口，树中的两个元素能够应用compareTo办法进行比拟。
咱们节点中元素的类型为int型，所以该接口泛型为Comparable<Integer>，上面是具体实现：

2.1 节点类

  • element 为数据元素
  • left 为左子节点
  • right 为右子节点
class Node implements Comparable<Integer> {    private final int element; // 数据元素    private Node left; // 左子树    private Node right; // 右子树    private Node(Integer element) {        this.element = element;    }    @Override    public int compareTo(Integer o) {        return o.compareTo(element);    }}

2.2 二叉查找树类

  • root 为树根，所有的操作均始于此

前面会在该类中减少其余办法，如增加、查找、删除等

class BinarySearchTree {        private Node root; // 树根}

3. 插入节点

向二叉查找树中插入的节点总是叶子节点，插入过程如下：

  1. 若root为空，则将插入节点设为root
  2. 以后元素与插入元素通过compareTo进行比拟，若插入元素值小，并且左子节点left为空，则插入至以后节点左子节点；否则持续递归
  3. 若插入元素值大，且右子节点right为空，则插入至以后节点右子节点；否则持续递归。
  4. 若插入元素等于以后节点元素，则插入失败。注：也能够将其插入到右子节点，我这里为了不便间接放弃插入。

具体实现：
在BinarySearchTree类中增加两个办法：

  • public boolean add(int element) 为公开办法
  • private boolean add(Node node, int element)为公有办法，外部递归应用
       // 增加元素       public boolean add(int element) {            if (root == null) {                root = new Node(element);                return true;            }            return add(root, element);        }        // 增加元素（递归）        private boolean add(Node node, int element) {            if (node.compareTo(element) < 0) {                if (node.left == null) {                    node.left = new Node(element);                    return true;                } else {                    return add(node.left, element);                }            } else if (node.compareTo(element) > 0) {                if (node.right == null) {                    node.right = new Node(element);                    return true;                } else {                    return add(node.right, element);                }            } else {                return false;            }        }

4. 查找节点

通过二叉查找树查找元素，其过程如下：

  1. 若root为空，则查找失败
  2. 将以后元素与指标元素对比，若相等则查找胜利。
  3. 若不相等，则持续递归查找：若目标值小于以后节点值，则查找左子树；否则，查找右子树。

具体实现：
在BinarySearchTree类中增加两个办法：

  • public Node find(int element) 为公开办法
  • private Node find(Node node, int element) 为公有办法，外部递归应用
      // 查找元素      public Node find(int element) {            if (root == null) {                return null;            }            return find(root, element);        }        // 查问元素（递归）        private Node find(Node node, int element) {            if (node == null) {                return null;            }            int compareResult = node.compareTo(element);            if (compareResult < 0) {                return find(node.left, element);            } else if (compareResult > 0) {                return find(node.right, element);            } else {                return node;            }        }

5. 遍历节点

BST是一个有序二叉树，通过中序遍历可程序输入树中节点。
中序遍历过程如下：

  1. 递归遍历左子节点
  2. 输入以后节点
  3. 递归遍历右子节点

具体实现：
在BinarySearchTree类中增加两个办法：

  • public void orderPrint() 为公开办法
  • private void orderPrint(Node node) 为公有办法，外部递归应用
      // 遍历节点      public void orderPrint() {            orderPrint(root);        }        // 遍历节点（递归）        private void orderPrint(Node node) {            if (node == null) {                return;            }            // 递归左子节点            if (node.left != null) {                orderPrint(node.left);            }            // 输入以后节点            System.out.println(node.element);            // 递归右子节点            if (node.right != null) {                orderPrint(node.right);            }        }

6. 删除节点

删除节点最为复查，共有三种状况：

6.1 指标元素为叶子节点

叶子节点最容易删除，过程如下：

  1. 找到指标节点的父节点
  2. 判断指标节点是父节点的左子树还是右子树
  3. 若是左子树，将父节点的left设为空；否则将父节点的right设为空

6.2 指标元素即有左子树，也有右子树

该状况删除操作最为简单，过程如下：

  1. 找到指标节点的父节点
  2. 判断指标节点是父节点的左子树还是右子树
  3. 找到右子树中最小元素（叶子节点），将其赋给长期变量minNode，再将该元素从树中删除
  4. 将指标元素的属性赋予minNode。
  5. 若指标元素是父节点的左子树，将父节点的left设为minNode；否则将父节点的right设为minNode

6.3 指标元素只有左子树，或只有右子树

删除过程如下

  1. 找到指标节点的父节点
  2. 判断指标节点是父节点的左子树还是右子树
  3. 若是左子树，将父节点的left设为指标节点不为空的子树；否则将父节点的right设为指标节点不为空的子树

具体实现
在BinarySearchTree类中增加两个办法：

  • public boolean remove(int element) 为公开办法
  • private boolean remove(Node parentNode, Node node, int element)为公有办法，外部递归应用
      // 删除节点      public boolean remove(int element) {            if (root == null) {                return false;            }            // 如果删除的元素是root            if (root.compareTo(element) == 0) {                if (root.right == null) {                    root = root.left;                } else {                    root.right.left = root.left;                    root = root.right;                }                return true;            }            return remove(null, root, element);        }        // 删除节点（递归）        private boolean remove(Node parentNode, Node node, int element) {            if (node == null) {                return false;            }            // 先找到指标元素            int compareResult = node.compareTo(element);            if (compareResult < 0) {                return remove(node, node.left, element);            }            if (compareResult > 0) {                return remove(node, node.right, element);            }            // 找到指标元素，判断该节点是父节点的左子树还是右子树            boolean isLeftOfParent = false;            if (parentNode.left != null && parentNode.left.compareTo(element) == 0) {                isLeftOfParent = true;            }            // 删除指标元素            if (node.left == null && node.right == null) { // （1）指标元素为叶子节点，间接删除                if (isLeftOfParent) {                    parentNode.left = null;                } else {                    parentNode.right = null;                }            } else if (node.left != null && node.right != null) { // （2）指标元素即有左子树，也有右子树                // 找到右子树最小值（叶子节点），并将其删除                Node minNode = findMin(node.right);                remove(minNode.element);                // 将该最小值替换要删除的指标节点                minNode.left = node.left;                minNode.right = node.right;                if(isLeftOfParent) {                    parentNode.left = minNode;                } else {                    parentNode.right = minNode;                }            } else { // （3）指标元素只有左子树，或只有右子树                if (isLeftOfParent) {                    parentNode.left = node.left != null ? node.left : node.right;                } else {                    parentNode.right = node.left != null ? node.left : node.right;                }            }            return true;        }    }

7. 残缺代码

该代码依据下图二叉查找树实现，其操作包含：增加、查找、遍历、删除、查问最小值、查问最大值。

public class BinarySearchTreeDemo {    public static void main(String[] args) {        BinarySearchTree tree = new BinarySearchTree();        System.out.println("----------------------增加元素");        Integer[] array = {5, 2, 7, 1, 4, 3, 7, 6, 9, 8};        for (Integer element : array) {            System.out.printf("增加元素[%s] --> %s\n", element, tree.add(element));        }        System.out.println("----------------------程序输入（中序遍历）");        tree.orderPrint();        System.out.println("----------------------查找元素");        System.out.println(tree.find(7));        System.out.println("----------------------查找最小元素");        System.out.println(tree.findMin());        System.out.println("----------------------查找最大元素");        System.out.println(tree.findMax());        System.out.println("----------------------是否蕴含元素");        System.out.println("是否蕴含[0] --> \t" + tree.contains(0));        System.out.println("是否蕴含[2] --> \t" + tree.contains(2));        System.out.println("----------------------删除指标元素");        System.out.println("删除[0] --> \t" + tree.remove(0));        tree.orderPrint();        System.out.println("删除[1] --> \t" + tree.remove(1));        tree.orderPrint();        System.out.println("删除[4] --> \t" + tree.remove(4));        tree.orderPrint();        System.out.println("删除[7] --> \t" + tree.remove(7));        tree.orderPrint();    }    private static class BinarySearchTree {        private Node root; // 树根        /**         * 增加元素         *         * @param element         * @return         */        public boolean add(int element) {            if (root == null) {                root = new Node(element);                return true;            }            return add(root, element);        }        /**         * 增加元素（递归）         *         * @param node         * @param element         * @return         */        private boolean add(Node node, int element) {            if (node.compareTo(element) < 0) {                if (node.left == null) {                    node.left = new Node(element);                    return true;                } else {                    return add(node.left, element);                }            } else if (node.compareTo(element) > 0) {                if (node.right == null) {                    node.right = new Node(element);                    return true;                } else {                    return add(node.right, element);                }            } else {                return false;            }        }        /**         * 查问元素         *         * @param element         * @return         */        public Node find(int element) {            if (root == null) {                return null;            }            return find(root, element);        }        /**         * 查问元素（递归）         *         * @param node         * @param element         * @return         */        private Node find(Node node, int element) {            if (node == null) {                return null;            }            int compareResult = node.compareTo(element);            if (compareResult < 0) {                return find(node.left, element);            } else if (compareResult > 0) {                return find(node.right, element);            } else {                return node;            }        }        /**         * 查找最大值         *         * @return         */        public Node findMax() {            return findMax(root);        }        /**         * 查找最大值（递归）         *         * @param node         * @return         */        private Node findMax(Node node) {            if (node.right == null) {                return node;            }            return findMax(node.right);        }        /**         * 查找最小值         *         * @return         */        private Node findMin() {            return findMin(root);        }        /**         * 查找最小值（递归）         *         * @param node         * @return         */        private Node findMin(Node node) {            if (node.left == null) {                return node;            }            return findMin(node.left);        }        /**         * 程序输入         */        public void orderPrint() {            orderPrint(root);        }        /**         * 程序输入（递归）         *         * @param node         */        private void orderPrint(Node node) {            if (node == null) {                return;            }            // 递归左子节点            if (node.left != null) {                orderPrint(node.left);            }            // 输入以后节点            System.out.println(node.element);            // 递归右子节点            if (node.right != null) {                orderPrint(node.right);            }        }        /**         * 是否蕴含某值         *         * @param element         * @return         */        public boolean contains(int element) {            if (find(element) == null) {                return false;            }            return true;        }        /**         * 删除指标元素         *         * @param element         * @return         */        public boolean remove(int element) {            if (root == null) {                return false;            }            // 如果删除的元素是root            if (root.compareTo(element) == 0) {                if (root.right == null) {                    root = root.left;                } else {                    root.right.left = root.left;                    root = root.right;                }                return true;            }            return remove(null, root, element);        }        /**         * 删除指标元素（递归），有三种状况：         * （1）指标元素为叶子节点         * （2）指标元素即有左子树，也有右子树         * （3）指标元素只有左子树，或只有右子树         *         * @param parentNode 以后节点的父节点         * @param node       以后节点（若以后节点上的元素与要删除的元素匹配，则删除以后节点）         * @param element    要删除的元素         * @return         */        private boolean remove(Node parentNode, Node node, int element) {            if (node == null) {                return false;            }            // 先找到指标元素            int compareResult = node.compareTo(element);            if (compareResult < 0) {                return remove(node, node.left, element);            }            if (compareResult > 0) {                return remove(node, node.right, element);            }            // 找到指标元素，判断该节点是父节点的左子树还是右子树            boolean isLeftOfParent = false;            if (parentNode.left != null && parentNode.left.compareTo(element) == 0) {                isLeftOfParent = true;            }            // 删除指标元素            if (node.left == null && node.right == null) { // （1）指标元素为叶子节点，间接删除                if (isLeftOfParent) {                    parentNode.left = null;                } else {                    parentNode.right = null;                }            } else if (node.left != null && node.right != null) { // （2）指标元素即有左子树，也有右子树                // 找到右子树最小值（叶子节点），并将其删除                Node minNode = findMin(node.right);                remove(minNode.element);                // 将该最小值替换要删除的指标节点                minNode.left = node.left;                minNode.right = node.right;                if(isLeftOfParent) {                    parentNode.left = minNode;                } else {                    parentNode.right = minNode;                }            } else { // （3）指标元素只有左子树，或只有右子树                if (isLeftOfParent) {                    parentNode.left = node.left != null ? node.left : node.right;                } else {                    parentNode.right = node.left != null ? node.left : node.right;                }            }            return true;        }    }    private static class Node implements Comparable<Integer> {        private final Integer element; // 数据元素        private Node left; // 左子树        private Node right; // 右子树        private Node(Integer element) {            this.element = element;        }        @Override        public int compareTo(Integer o) {            return o.compareTo(element);        }        @Override        public String toString() {            return "Node{" +                    "element=" + element +                    '}';        }    }}

输入后果：

----------------------增加元素增加元素[5] --> true增加元素[2] --> true增加元素[7] --> true增加元素[1] --> true增加元素[4] --> true增加元素[3] --> true增加元素[7] --> false增加元素[6] --> true增加元素[9] --> true增加元素[8] --> true----------------------程序输入（中序遍历）123456789----------------------查找元素Node{element=7}----------------------查找最小元素Node{element=1}----------------------查找最大元素Node{element=9}----------------------是否蕴含元素是否蕴含[0] -->     false是否蕴含[2] -->     true----------------------删除指标元素删除[0] -->     false123456789删除[1] -->     true23456789删除[4] -->     true2356789删除[7] -->     true235689