数据结构 -- 二叉查找树_满二叉搜索树查找

一、完美二叉树

又叫满二叉树，即除了最后一个层级的叶子节点外，其余每个结点都有两个子结点

二、完全二叉树

需要满足两个条件：
（1）除了最后一层外，其它各层的结点个数都达到最大个数
（2）最后一层的结点集中在左侧，且结点连续，只有右侧部分可以缺失结点

三、二叉树的存储

在使用二叉树存储数据时，我们有两种选择，一种是数组存储，另一种是链表存储。

（1）数组存储

使用数组进行存储时，为了分辨各个节点之间的关系，我们会将树补全成一棵满二叉树，但是会造成空间的浪费。

（2）链表存储

把每个节点包装成一个对象，通过left和right分别指向其左子节点和右子节点，避免了空间的浪费，又条例清晰。

四、什么是二叉查找树

又名二叉排序树、二叉搜索树。当二叉查找树不为空时必须满足以下三个条件：
（1）非空左子树的结点的 key 小于其根结点的 key
（2）非空右子树的结点的 key 大于其根结点的 key
（3）左子树和右子树本身也是个二叉查找树

五、树的遍历

（1）先序遍历

访问根结点 => 访问左子树 => 访问右子树。在访问左子树或右子树的时候，仍是按照这个规则继续访问。

（2）中序遍历

访问左子树 => 访问根结点 => 访问右子树。在访问左子树或右子树的时候，仍是按照这个规则继续访问。

（3）后续遍历

访问左子树 => 访问右子树 => 访问根结点 。在访问左子树或右子树的时候，仍是按照这个规则继续访问。

六、API设计

6.1 节点类

6.2 二叉查找树类

6.3 方法实现思路

6.3.1 增

1、如果当前树中没有任何一个节点，则直接把新节点当作根节点使用
2、如果当前树不为空，则从根节点开始：
2.1如果新节点的key小于当前节点的key，则继续找当前节点的左子节点。
2.2如果新节点的key大于当前节点的key，则继续找当前节点的右子节点。
2.3如果新节点的key等于当前节点的key，则树中已经存在这样的节点，替换该节点的value值即可。

6.3.2 查

从根节点开始：
1、如果要查询的key小于当前节点的key，则继续找当前节点的左子节点；
2、如果要查询的key大于当前节点的key，则继续找当前节点的右子节点；
3、如果要查询的key等于当前节点的key，则书中返回当前节点的value。

6.3.3 删（需要考虑删除后新的顺序）

1、找到被删除的节点；
2、找到被删除节点右子树中的最小节点minNode
3、删除右子树中的最小节点
4、让被删除节点的左子树称为最小节点minNode的左子树，让被删除节点的右子树称为最小节点minNode的右子树
5、让被删除节点的父节点指向最小节点minNode

七、代码实现

7.1 二叉查找树实现

/**
 * 二叉查找树 -- 链表实现
 * @date 2021/5/20 14:26
 */
public class BinaryTree<Key extends Comparable<Key>, Value> {
    // 根节点
    private Node root;
    // 树中元素个数
    private int N;

    // 构造器
    public BinaryTree() {}

    // 增
    public void put(Key key, Value value){
        // 从根节点开始
        root = put(root, key, value);
    }
    // 向指定的树x中添加key-value，并返回添加元素后的新树
    private Node put(Node x, Key key, Value value){
        if(x == null){
            N++;
            return new Node(key, value, null, null);
        }
        int cmp = key.compareTo((Key) x.key);
        if(cmp > 0){
            // 递归
            x.right = put(x.right, key, value);
        }else if(cmp < 0){
            x.left = put(x.left, key, value);
        }else {
            x.value = value;
        }
        return x;
    }

    // 查
    public Value get(Key key){
        return get(root, key);
    }
    // 从指定的树x中，查找key对应的值
    private Value get(Node x, Key key){
        if(x == null){
            return null;
        }
        int cmp = key.compareTo((Key) x.key);
        if(cmp > 0){// 大于当前节点，找右边
            // 递归
            return get(x.right, key);
        }else if(cmp < 0){
            return get(x.left, key);
        }else {
            return (Value) x.value;
        }
    }

    // 删
    public void delete(Key key){
        root = delete(root, key);
    }
    // 删除指定树x中的key对应的value，并返回删除后的新树
    private Node delete(Node x, Key key){
        if(x == null){
            return null;
        }
        int cmp = key.compareTo((Key) x.key);
        if(cmp > 0){
            x.right = delete(x.right, key);
        }else if(cmp < 0){
            x.left = delete(x.left, key);
        }else {
            if(x.right == null){
                return x.left; // ?不是返回新树么？
            }
            if (x.left == null){
                return x.right;
            }
            Node minNode = x.right;
            while (minNode.left != null){
                minNode = minNode.left;
            }
            Node n = x.right;
            while (n.left != null){
                if (n.left.left == null){
                    n.left = null;
                }else {
                    n = n.left;
                }
            }
            minNode.left = x.left;
            minNode.right = x.right;
            x = minNode;
            N--;
        }
        return x;
    }

    // 获取树中元素个数
    public int size(){
        return N;
    }
}

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

7.2 二叉查找树其他便捷方法

7.2.1 查找最小的键

    // 查找最小键
    public Key min(){
        return (Key) min(root).key;
    }
    private Node min(Node x){
        if(x.left != null){
            return min(x.left);
        }else {
            return x;
        }
    }
1
2
3
4
5
6
7
8
9
10
11

7.2.2 查找最大的键

    // 查找最大键
    public Key max(){
        return (Key) max(root).key;
    }
    private Node max(Node x){
        if(x.right != null){
            return max(x.right);
        }else {
            return x;
        }
    }
1
2
3
4
5
6
7
8
9
10
11

7.3 二叉树的基础遍历

7.3.1 前序遍历

    // 前序遍历
    // 获取指定树的所有键，并放入keys队列中
    private void preErgodic(Node x, Queue<Key> keys){
        if(x==null){
            return;
        }

        // 根 -- 把x节点的key放入到keys中
        keys.enqueue((Key) x.key);

        // 左子树 -- 递归遍历x节点的左子树
        if (x.left != null){
            preErgodic(x.left, keys);
        }

        // 右子树 -- 递归遍历x节点的右子树
        if(x.right != null){
            preErgodic(x.right, keys);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

7.3.2 中序遍历

    // 中序遍历
    public Queue<Key> midErgodic(){
        Queue<Key> keys = new Queue<>();
        midErgodic(root, keys);
        return keys;
    }
    private void midErgodic(Node x, Queue<Key> keys){
        if (x==null){
            return;
        }
        // 左子树 -- 递归遍历x节点的左子树
        if (x.left!=null){
            midErgodic(x.left, keys);
        }
        // 根 -- 把x节点的key放入到keys中
        keys.enqueue((Key) x.key);

        // 右子树 -- 递归遍历x节点的右子树
        if (x.right != null){
            midErgodic(x.right, keys);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

7.3.3 后续遍历

    // 后序遍历
    public Queue<Key> afterErgodic(){
        Queue<Key> keys = new Queue<>();
        afterErgodic(root, keys);
        return keys;
    }
    private void afterErgodic(Node x, Queue<Key> keys){
        if (x == null){
            return;
        }
        // 左子树 -- 递归遍历x节点的左子树
        if (x.left != null){
            afterErgodic(x.left, keys);
        }

        // 右子树 -- 递归遍历x节点的右子树
        if (x.right != null){
            afterErgodic(x.right, keys);
        }

        // 根 -- 把x节点的key放入到keys中
        keys.enqueue((Key) x.key);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

7.4 二叉树的层序遍历

    // 层序遍历 -- 从上向下，从左往右
    public Queue<Key> layerErgodic(){
        // 创建队列 -- 存储节点的key
        Queue<Key> keys = new Queue<>();
        Queue<Node> nodes = new Queue<>(); //辅助队列
        // （1）根节点进入队列
        nodes.enqueue(root);
        // （2）弹元素 -- 先弹，将节点的key放到keys中，判断有没有左右子节点，如果有放到队列中
        while (!nodes.isEmpty()){
            Node x = nodes.dequeue(); // 弹出节点
            keys.enqueue((Key) x.key); // 把弹出元素的key放到队列中
            if(x.left!=null){
                nodes.enqueue(x.left);
            }
            if (x.right!=null){
                nodes.enqueue(x.right);
            }
        }
        return keys;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

7.5 二叉树的最大深度

    // 最大深度
    public int maxDepth(){
        return maxDepth(root);
    }
    // 计算指定树x的最大深度
    private int maxDepth(Node x){
        // 1、如果根节点为空，则最大深度为0
        if (x==null){
            return 0;
        }
        int max = 0;
        int maxL = 0;
        int maxR = 0;
        // 2、计算左子树的最大深度
        if (x.left!=null){
            maxL = maxDepth(x.left);
        }
        // 3、计算右子树的最大深度
        if (x.right!=null){
            maxR = maxDepth(x.right);
        }
        // 4、当前树的最大深度 = 左子树最大深度 + 右子树最大深度 + 1
        max = maxL > maxR ? maxL+1 : maxR+1;
        return max;
    }
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