恋上数据结构与算法：二叉搜索树01(十二)_恋上数据结构与算法打印器

作者：知新_RL | 2024-05-24 01:20:54

踩

恋上数据结构与算法打印器

文章目录

(一)二叉搜索树（Binary Search Tree）的需求分析

在这里插入图片描述
说明：

二分搜索使得复杂度每次都减半，最坏复杂度就是logn（记住）
对于上面的有序的动态数组（无序的话添加很快，加在后面就可以了，但是删除依然很慢），无论是增加元素还是删除元素，都应该先做一次搜索，如果使用普通的搜索复杂度肯定是O(n)，使用二分搜索最坏复杂度可以降低到O(logn)
归根结底是要解决搜索的问题

(二)二叉搜索树（Binary Search Tree）的概念

在这里插入图片描述
说明：

任意一个节点的值都大于其左子树所有节点的值（不是之和）
任意一个节点的值都小于其右子树所有节点的值（不是之和）
它的左右子树也是一颗二叉搜索树，也满足上面两点规律

(三)二叉搜索树（Binary Search Tree）的设计

在这里插入图片描述
说明：对于之前的数组和链表都有索引（int index）的概念，但是二叉搜索树没有索引
原因：二叉树是树形结构，非线性结构没办法标索引

代码大致框架如下：
在这里插入图片描述

(四)二叉搜索树（Binary Search Tree）之add：根节点

首先写一个Node内部类，如下：

    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }
1
2
3
4
5
6
7
8
9
10
11

构造节点的时候传递的element通常是不允许为null的，写一个检查的方法，如下：

    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }
1
2
3
4
5

第一次添加节点，添加的是根节点，如下：
在这里插入图片描述

    public void add(E element) {
        elementNotNullCheck(element);
        //添加第一个节点
        if (root == null) {
            root = new Node<>(element, null);
            size++;
            return;
        }
        //添加的不是第一个节点
        
    }
1
2
3
4
5
6
7
8
9
10
11

(五)二叉搜索树（Binary Search Tree）之add：思路

对下面这颗二叉树添加12和1，如下：
在这里插入图片描述
添加之后，结果如下：

过程：以添加12为例，首先用12跟7比较，发现12比7大，就继续找7的右节点
以此类推，找到最后发现还是比11大，就把12放在11的右节点

步骤：

找到父节点parent
创建新节点node
parent.left = node或者parent.right = node

遇到值相等的元素该如何处理？建议覆盖旧的值

(六)二叉搜索树（Binary Search Tree）之add：实现

先写一个compare(E e1, E e2)方法实现比较功能，但是先留空，如下：

    /**
     * 返回值等于0，代表e1等于e2
     * 返回值大于0，代表e1大于e2
     * 返回值小于0，代表e1小于e2
     *
     * @param e1
     * @param e2
     * @return
     */
    private int compare(E e1, E e2) {
        return 0;
    }
1
2
3
4
5
6
7
8
9
10
11
12

add(E element)方法如下：

public void add(E element) {
        elementNotNullCheck(element);
        //添加第一个节点
        if (root == null) {
            root = new Node<>(element, null);
            size++;
            return;
        }
        //添加的不是第一个节点
        Node<E> node = root;//找到父节点
        Node<E> parent = null;//用于保存父节点
        int cmp = 0;//用于记录方向（左还是右）
        while (node != null) {//只有node不为空，才拿node的值跟element做比较
            cmp = compare(element, node.element);//记录方向
            parent = node;//保存父节点，否则while循环结束，node为null，无法进行下一步操作
            if (cmp > 0) {
                node = node.right;//拿node的右节点继续做比较
            } else if (cmp < 0) {
                node = node.left;//拿node的左节点继续做比较
            } else {//相等
                return;//最好是替换，这里先直接返回
            }
        }
        //看插入到父节点的哪个位置
        Node<E> newNode = new Node<>(element, parent);//创建一个新节点
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

(七)二叉搜索树（Binary Search Tree）之compare：comparable

首先编写一个Comparable接口，如下：
在这里插入图片描述
我们让BinarySearchTree里面的泛型E继承Comparable接口

BinarySearchTree里的元素必须实现Comparable接口，并重写int compareTo(E e)方法，如下：

在Person类中重写int compareTo(E e)方法，并且在BinarySearchTree中调用，如下：
在这里插入图片描述

(八)二叉搜索树（Binary Search Tree）之compare：comparator

二叉搜索树要求小的节点放在左子树，大的节点放在右子树，两种情况如下：
在这里插入图片描述
而刚才继承comparable接口的写法就会存在弊端，如下：

如果我再创建一颗树（bst3），那么这两棵树只能都是：年龄小的节点小或年龄小的节点大
如果我想bst2属于年龄小的节点小，而bst3属于年龄小的节点大就需要用下面这种方法了

首先编写一个Comparator接口，如下：
在这里插入图片描述
通过构造函数的方法传递比较器接口，如下：

这样就可以实现个性化比较器了，如下：

在BinarySearchTree把上一个比较器相关的代码注释掉，如下：

最后修改compare(E e1, E e2)方法，如下：
在这里插入图片描述