树

为什么需要树这种存储结构?

  1. 数组：
    • 优点：通过下标方式查找元素，查找速度快，况且还可以通过排序+查找算法进一步提高查找速度，随机存取是其最大优势。
    • 缺点：插入删除元素复杂，涉及到整体移动的问题，耗费大量时间。
  2. 链式存储：
    • 优点：插入删除方便。
    • 缺点：查找效率不高，需要从头开始遍历查找。

    提一嘴哈希表（数组+链表版），一定程度上集数组和链表之长，既提高查找效率，又简化了插入删除操作。

  3. 树：能提高数据的存储、读取效率，比如二叉排序树，即保证了查询效率，插入删除操作也方便。

树的常用术语(不必纠结)：

image-20241103104817501
术语 解释
节点 A、B、C……都是节点
根节点root A
父节点 C是F和G的父节点
子节点 C是A的子节点
叶子节点 没有子节点的节点
节点的权 节点值
路径 从root找到当前节点的路线
层 如图
子树 D、H为B的子树
树的高度 4
森林 多棵树构成

注意事项：

树分为有序树和无序树，有序树分左右，无序树不分左右。

二叉树

基本概念

  1. 每个节点都至多有两个子节点。
  2. 二叉树的子节点分为左节点和右节点。
  3. 满二叉树：如果所有叶子节点都在最后一层，且节点总数为$2^n-1$个，其中n为层数，则称满二叉树。
  4. 完全二叉树：若二叉树的所有叶子节点都在最后一层或倒数第二层，且最后一层的叶子节点左连续，倒数第二层的叶子节点右连续，则称完全二叉树。

性质

参考《数据结构（C语言版）》–清华大学出版社

有助于加深对顺序存储二叉树中“为什么有这样的特点”的理解，使之成为严谨的数学推导。（当然不看也行，直接找规律也能推出来）

  1. 在二叉树的第$i$层至多有$2^{i-1}$个节点（$i\geq1$）
  2. 深度为$k$的二叉树至多有$2^k-1$个节点（$k\geq1$）
  3. 对任意一棵二叉树，如果其终端节点数为$n_0$，度为2的节点数为$n_2$，则$n_0=n_2+1$

关于第三点的推导：

已知$n=n_0+n_1+n_2$，其中$n$为节点总数（这个式子是基于节点数列出来的）

又因为$n=n_1+2n_2+1$，这个式子的原因为节点数等于分支数+1，只有$n_1$有1个分支，$n_2$有2个分支，$n_0$没有分支。

两式消去$n_1$即可

  1. 具有n个节点的完全二叉树的深度 $\lfloor \log_2 n \rfloor + 1$。

Proof：

设深度为k，则根据完全二叉树定义以及性质2可知：

$2^{k-1}-1<n\leq 2^k-1$或$2^{k-1}\leq n < 2^k$，选则其一可解得……

  1. 对于一个有n个节点的完全二叉树，对于任一节点$i$（$1 \leq i \leq n$），有：
    • 若$i=1$，则为root节点；若$i>1$，则其父节点为$\lfloor i/2 \rfloor$
    • 若$2i>n$，则节点$i$无左子节点，否则其左子节点为$2i$
    • 若$2i+1>n$，则节点$i$无右节点，否则其右子节点为$2i+1$

链式存储二叉树

需要创建一个结点类，应包括数据本身的数据、左节点left、右节点right、[父节点root可选]

连式存储很常见，所以不做代码演示，因为后续的很多都用到了链式存储……

而且遍历、查找方法在节点类中均有写，但是最终我们是通过调用BinaryTree这个类里面的方法，所以节点类里面写的方法一般情况是给二叉树用的（如遍历、查找[后续代码可见其用意]）

前序/中序/后续遍历

思路分析

区分前/中/后序，看父节点什么时候输出。

概念：

  1. 前序遍历：先输出父节点，再遍历左子树和右子树。
  2. 中序遍历：先遍历左子树，再输出父节点，再遍历右子树。
  3. 后续遍历：先遍历左子树，再遍历右子树，最后输出父节点。

流程：

  1. 创建二叉树
  2. 遍历

    • 前序遍历

      • 先输出当前节点(初始时为root节点)
      • 如果左子节点不为空，则向左递归执行前序遍历
      • 如果右子节点不为空，则向右递归执行前序遍历

    • 中序遍历

      • 如果当前节点的左子节点不为空，则向左递归执行中序遍历
      • 输出当前节点
      • 如果当前节点的右子节点不为空，则向右递归执行中序遍历

    • 后续遍历

      • 如果当前节点的左子节点不为空，则向左递归执行后序遍历
      • 如果当前节点的右子节点不为空，则向右递归执行后序遍历
      • 输出当前节点

小技巧：

无论何种技巧，画图永远不会错

前序遍历就是走到哪输出到哪（从根先往左下，再回溯尝试往右）；中序遍历，某个节点没有左节点了（优先输出左叶子，没有左叶子后就从根往下，输出一次掉一片叶子），就输出；后序遍历，某个节点同时没有左右了，输出（优先左叶子，再右叶子，每次输出一次就相当于掉一片叶子）。

代码实现

BinaryTreeDemo

核心为preOrder、infixOrder、postOrder（in class BinaryTree和HumanNode）

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
package com.yukinoshita.dataStructure.tree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HumanNode humanNode = new HumanNode(1,"yukino");
        HumanNode humanNode2 = new HumanNode(2,"yukino2");
        HumanNode humanNode3 = new HumanNode(3,"yukino3");
        HumanNode humanNode4 = new HumanNode(4,"yukino4");
        HumanNode humanNode5 = new HumanNode(5,"yukino5");
        //姑且手动创建
        humanNode.setLeft(humanNode2);
        humanNode.setRight(humanNode3);
        humanNode2.setLeft(humanNode4);
        humanNode3.setRight(humanNode5);

        binaryTree.setRoot(humanNode);
        System.out.println("前序遍历：");
        binaryTree.preOrder();
        System.out.println("中序遍历：");
        binaryTree.infixOrder();
        System.out.println("后续遍历：");
        binaryTree.postOrder();
    }
}

//定义BinaryTree 二叉树
class BinaryTree{
    HumanNode root;

    public void setRoot(HumanNode root) {
        this.root = root;
    }

    //前序遍历
    public void preOrder(){
        if(this.root != null){
            this.root.preOrder();
        }else{
            System.out.println("The tree is empty");
        }
    }

    //中序遍历
    public void infixOrder(){
        if (this.root != null) {
            this.root.infixOrder();
        }else{
            System.out.println("The tree is empty");
        }
    }

    //后序遍历
    public void postOrder(){
        if (this.root != null) {
            this.root.postOrder();
        }else{
            System.out.println("The tree is empty");
        }
    }
}

//节点
class HumanNode {
    private int id;
    private String name;
    private HumanNode left;
    private HumanNode right;

    public HumanNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    //前序遍历
    public void preOrder() {
        System.out.println(this);//先输出父节点
        if (this.left != null) {//左递归
            this.left.preOrder();
        }
        if (this.right != null) {//右递归
            this.right.preOrder();
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.left != null) {//左递归
            this.left.infixOrder();
        }
        System.out.println(this);//输出父节点
        if (this.right != null) {//右递归
            this.right.infixOrder();
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.left != null) {//左递归
            this.left.postOrder();
        }
        if (this.right != null) {//右递归
            this.right.postOrder();
        }
        System.out.println(this);//输出父节点
    }

    @Override
    public String toString() {
        return "HumanNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HumanNode getLeft() {
        return left;
    }

    public void setLeft(HumanNode left) {
        this.left = left;
    }

    public HumanNode getRight() {
        return right;
    }

    public void setRight(HumanNode right) {
        this.right = right;
    }
}

前序/中序/后续查找

思路分析

流程：

  1. 存在一颗二叉树
  2. 查找
    • 前序查找
      • 先判断当前节点的id是否等于要查找的
      • 如果相等，则返回当前节点
      • 如果不等，则判断当前节点的左子节点是否为空，若不为空，则向左递归。
      • 如果左递归找到节点，则返回；否则，判断判断当前节点的右子节点是否为空，若不为空，则继续向右递归。
    • 中序查找
      • 判断当前节点的左子节点是否为空，若不为空，则向左递归。
      • 如果找到，则返回。
      • 如果没找到，则判断当前节点是否是要找的绩点，如果是，则返回。
      • 不是，判断右子节点是否为空，不为空，则向右递归，找到则返回，否则返回null。
    • 后序查找
      • 判断当前节点的左子节点是否为空，若不为空，则向左递归。
      • 如果找到，则返回。
      • 如果没找到，判断右子节点是否为空，不为空，则向左递归，找到则返回。
      • 若没找到，判断当前节点是否是想要找的节点，如果是返回，不是则返回null。

tips1：无论怎样，凡是遇到需要访问左、右节点的操作，均需要先判断是否为空。

tips2：前序–>当前，左，右； 中序–>左，当前，右； 后序–>左，右，当前。

代码实现

BinaryTreeDemo

核心为preOrderSearch、infixOrderSearch、postOrderSearch（in class BinaryTree和HumanNode）

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
package com.yukinoshita.dataStructure.tree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HumanNode humanNode = new HumanNode(1, "yukino");
        HumanNode humanNode2 = new HumanNode(2, "yukino2");
        HumanNode humanNode3 = new HumanNode(3, "yukino3");
        HumanNode humanNode4 = new HumanNode(4, "yukino4");
        HumanNode humanNode5 = new HumanNode(5, "yukino5");
        //姑且手动创建
        humanNode.setLeft(humanNode2);
        humanNode.setRight(humanNode3);
        humanNode2.setLeft(humanNode4);
        humanNode3.setRight(humanNode5);
        binaryTree.setRoot(humanNode);

        HumanNode res = null;
        System.out.println("前序遍历方式：");
        res = binaryTree.preOrderSearch(1);
        System.out.println("找到节点为："+res);

        System.out.println("中序遍历方式：");
        res = binaryTree.infixOrderSearch(1);
        System.out.println("找到节点为："+res);

        System.out.println("后序遍历方式：");
        res = binaryTree.postOrderSearch(1);
        System.out.println("找到节点为："+res);

    }
}

//定义BinaryTree 二叉树
class BinaryTree {
    HumanNode root;

    public void setRoot(HumanNode root) {
        this.root = root;
    }

    //前序遍历查找
    public HumanNode preOrderSearch(int id) {
        if (this.root != null) {
            return this.root.preOrderSearch(id);
        }
        return null;
    }

    //中序遍历查找
    public HumanNode infixOrderSearch(int id) {
        if (this.root != null) {
            return this.root.infixOrderSearch(id);
        }
        return null;
    }

    //后序遍历查找
    public HumanNode postOrderSearch(int id) {
        if (this.root != null) {
            return this.root.postOrderSearch(id);
        }
        return null;
    }

    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("The tree is empty");
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("The tree is empty");
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("The tree is empty");
        }
    }
}

//节点
class HumanNode {
    private int id;
    private String name;
    private HumanNode left;
    private HumanNode right;

    public HumanNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    //前序遍历查找
    public HumanNode preOrderSearch(int id) {
        System.out.println("前序遍历ing");
        if (this.id == id) {
            return this;
        }
        HumanNode humanNode = null;
        if (this.left != null) {
            humanNode = this.left.preOrderSearch(id);
        }
        if (humanNode != null) {
            return humanNode;
        }
        if (this.right != null) {
            humanNode = this.right.preOrderSearch(id);
        }
        return humanNode;
    }

    //中序遍历查找
    public HumanNode infixOrderSearch(int id) {
        System.out.println("中序遍历ing");
        HumanNode humanNode = null;
        if (this.left != null) {
            humanNode = this.left.infixOrderSearch(id);
        }
        if (humanNode != null) {
            return humanNode;
        }
        if (this.id == id) {
            return this;
        }
        if (this.right != null) {
            humanNode = this.right.infixOrderSearch(id);
        }
        return humanNode;
    }

    //后序遍历查找
    public HumanNode postOrderSearch(int id) {
        System.out.println("后序遍历ing");
        HumanNode humanNode = null;
        if (this.left != null) {
            humanNode = this.left.postOrderSearch(id);
        }
        if (humanNode != null) {
            return humanNode;
        }
        if (this.right != null) {
            humanNode = this.right.postOrderSearch(id);
        }
        if (humanNode != null) {
            return humanNode;
        }
        return this.id == id ? this : humanNode;
    }

    //前序遍历
    public void preOrder() {
        System.out.println(this);//先输出父节点
        if (this.left != null) {//左递归
            this.left.preOrder();
        }
        if (this.right != null) {//右递归
            this.right.preOrder();
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.left != null) {//左递归
            this.left.infixOrder();
        }
        System.out.println(this);//输出父节点
        if (this.right != null) {//右递归
            this.right.infixOrder();
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.left != null) {//左递归
            this.left.postOrder();
        }
        if (this.right != null) {//右递归
            this.right.postOrder();
        }
        System.out.println(this);//输出父节点
    }

    @Override
    public String toString() {
        return "HumanNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HumanNode getLeft() {
        return left;
    }

    public void setLeft(HumanNode left) {
        this.left = left;
    }

    public HumanNode getRight() {
        return right;
    }

    public void setRight(HumanNode right) {
        this.right = right;
    }
}

删除节点

思路分析

删除操作：

  1. 如果删除的节点是叶子节点，则删除该节点
  2. 如果删除的节点是非叶子节点，则删除子树

如果不想把整棵子树删除，

可以考虑将第二点改为：(放于实现2)

  • 若该非叶子节点A只有一个子节点B，则让这个子节点B替代A
  • 若改非叶子节点A有左节点B和右节点C，则让左子节点B替代A
  • 但是其实实现还有有一定难度的：假如要删除的A既有左子节点B和右子节点C，且B、C都各自有两个子节点，这时候就很复杂咯……(我这边暂时用一种简单实现：还是让B替代A，但是在B向左while循环，找到最左边的那个位置，然后把C插入(这样子代码实现简单，但是树的层数会变高……))

后续的二叉排序树更有另一套规则

思路：

  1. 若树只有一个root节点，则判断root是否要要删的，若是，置null。然后进行下面操作：(第0步写在BinaryTree的删除方法里[最先判断]，后续5步写在HumanNode的删除方法里)

  2. 因为二叉排序树是单向的，所以我们判断的是当前节点的子节点是否需要删除，而不是判断当前节点是否需要被删除（除非节点设计上带有父节点、或者查找时带有父节点信息）。

  3. 如果当前节点的左子节点不为空if(this.left != null)，且为要删除的节点，则删除this.left = null(简单粗暴法)，结束递归。

  4. 如果当前节点的左子节点不为空if(this.right != null)，且为要删除的节点，则删除this.right = null(简单粗暴法)，结束递归。

  5. 若第2、3步都没删除成功，则向左递归（当然要判断是否为空）。

  6. 若第4步没删除成功，则向右递归（当然要判断是否为空）。

代码实现

实现1(直接把子树删掉)

BinaryTreeDemo

核心为：delNodeByIdin class BinaryTree和HumanNode

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
package com.yukinoshita.dataStructure.tree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HumanNode humanNode = new HumanNode(1, "yukino");
        HumanNode humanNode2 = new HumanNode(2, "yukino2");
        HumanNode humanNode3 = new HumanNode(3, "yukino3");
        HumanNode humanNode4 = new HumanNode(4, "yukino4");
        HumanNode humanNode5 = new HumanNode(5, "yukino5");
        //姑且手动创建
        humanNode.setLeft(humanNode2);
        humanNode.setRight(humanNode3);
        humanNode2.setLeft(humanNode4);
        humanNode3.setRight(humanNode5);
        binaryTree.setRoot(humanNode);

        binaryTree.preOrder();
        boolean flag = binaryTree.delNodeById(2);
        System.out.println("是否删除成功："+flag);
        binaryTree.preOrder();

    }
}

//定义BinaryTree 二叉树
class BinaryTree {
    HumanNode root;

    public void setRoot(HumanNode root) {
        this.root = root;
    }

    public boolean delNodeById(int id){
        if(this.root == null){
            return false;
        }else if(root.getId() == id){
            this.root = null;
            return true;
        }else{
            return this.root.delNodeById(id);
        }
    }

    //前序遍历查找
    public HumanNode preOrderSearch(int id) {
        if (this.root != null) {
            return this.root.preOrderSearch(id);
        }
        return null;
    }

    //中序遍历查找
    public HumanNode infixOrderSearch(int id) {
        if (this.root != null) {
            return this.root.infixOrderSearch(id);
        }
        return null;
    }

    //后序遍历查找
    public HumanNode postOrderSearch(int id) {
        if (this.root != null) {
            return this.root.postOrderSearch(id);
        }
        return null;
    }

    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("The tree is empty");
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("The tree is empty");
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("The tree is empty");
        }
    }
}

//节点
class HumanNode {
    private int id;
    private String name;
    private HumanNode left;
    private HumanNode right;

    public HumanNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public boolean delNodeById(int id){
        boolean flag = false;
        //左删
        if(this.left != null && this.left.id == id){
            this.left = null;
            return true;
        }
        //右删
        if(this.right != null && this.right.id == id){
            this.right =null;
            return true;
        }
        //左递归
        if(this.left != null){
            flag = this.left.delNodeById(id);
        }
        //左递归删不掉，则右递归
        if(!flag && this.right!= null){
            flag = this.right.delNodeById(id);
        }
        return flag;
    }

    //前序遍历查找
    public HumanNode preOrderSearch(int id) {
        System.out.println("前序遍历ing");
        if (this.id == id) {
            return this;
        }
        HumanNode humanNode = null;
        if (this.left != null) {
            humanNode = this.left.preOrderSearch(id);
        }
        if (humanNode != null) {
            return humanNode;
        }
        if (this.right != null) {
            humanNode = this.right.preOrderSearch(id);
        }
        return humanNode;
    }

    //中序遍历查找
    public HumanNode infixOrderSearch(int id) {
        System.out.println("中序遍历ing");
        HumanNode humanNode = null;
        if (this.left != null) {
            humanNode = this.left.infixOrderSearch(id);
        }
        if (humanNode != null) {
            return humanNode;
        }
        if (this.id == id) {
            return this;
        }
        if (this.right != null) {
            humanNode = this.right.infixOrderSearch(id);
        }
        return humanNode;
    }

    //后序遍历查找
    public HumanNode postOrderSearch(int id) {
        System.out.println("后序遍历ing");
        HumanNode humanNode = null;
        if (this.left != null) {
            humanNode = this.left.postOrderSearch(id);
        }
        if (humanNode != null) {
            return humanNode;
        }
        if (this.right != null) {
            humanNode = this.right.postOrderSearch(id);
        }
        if (humanNode != null) {
            return humanNode;
        }
        return this.id == id ? this : humanNode;
    }

    //前序遍历
    public void preOrder() {
        System.out.println(this);//先输出父节点
        if (this.left != null) {//左递归
            this.left.preOrder();
        }
        if (this.right != null) {//右递归
            this.right.preOrder();
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.left != null) {//左递归
            this.left.infixOrder();
        }
        System.out.println(this);//输出父节点
        if (this.right != null) {//右递归
            this.right.infixOrder();
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.left != null) {//左递归
            this.left.postOrder();
        }
        if (this.right != null) {//右递归
            this.right.postOrder();
        }
        System.out.println(this);//输出父节点
    }

    @Override
    public String toString() {
        return "HumanNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HumanNode getLeft() {
        return left;
    }

    public void setLeft(HumanNode left) {
        this.left = left;
    }

    public HumanNode getRight() {
        return right;
    }

    public void setRight(HumanNode right) {
        this.right = right;
    }
}

实现2(仅删节点)+清晰

BinaryTree.delNodeById

1
2
3
4
5
6
7
8
9
10
11
//不变
public boolean delNodeById(int id){
        if(this.root == null){
            return false;
        }else if(root.getId() == id){
            this.root = null;
            return true;
        }else{
            return this.root.delNodeById(id);
        }
    }

HumanNode.delNodeById

  • 若该非叶子节点A只有一个子节点B，则让这个子节点B替代A
  • 若改非叶子节点A有左节点B和右节点C，则让左子节点B替代A
  • 但是其实实现还有有一定难度的：假如要删除的A既有左子节点B和右子节点C，且B、C都各自有两个子节点，这时候就很复杂咯……
    • 我这边暂时用一种简单实现：还是让B替代A，但是不断在B向左while循环，找到最左边的那个位置，然后把C插入
    • 这样子代码实现简单，但是树的层数会变高……
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
public boolean delNodeById(int id){
        boolean flag = false;
        //左删
        if(this.left != null && this.left.id == id){
            if(isLeaf(this.left)){//如果是叶子节点
                this.left = null;
            }else{//不是叶子
                if(this.left.left!= null){
                    if(this.left.right != null){//说明要给this.left.right找合适的位置接回去
                        HumanNode temp = this.left;

                        while(temp.left!= null){//找到可以插入的位置
                            temp=temp.left;
                        }
                        temp.left = this.left.right;
                    }
                    this.left = this.left.left;//执行 原先被删除节点的左子节点进行替代的操作
                }else{
                    this.left = this.left.right;
                }
            }
            return true;
        }
        //右删
        if(this.right != null && this.right.id == id){
            if(isLeaf(this.right)){
                this.right =null;
            }else{
                if(this.right.left!= null){
                    if(this.right.right != null){//说明要给this.right.right找合适的位置接回去
                        HumanNode temp = this.right;

                        while(temp.left!= null){//找到可以插入的位置
                            temp=temp.left;
                        }
                        temp.left = this.right.right;
                    }
                    this.right = this.right.left;//执行 原先被删除节点的左子节点进行替代的操作
                }else{
                    this.right = this.right.right;
                }
            }
            return true;
        }
        //左递归
        if(this.left != null){
            flag = this.left.delNodeById(id);
        }
        //左递归删不掉，则右递归
        if(!flag && this.right!= null){
            flag = this.right.delNodeById(id);
        }
        return flag;
    }

main测试代码1：结果为1 4 6 8 7 3 5

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
public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HumanNode humanNode = new HumanNode(1, "yukino");
        HumanNode humanNode2 = new HumanNode(2, "yukino2");
        HumanNode humanNode3 = new HumanNode(3, "yukino3");
        HumanNode humanNode4 = new HumanNode(4, "yukino4");
        HumanNode humanNode5 = new HumanNode(5, "yukino5");

        HumanNode humanNode6 = new HumanNode(6, "yukino6");
        HumanNode humanNode7 = new HumanNode(7, "yukino7");
        HumanNode humanNode8 = new HumanNode(8, "yukino7");
        //姑且手动创建
        humanNode.setLeft(humanNode2);
        humanNode.setRight(humanNode3);
        humanNode2.setLeft(humanNode4);
        humanNode3.setRight(humanNode5);

        humanNode4.setLeft(humanNode6);
        humanNode4.setRight(humanNode7);
        humanNode2.setRight(humanNode8);
        binaryTree.setRoot(humanNode);

        binaryTree.preOrder();
        boolean flag = binaryTree.delNodeById(2);
        System.out.println("是否删除成功："+flag);
        binaryTree.preOrder();

    }

main测试代码2：结果为1 2 4 6 7 8 5

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
public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HumanNode humanNode = new HumanNode(1, "yukino");
        HumanNode humanNode2 = new HumanNode(2, "yukino2");
        HumanNode humanNode3 = new HumanNode(3, "yukino3");
        HumanNode humanNode4 = new HumanNode(4, "yukino4");
        HumanNode humanNode5 = new HumanNode(5, "yukino5");

        HumanNode humanNode6 = new HumanNode(6, "yukino6");
        HumanNode humanNode7 = new HumanNode(7, "yukino7");
        HumanNode humanNode8 = new HumanNode(8, "yukino7");
        //姑且手动创建
        humanNode.setLeft(humanNode2);
        humanNode.setRight(humanNode3);
        humanNode2.setLeft(humanNode4);
        humanNode3.setRight(humanNode5);

        humanNode3.setLeft(humanNode6);
        humanNode6.setLeft(humanNode7);
        humanNode6.setRight(humanNode8);
        binaryTree.setRoot(humanNode);

        binaryTree.preOrder();
        boolean flag = binaryTree.delNodeById(3);
        System.out.println("是否删除成功："+flag);
        binaryTree.preOrder();

    }

顺序存储二叉树

思路分析

说明：

从数据存储来看，数组存储方式和树存储方式可以相互转换（如下：）

image-20241103185227543

要求：

  1. 二叉树中的数据用数组的形式存放，如上
  2. 在遍历数组时，仍能实现树的前序/中序/后序遍历。

特点：

  1. 顺序存储二叉树，通常只考虑完全二叉树。
  2. 第n个元素的左子节点为$2*n+1$
  3. 第n个元素的右子节点为$2*n+2$
  4. 第n个元素的父节点为$(n-1)/2$

    n表示二叉树中第几个元素（从0开始），且编号顺序为——低层优先、左节点优先

ps：八大排序算法之堆排序，就会使用顺序存储二叉树。

代码实现

ArrayBinaryTreeDemo

实现了数组的前序/中序/后序查找

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
package com.yukinoshita.dataStructure.tree;

public class ArrayBinaryTreeDemo {
    public static void main(String args[]) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
        System.out.println("前序遍历：");
        arrayBinaryTree.preOrder();//1 2 4 5 3 6 7
        System.out.println("中序遍历：");
        arrayBinaryTree.infixOrder();//4 2 5 1 6 3 7
        System.out.println("后序遍历：");
        arrayBinaryTree.postOrder();//4 5 2 6 7 3 1
    }
}

//实现顺序存储二叉树的遍历
class ArrayBinaryTree {
    private int[] arr;

    //重载，使得不写参数就是代表从根节点开始遍历
    public void postOrder(){
        this.postOrder(0);
    }

    public void infixOrder(){
        this.infixOrder(0);
    }

    public void preOrder(){
        this.preOrder(0);
    }

    /**
     * 顺序存储二叉树的前序遍历
     *
     * @param index 数组下标
     */
    public void preOrder(int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("当前数组为空，无法执行前序遍历");
            return;
        }
        System.out.println("当前节点为:" + arr[index]);

        //如果存在左子节点
        if (2 * index + 1 < arr.length) {
            preOrder(2 * index + 1);
        }
        //如果存在右子节点
        if (2 * index + 2 < arr.length) {
            preOrder(2 * index + 2);
        }
    }

    public void infixOrder(int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("当前数组为空，无法执行前序遍历");
            return;
        }

        if (2 * index + 1 < arr.length) {
            infixOrder(2 * index + 1);
        }

        System.out.println("当前节点为:" + arr[index]);

        if (2 * index + 2 < arr.length) {
            infixOrder(2 * index + 2);
        }
    }

    public void postOrder(int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("当前数组为空，无法执行前序遍历");
            return;
        }

        if (2 * index + 1 < arr.length) {
            postOrder(2 * index + 1);
        }

        if (2 * index + 2 < arr.length) {
            postOrder(2 * index + 2);
        }

        System.out.println("当前节点为:" + arr[index]);
    }

    public ArrayBinaryTree(int[] arr) {
        this.arr = arr;
    }

}

线索化二叉树

思路分析

问题：

将${ 1,3,6,8,10,14 }$构建成一颗二叉树，如下图

image-20241103201821509
  1. 当对上述中序遍历时：8，3，10，1，14，6
  2. 但是对于8，10，14，6这几个节点的左右指针没有充分利用
  3. 如果有个新需求——充分利用各个节点的指针，让每个节点可以指向自己的前后节点
  4. 解决方案：线索化二叉树

介绍：

  1. $n$个节点的二叉链表中含有$n+1$个空指针域（推导：$2n-(n-1)=n+1$）。利用二叉链表中的空指针域，存放指向该节点在某种遍历次序下的前驱节点和后驱节点，这种附加的指针称为“线索”。
  2. 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。分为前序线索二叉树、中序线索二叉树、后序线索二叉树。
  3. 一个节点的前一个节点，称前驱节点。
  4. 一个节点的后一个节点，称后继节点。

图解——将上述二叉树按中序遍历线索化：

image-20241104094103323

8号左指针指向较为特殊，通过代码运行逻辑可以得出。（特地标出来，是为了说明8的leftType = =1，为后续遍历中序线索化二叉树做铺垫）

但是有些问题：线索化后的二叉树，其left既可能指向左子树（如1），也可能指向其前驱节点（如10）；其right既可能指向后继节点（如8），也可能指向其右子树（如1、3）。

  • [x] 进一步简化、讲清楚找红色线索的方法！！！参考blog画出线索的方法，很简单，易于记忆！

画出线索的方法（重要！这是分析の方法）:

  1. 中序线索找法
    • 根据特定的遍历方式，写出最终的输出。例如上述想实现中序线索化，则先用中序遍历的思路看看——8，3，10，1，14，6
    • 根据这个输出顺序，给左或右为空的节点连接上对应的前驱节点、后继节点
    • 由于是中序，8号左边null。其余的：8右为3；10左为3，10右为1；1左右？不需要；14左1，14右6；6不需要左，最终6右不需要。
  2. 前序线索找法
    • 先用前序遍历得到输出：1，3，8，10，6，14
    • 给左或右为空的节点连接上对应的前驱节点、后继节点
    • 1不需要；3不需要；8左3，8右10；10左8，10右6；6右14；14左6，14右仍为null(经测：14的rightType==0)；
  3. 后序线索找法
    • 先用后序遍历得到输出：8，10，3，14，6，1
    • 给左或右为空的节点连接上对应的前驱节点、后继节点
    • 8左为null，8右为10；10左为8，10右为3；3不需要；14左为3，14右为1；6右为1；1不需要。

线索化代码流程：（步骤执行顺序的不同）

  1. 前序线索化：

    • 线索化当前节点：处理前驱结点+处理后继节点
    • 如果左节点的leftType == 0 ，再线索化左子树（左递归）
    • 如果右节点的rightType == 0，再线索化右子树（右递归）

    • 进入前序线索化，在进入左、右递归前！一定要判断某某Type == 0！不然会进入死递归！坐等StackOverflowError吧！

  2. 中序线索化：

    • 线索化左子树
    • 线索化当前节点：处理前驱结点+处理后继节点
    • 线索化右子树

  3. 后序线索化：

    • 线索化左子树
    • 线索化右子树
    • 线索化当前节点：处理前驱结点+处理后继节点

神奇吧，只有前序线索化在进入递归前需要判断……

  • [x] 必须要给threadedNode(HumanNode node)方法画一个图解！（这玩意的设置前驱节点和设置后继节点的代码部分并不是很直观、。而且，画图这一过程可以加深我的印象以及理解。）

图解–设置前驱结点、后继节点：

image-20241104090654992

代码实现

中序线索化

ThreadedBinaryTreeDemo

要点在于：在HumanNode中新增了leftType和rightType两个字段及对应getter、setter方法。

在ThreadedBinaryTree中使用了threadedNode方法用于(中序)线索化二叉树

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
package com.yukinoshita.dataStructure.tree.threadedBinaryTree;

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();

        HumanNode root = new HumanNode(1,"yukino");
        HumanNode node2 = new HumanNode(3,"yukinoshita");
        HumanNode node3 = new HumanNode(6,"yu");
        HumanNode node4 = new HumanNode(8,"kino");
        HumanNode node5 = new HumanNode(10,"yuKiNO");
        HumanNode node6 = new HumanNode(14,"shita");

        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNode();

        //测试是否线索化成功：
        System.out.printf("10号节点的前驱节点id为：%d \t 后继节点id为：%d",node5.getLeft().getId(),node5.getRight().getId());
        System.out.println("8号节点的右指针类型："+node4.getRightType());
//        System.out.println(node4.getLeft().getId());//注意，8号节点的left为null，因为此时prev == null。（调试发现）
        //虽然8号节点的leftType已经被设置为1，但是left指向为null。
    }
}


//线索化二叉树
class ThreadedBinaryTree {
    HumanNode root;

    private HumanNode prev = null;//在递归进行线索化时，prev总是为前一个节点

    public void setRoot(HumanNode root) {
        this.root = root;
    }

    //重载，自动从root节点开始线索化
    public void threadedNode(){
        this.threadedNode(root);
    }

    /**
     * 二叉树中进行线索化的方法（此为中序）
     *
     * @param node 当前需要线索化的节点
     */
    public void threadedNode(HumanNode node) {
        //如果node == null，不能线索化
        if (node == null) {
            return;
        }
        //1. 线索化左子树
        threadedNode(node.getLeft());

        //2. 线索化当前节点
        //处理当前节点的前驱节点
        if (node.getLeft() == null) {
            node.setLeft(prev);//让当前节点指向前驱节点
            node.setLeftType(1);//(修改指针类型)说明此时的左指针是指向前驱节点，非左子树
        }
        //处理后继节点
        if (prev != null && prev.getRight() == null) {//此时应该是node递归到了"下一个"，看看上一个prev的right是不是为空
            prev.setRight(node);        //这时才设置是设置后继节点的时候(画图理解)
            prev.setRightType(1);
        }

        prev = node;//每处理一个节点后，更新！

        //3. 线索化右子树
        threadedNode(node.getRight());
    }



}

class HumanNode {
    private int id;
    private String name;
    private HumanNode left;
    private HumanNode right;

    /*
        规定leftType == 0，指向的是左子树；为1，指向前驱节点
        规定rightType == 0，指向的是右子树；为1，指向后继节点
     */
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public HumanNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HumanNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HumanNode getLeft() {
        return left;
    }

    public void setLeft(HumanNode left) {
        this.left = left;
    }

    public HumanNode getRight() {
        return right;
    }

    public void setRight(HumanNode right) {
        this.right = right;
    }
}

前序线索化

threadedNode

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
/**
     * 前序线索化二叉树
     *
     * @param node 当前需要线索化的节点
     */
    public void threadedNode(HumanNode node) {
        if (node == null) {
            return;
        }
        //1. 线索化当前节点
        //1.1. 设置前驱节点
        if (node.getLeft() == null) {
            node.setLeft(prev);
            node.setLeftType(1);
        }
        //1.2. 设置后继节点
        if (prev != null && prev.getRight() == null) {
            prev.setRight(node);
            prev.setRightType(1);
        }
        prev = node;

        //2. 向左递归线索化，但是必须是有效节点
        if (node.getLeftType() == 0) {
            threadedNode(node.getLeft());
        }

        //3. 向右递归线索化
        if (node.getRightType() == 0) {
            threadedNode(node.getRight());
        }
    }

后序线索化

threadedNode

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
/**
 * 后序线索化二叉树
 *
 * @param node 当前需要线索化的节点
 */
public void threadedNode(HumanNode node) {
    if (node == null) {
        return;
    }
    //1. 向左递归线索化
    threadedNode(node.getLeft());

    //2. 向右递归线索化
    threadedNode(node.getRight());

    //3. 线索化当前节点
    //3.1. 设置前驱节点
    if (node.getLeft() == null) {
        node.setLeft(prev);
        node.setLeftType(1);
    }
    //3.2. 设置后继节点
    if (prev != null && prev.getRight() == null) {
        prev.setRight(node);
        prev.setRightType(1);
    }
    prev = node;
}

完整版

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
package com.yukinoshita.dataStructure.tree.threadedBinaryTree;

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();

        HumanNode root = new HumanNode(1, "yukino");
        HumanNode node2 = new HumanNode(3, "yukinoshita");
        HumanNode node3 = new HumanNode(6, "yu");
        HumanNode node4 = new HumanNode(8, "kino");
        HumanNode node5 = new HumanNode(10, "yuKiNO");
        HumanNode node6 = new HumanNode(14, "shita");

        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNode();

        //测试是否线索化成功：
        System.out.println("理应新增的线索测试：");
        System.out.printf("8号右边为：%d号节点\n", node4.getRight().getId());
        System.out.printf("10号左边为：%d号节点\n", node5.getLeft().getId());
        System.out.printf("10号右边为：%d号节点\n", node5.getRight().getId());
        System.out.printf("14号左边为：%d号节点\n", node6.getLeft().getId());
        System.out.printf("14号右边为：%d号节点\n", node6.getRight().getId());
        System.out.printf("6号右边为：%d号节点\n", node3.getRight().getId());
        
    }
}


//线索化二叉树
class ThreadedBinaryTree {
    HumanNode root;

    private HumanNode prev = null;//在递归进行线索化时，prev总是为前一个节点

    public void setRoot(HumanNode root) {
        this.root = root;
    }



    //重载，自动从root节点开始线索化
    public void threadedNode() {
        this.threadedNode(root);
    }

    /**
     * 后序线索化二叉树
     *
     * @param node 当前需要线索化的节点
     */
    public void threadedNode(HumanNode node) {
        if (node == null) {
            return;
        }
        //1. 向左递归线索化
        threadedNode(node.getLeft());

        //2. 向右递归线索化
        threadedNode(node.getRight());

        //3. 线索化当前节点
        //3.1. 设置前驱节点
        if (node.getLeft() == null) {
            node.setLeft(prev);
            node.setLeftType(1);
        }
        //3.2. 设置后继节点
        if (prev != null && prev.getRight() == null) {
            prev.setRight(node);
            prev.setRightType(1);
        }
        prev = node;
    }
}

class HumanNode {
    private int id;
    private String name;
    private HumanNode left;
    private HumanNode right;

    /*
        规定leftType == 0，指向的是左子树；为1，指向前驱节点
        规定rightType == 0，指向的是右子树；为1，指向后继节点
     */
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public HumanNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HumanNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HumanNode getLeft() {
        return left;
    }

    public void setLeft(HumanNode left) {
        this.left = left;
    }

    public HumanNode getRight() {
        return right;
    }

    public void setRight(HumanNode right) {
        this.right = right;
    }
}

遍历线索化二叉树

思路分析

要求：对已经(中序)线索化的二叉树采取相同策略(中序)的遍历方式。

问题：因为线索化后，各个节点的指向以发生变化，因此原先的遍历方式不能再使用，需要用新的遍历方式遍历线索化二叉树。

优点：由于各个节点可以通过线型方式遍历，所以无需使用递归，提高了遍历的效率。

代码实现

遍历中序线索化二叉树

ThreadedBinaryTreeDemo

新增threadedList遍历中序线索化二叉树方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//遍历中序线索化二叉树
public void threadedList() {
    HumanNode node = root;
    while (node != null) {

        //循环地找到leftType == 1的节点
        //对应中序遍历的 “左递归优先”
        while (node.getLeftType() == 0) {
            node = node.getLeft();
        }
        System.out.println(node);

        //如果当前节点的右指针指向后继节点，则一直输出
        while (node.getRightType() == 1) {
            node = node.getRight();
            System.out.println(node);
        }
        node = node.getRight();

    }
}

完整版

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
package com.yukinoshita.dataStructure.tree.threadedBinaryTree;

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();

        HumanNode root = new HumanNode(1, "yukino");
        HumanNode node2 = new HumanNode(3, "yukinoshita");
        HumanNode node3 = new HumanNode(6, "yu");
        HumanNode node4 = new HumanNode(8, "kino");
        HumanNode node5 = new HumanNode(10, "yuKiNO");
        HumanNode node6 = new HumanNode(14, "shita");

        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNode();

        //测试遍历中序线索化二叉树
        threadedBinaryTree.threadedList();// 8 3 10 1 14 6
    }
}


//线索化二叉树
class ThreadedBinaryTree {
    HumanNode root;

    private HumanNode prev = null;//在递归进行线索化时，prev总是为前一个节点

    public void setRoot(HumanNode root) {
        this.root = root;
    }

    //遍历中序线索化二叉树
    public void threadedList() {
        HumanNode node = root;
        while (node != null) {

            //循环地找到leftType == 1的节点
            //对应中序遍历的 “左递归优先”
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }
            System.out.println(node);

            //如果当前节点的右指针指向后继节点，则一直输出
            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }
            node = node.getRight();

        }
    }

    //重载，自动从root节点开始线索化
    public void threadedNode() {
        this.threadedNode(root);
    }

    /**
     * 二叉树中进行线索化的方法（此为中序）
     *
     * @param node 当前需要线索化的节点
     */
    public void threadedNode(HumanNode node) {
        //如果node == null，不能线索化
        if (node == null) {
            return;
        }
        //1. 线索化左子树
        threadedNode(node.getLeft());

        //2. 线索化当前节点
        //处理当前节点的前驱节点
        if (node.getLeft() == null) {
            node.setLeft(prev);//让当前节点指向前驱节点
            node.setLeftType(1);//(修改指针类型)说明此时的左指针是指向前驱节点，非左子树
        }
        //处理后继节点
        if (prev != null && prev.getRight() == null) {//此时应该是node递归到了"下一个"，看看上一个prev的right是不是为空
            prev.setRight(node);        //这时才设置是设置后继节点的时候(画图理解)
            prev.setRightType(1);
        }

        prev = node;//每处理一个节点后，更新！

        //3. 线索化右子树
        threadedNode(node.getRight());
    }


}

class HumanNode {
    private int id;
    private String name;
    private HumanNode left;
    private HumanNode right;

    /*
        规定leftType == 0，指向的是左子树；为1，指向前驱节点
        规定rightType == 0，指向的是右子树；为1，指向后继节点
     */
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public HumanNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HumanNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HumanNode getLeft() {
        return left;
    }

    public void setLeft(HumanNode left) {
        this.left = left;
    }

    public HumanNode getRight() {
        return right;
    }

    public void setRight(HumanNode right) {
        this.right = right;
    }
}

遍历前序线索化二叉树

threadedList

1
2
3
4
5
6
7
8
9
10
11
public void threadedList() {
    HumanNode node = root;
    while (node != null) {
        while (node.getLeftType() == 0) {//左指针不是线索
            System.out.println(node);//则边访问，边移动
            node = node.getLeft();
        }
        System.out.println(node);
        node = node.getRight();
    }
}

完整版：

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
package com.yukinoshita.dataStructure.tree.threadedBinaryTree;

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();

        HumanNode root = new HumanNode(1, "yukino");
        HumanNode node2 = new HumanNode(3, "yukinoshita");
        HumanNode node3 = new HumanNode(6, "yu");
        HumanNode node4 = new HumanNode(8, "kino");
        HumanNode node5 = new HumanNode(10, "yuKiNO");
        HumanNode node6 = new HumanNode(14, "shita");

        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNode();

        //测试是否线索化成功：
//        System.out.printf("10号节点的前驱节点id为：%d \t 后继节点id为：%d \n", node5.getLeft().getId(), node5.getRight().getId());
//        System.out.println("14号节点的左指针类型：" + node6.getLeftType());

        //测试遍历前序线索化二叉树是否成功：
        threadedBinaryTree.threadedList();
    }
}


//线索化二叉树
class ThreadedBinaryTree {
    HumanNode root;

    private HumanNode prev = null;//在递归进行线索化时，prev总是为前一个节点

    public void setRoot(HumanNode root) {
        this.root = root;
    }

    public void threadedList() {
        HumanNode node = root;
        while (node != null) {
            while (node.getLeftType() == 0) {//左指针不是线索
                System.out.println(node);//则边访问，边移动
                node = node.getLeft();
            }
            System.out.println(node);
            node = node.getRight();
        }
    }

    //重载，自动从root节点开始线索化
    public void threadedNode() {
        this.threadedNode(root);
    }

    /**
     * 前序线索化二叉树
     *
     * @param node 当前需要线索化的节点
     */
    public void threadedNode(HumanNode node) {
        if (node == null) {
            return;
        }
        //1. 线索化当前节点
        //1.1. 设置前驱节点
        if (node.getLeft() == null) {
            node.setLeft(prev);
            node.setLeftType(1);
        }
        //1.2. 设置后继节点
        if (prev != null && prev.getRight() == null) {
            prev.setRight(node);
            prev.setRightType(1);
        }
        prev = node;

        //2. 向左递归线索化，但是必须是有效节点
        if (node.getLeftType() == 0) {
            threadedNode(node.getLeft());
        }

        //3. 向右递归线索化
        if (node.getRightType() == 0) {
            threadedNode(node.getRight());
        }
    }
}

class HumanNode {
    private int id;
    private String name;
    private HumanNode left;
    private HumanNode right;

    /*
        规定leftType == 0，指向的是左子树；为1，指向前驱节点
        规定rightType == 0，指向的是右子树；为1，指向后继节点
     */
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public HumanNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HumanNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HumanNode getLeft() {
        return left;
    }

    public void setLeft(HumanNode left) {
        this.left = left;
    }

    public HumanNode getRight() {
        return right;
    }

    public void setRight(HumanNode right) {
        this.right = right;
    }
}

遍历后序线索化二叉树

threadedList

这个代码很复杂，已经需要使用三叉链表了。

引用自博客，暂时不深入思考、以及实现。

  • [ ] 有空再说。
image-20241104193040292

赫夫曼树

Huffman，赫夫曼，哈夫曼，霍夫曼。

基本概念介绍

  1. 路径和路径长度：从一个节点往下可以到达的孩子或孙子节点的通路，成为路径；通路中分支的数目称为路径长度。若根节点为第L层，则第L层的节点的路径长度为$L-1$
  2. 结点的权、带权路径长度：节点中含有一个有某种含义的数值，称为节点的权；路径长度*节点的权 = 带权路径长度
image-20241105200517736
  1. 树的带权路径长度：所有叶子节点的带权路径长度之和，称为树的带权路径长度，记为WPL（weighted path length），赫夫曼树的特点就是带权路径长度最短，也就是要让权值越大的节点离根节点越近。
  2. WPL最小的就是赫夫曼树，图解(e.g.中间的是赫夫曼树)：
image-20241105201026809

创建赫夫曼树

思路分析

构成赫夫曼树的步骤：

  1. 将数据从小到大排序(首次，将每个数据都看作根节点) / 或根据每棵树的根节点进行排序(非首次–or通用讲法)。
  2. 取出根节点权值最小的两颗二叉树
  3. 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
  4. 再将这颗新的二叉树，以根节点的权值大小再次排序（也就是回到第一步）。不断重复 ，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

简单理解：一，排序；二，取出最小两颗，组成新树，根节点为；三，回到第一步。（也就是图解中，三张图片为一轮）

图解：

以${ 15,8,6,1,20,10 }$为例

  • 执行第一步排序，得到${ 1,6,8,10,15,20 }$，相当于有6棵树，每棵树都是一个单独的节点：
image-20241105204913658
  • 第二步，取出最小的两颗二叉树；第三步，新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和。
image-20241105205229638
  • 第四步（也可以说是回到），再以新的这些树的根节点进行从小到大排序：
image-20241105205419103
  • 开始重复：再次执行第一步（上面已经排有序了）。
image-20241105210527613
  • 再排序：(注意！实际代码运行此处有差异！)
image-20241105210700873
  • 再取、再排：
image-20241105211006627
  • 再取、再排：
image-20241105211150432
  • 最后一步——赫夫曼树的降临：
image-20241105211319376

（上述仅能展示思路！！但是最终的二叉树视代码实现而定！！）

我的实现代码中，最终得到的huffmanTree就不是上面这个形状的，原因在于有一步的排序过程——出现了两个根节点为15的树。

我的代码中，采取的策略是——新生成的树都是在ArrayList末尾进行add，然后再排序，所以新生成、根节点为15的树应该在旧的那个之后……下面给出修改后过程（中间有所不同）

为什么前序遍历后怎么和预期不一样……问题就出在这里……

小结：赫夫曼树根据排序方式的不同，最终形成的赫夫曼树的结构也不同。但是WPL一致、最小。这里的"排序方法"语义较小，是指遇到相同元素的情况下，该如何排序。

image-20241106113028048 image-20241106113522437 image-20241106113642780 image-20241106113746002

所以代码的前序遍历应该为：

$60 \quad 25 \quad 10 \quad 15 \quad 35 \quad 15 \quad 7 \quad 1 \quad 6 \quad 8 \quad 20$

代码实现

HuffmanTree

主要代码：createHuffmanTree创建赫夫曼树

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
package com.yukinoshita.dataStructure.huffmanTree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr = {15, 8, 6, 1, 20, 10};
//        int[] arr = {13, 7, 8, 3, 29, 6,1};
//        int [] arr = {};
        Node root = createHuffmanTree(arr);
        preOrder(root);

    }

    public static void preOrder(Node root) {
        if (root == null) {
            System.out.println("huffman tree is empty");
        }else{
            root.preOrder();
        }
    }

    public static Node createHuffmanTree(int[] arr){
        if(arr.length ==0){
            return null;
        }
        List<Node> nodes = new ArrayList<Node>();
        for(int val:arr){
            nodes.add(new Node(val));
        }

        while(nodes.size() > 1){
            //排序
            Collections.sort(nodes);
            //取出最小
            Node leftNode = nodes.get(0);
            //取出次小
            Node rightNode = nodes.get(1);
            //构建新子树：
            Node newNode = new Node(leftNode.weight+ rightNode.weight,leftNode,rightNode);
            //删除已处理的，加入新的树
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(newNode);
        }

        //返回这棵树的根节点
        return nodes.get(0);
    }

}

class Node implements Comparable<Node> {
    int weight;
    Node left;
    Node right;

    Node(int weight) {
        this.weight = weight;
        this.left = null;
        this.right = null;
    }

    public Node(int weight, Node left, Node right) {
        this.weight = weight;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        //表示从小到大排
        return this.weight - o.weight;
    }

    //前序遍历：(用于测试)
    public void preOrder(){
        System.out.println(this);
        if(this.left != null) this.left.preOrder();
        if(this.right != null) this.right.preOrder();
    }
}



赫夫曼编码

思路分析

直接采用atguigu的介绍：视频链接。

基本介绍

赫夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法

赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。

赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%～90%之间

赫夫曼码是**可变字长编码(VLC)**的一种。Huffman于1952年提出一种编码方法，称之为最佳编码

原理：

  1. 通信领域中信息的处理方式1-定长编码

    • i like like like java do you like a java // 共40个字符(包括空格)
    • 105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97//对应Ascii码
    • 01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001//对应的二进制
    • 按照二进制来传递信息，总的长度是 359 (包括空格)
    • 在线转码工具

  2. 通信领域中信息的处理方式2-变长编码

    • i like like like java do you like a java // 共40个字符(包括空格)
    • d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 空格:9// 各个字符对应的个数
    • 0=空格 , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d 说明：按照各个字符出现的次数进行编码，原则是出现次数越多的，则编码越小，比如 空格出现了9 次， 编码为0 ,其它依次类推.
    • 按照上面给各个字符规定的编码，则我们在传输 “i like like like java do you like a java” 数据时，编码就是10010110100…

  • 但是这种编码方式不是前缀编码[^9]，会出现二义性。

  1. 通信领域中信息的处理方式3-赫夫曼编码

    • i like like like java do you like a java // 共40个字符(包括空格)

    • d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数

    • 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值。

赫夫曼编码详解：

传输的字符串为：i like like like java do you like a java

  1. 统计各个字符对应的个数d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9
  2. 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值（字符也要传入）

也就是传入$arr=[1,1,1,2,2,2,4,4,4,5,5,9]$去创建赫夫曼树：

构成赫夫曼树的步骤：

  1. 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树

  2. 取出根节点权值最小的两颗二叉树

  3. 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和

  4. 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

image-20241106133401235
  1. 根据赫夫曼树，给各个字符,规定编码 (前缀编码)， 向左的路径为0 向右的路径为1 ， 编码如下：o:000 u: 10010 d: 100110 y: 100111 i: 101a : 110 k: 1110 e: 1111 j: 0000 v: 0001l: 001 : 01
  2. 按照上面的赫夫曼编码，我们的"i like like like java do you like a java" 字符串对应的编码为 (注意这里我们使用的无损压缩)1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110通过赫夫曼编码处理 长度为 133
  3. 长度为:133 说明:原来长度是 359 , 压缩了 (359-133) / 359 = 62.9%。此编码满足前缀编码,，即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性。赫夫曼编码是无损处理方案。

数据压缩

思路：

  1. Node { data (存放数据)， weight (权值)， left 和 right }
  2. 得到 “i like like like java do you like a java” 对应的 byte[] 数组
  3. 编写一个方法，将准备构建赫夫曼树的Node 节点放到 List , 形式 [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]…], 体现 d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9
  4. 可以通过List 创建对应的赫夫曼树

代码解释：

这个代码过程较多，但是每一部分并不难。
简单归纳下：总体的目标是把原始数据对应的byte[] 压缩为更小的byte[]

  1. 获取原始数据的byte[]

  2. 将这个根据这个byte[]构建赫夫曼树，规则详见创建赫夫曼树，这里简单回顾：

    • 排序-》取出两个最小的节点，构成新节点-》删除两个最小节点，将新的节点加入到数组-》只要数组长度大于1，就循环整个操作-》最后通过nodesArray.get(0)就获取到了赫夫曼树的根节点。
    image-20241106163538269

  3. 创建赫夫曼树后，就要利用赫夫曼树，得到对应的赫夫曼编码，规则为——为每一个叶子节点的值data编一个"码"，这个码就是从根节点到叶子节点的路径，每向左拼接一个"0"，每向右拼接一个"1"。最终得到赫夫曼编码，存放在Map<key,value>中，key就是数据，比如97('a’的ASCII)，value就是对应的码，比如01

image-20241106163609031
  1. 根据这个赫夫曼编码，可以将原始数据压缩，压缩过程又细分两步：
    1. 由于光是通过赫夫曼编码处理后，得到的只是"0100110101010…"这样的字符串，甚至比原先的字符串还长，所以要将这个字符串转换为8位一个的byte
    2. 第二步就是转换，不足8位就截断。huffmanCodeBytes[k] = (byte) Integer.parseInt(strByte, 2);其中，strByte是每次取了8位（不足就截断）。
  2. 最后得到的huffmanCodeBytes就是最终结果（类型为byte[]，且长度比str.getBytes()要短，就做到了压缩）
image-20241106164313508

可能需要补充的知识？

原码、反码、补码的转换。（也就是在压缩过程，为什么从"10101000"变成huffmanCodeBytes中的-88）

10101000(补码)->10100111(反码)->11011000(原码)

补码-1 = 反码；符号位不变，反码取反=原码。原码对应值计算为-88。

实现1

HuffmanCode

若对此代码不懂，再看一遍：p117至p120。

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
package com.yukinoshita.dataStructure.huffmanCode;

import java.util.*;

public class HuffmanCode {
    public static void main(String[] args) {
        String str = "i like like like java do you like a java";
        byte[] contentBytes = str.getBytes();
        System.out.println("还未压缩前的长度：" + contentBytes.length);
        List<Node> nodes = getNodes(contentBytes);
        System.out.println("nodes：" + nodes);

        System.out.println("创建赫夫曼树为：");
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        huffmanTreeRoot.preOrder();

        //测试是否生成了对应的huffman编码
//        getCodes(huffmanTreeRoot,"",stringBuilder);
//        getCodes(huffmanTreeRoot);
        Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot); //(其实不新生成也行，如上)
        System.out.println("生成的赫夫曼编码为：" + HuffmanCode.huffmanCodes);

        byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
        System.out.println("huffmanCodeBytes："+Arrays.toString(huffmanCodeBytes));
        System.out.println("压缩率为:"+(contentBytes.length-huffmanCodeBytes.length * 1.0) / contentBytes.length * 1.0);

    }

    /**
     * 将一个字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回压缩后的byte[]
     *
     * @param bytes        原始字符串对应的byte数组
     * @param huffmanCodes (根据字符串)生成的赫夫曼编码
     * @return 赫夫曼编码压缩处理后的byte数组
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }
//        System.out.println("测试：stringBuilder: "+stringBuilder.toString());
        //将"010001000101010101010..."转成byte数组
        //或者：int len =(stringBuilder.length() + 7) / 8;
        int len;
        if (stringBuilder.length() % 8 == 0) {
            len = stringBuilder.length() / 8;
        } else {
            len = stringBuilder.length() / 8 + 1;
        }
        //创建 存储压缩后的by数组
        byte[] huffmanCodeBytes = new byte[len];
        for (int i = 0, k = 0; i < stringBuilder.length(); i += 8, k++) {//因为是每8位对应一个byte
            String strByte;
            if (i + 8 > stringBuilder.length()) {//不够8位
                strByte = stringBuilder.substring(i);
            }else{
                strByte = stringBuilder.substring(i, i + 8);
            }
            //将strByte 转成一个byte，放入到huffmanCodeBytes
            huffmanCodeBytes[k] = (byte) Integer.parseInt(strByte, 2);
        }
        return huffmanCodeBytes;
    }

    //为了调用getCodes方便，重载一下：
    private static Map<Byte, String> getCodes(Node node) {
        if (node == null) {
            return null;
        }
        getCodes(node.left, "0", stringBuilder);
        getCodes(node.right, "1", stringBuilder);
        return huffmanCodes;
    }


    //生成赫夫曼树对应的赫夫曼编码
    //思路：
    //1. 将赫夫曼编码表放在Map<Byte,String>  键:值 = ASCII:码  e.g. 97:001
    static Map<Byte, String> huffmanCodes = new HashMap<>();
    //2. 在生成赫夫曼编码表时，需要去拼接路径，故用一个StringBuilder存储某个叶子节点的路径
    static StringBuilder stringBuilder = new StringBuilder();

    /**
     * 得到传入的node节点所有的叶子节点的赫夫曼编码，存放到huffmanCodes中
     *
     * @param node          传入节点
     * @param code          路径(左边为0，右边为1)
     * @param stringBuilder 用于拼接路径
     */
    private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder builder = new StringBuilder(stringBuilder);
        //将code加入到builder
        builder.append(code);
        if (node != null) {//node为空不处理
            if (node.data == null) {//说明node为非叶子节点
                //递归处理
                getCodes(node.left, "0", builder);//向左
                getCodes(node.right, "1", builder);//向右
            } else {//是叶子节点
                huffmanCodes.put(node.data, builder.toString());
            }
        }
    }

    /**
     * @param bytes 接收字节数组
     * @return 返回一个List，形式：[Node[data:97,weight=5], Node[data:32,weight:9],...]
     */
    private static List<Node> getNodes(byte[] bytes) {
        ArrayList<Node> nodes = new ArrayList<>();

        //遍历bytes，统计每一个byte出现的次数->Map
        Map<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) {//Map还没有这个字符数据
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }
        }

        //把每一个键值对转成一个Node对象，并加入到nodes集合
        //遍历map
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    private static Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            Collections.sort(nodes);

            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            Node newNode = new Node(null, leftNode.weight + rightNode.weight);
            newNode.left = leftNode;
            newNode.right = rightNode;

            nodes.remove(0);
            nodes.remove(0);
            nodes.add(newNode);
        }
        return nodes.get(0);
    }
}

class Node implements Comparable<Node> {
    Byte data;//存放数据，如'a'
    int weight;
    Node left, right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    //前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}

封装后实现2

HuffmanCode

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
package com.yukinoshita.dataStructure.huffmanCode;

import java.util.*;

public class HuffmanCode {
    public static void main(String[] args) {
        //输入的原始数据
        String str = "i like like like java do you like a java";
        byte[] contentBytes = str.getBytes();//得到其byte数组
        byte[] huffmanBytes = huffmanZip(contentBytes);
        System.out.println("压缩后："+Arrays.toString(huffmanBytes));
//        对此部分进行封装：
//        System.out.println("还未压缩前的长度：" + contentBytes.length);
//
//        //通过getNodes方法得到byte[]数组对应的节点（）
//        List<Node> nodes = getNodes(contentBytes);
//        System.out.println("nodes：" + nodes);
//
//        System.out.println("创建赫夫曼树为：");
//        Node huffmanTreeRoot = createHuffmanTree(nodes);
//        huffmanTreeRoot.preOrder();
//
//        //测试是否生成了对应的huffman编码
////        getCodes(huffmanTreeRoot,"",stringBuilder);
////        getCodes(huffmanTreeRoot);
//        Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot); //(其实不新生成也行，如上)
//        System.out.println("生成的赫夫曼编码为：" + HuffmanCode.huffmanCodes);
//
//        byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
//        System.out.println("huffmanCodeBytes："+Arrays.toString(huffmanCodeBytes));
//        System.out.println("压缩率为:"+(contentBytes.length-huffmanCodeBytes.length * 1.0) / contentBytes.length * 1.0);

    }

    //将方法进行封装，使得调用方便

    /**
     *
     * @param bytes 原始字符串对应的字节数组
     * @return 经过赫夫曼编码处理后的字节数组
     */
    public static byte[] huffmanZip(byte[] bytes){
        List<Node> nodes = getNodes(bytes);
        //根据nodes创建huffmanTree
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        //根据huffmanTree获得赫夫曼编码
        Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
        //根据赫夫曼编码对原始数据对应的字节码数组进行压缩
//        byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
//        return huffmanCodeBytes;
        return zip(bytes,huffmanCodes);
    }

    /**
     * 将一个字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回压缩后的byte[]
     *
     * @param bytes        原始字符串对应的byte数组
     * @param huffmanCodes (根据字符串)生成的赫夫曼编码
     * @return 赫夫曼编码压缩处理后的byte数组
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }
//        System.out.println("测试：stringBuilder: "+stringBuilder.toString());
        //将"010001000101010101010..."转成byte数组
        //或者：int len =(stringBuilder.length() + 7) / 8;
        int len;
        if (stringBuilder.length() % 8 == 0) {
            len = stringBuilder.length() / 8;
        } else {
            len = stringBuilder.length() / 8 + 1;
        }
        //创建 存储压缩后的by数组
        byte[] huffmanCodeBytes = new byte[len];
        for (int i = 0, k = 0; i < stringBuilder.length(); i += 8, k++) {//因为是每8位对应一个byte
            String strByte;
            if (i + 8 > stringBuilder.length()) {//不够8位
                strByte = stringBuilder.substring(i);
            }else{
                strByte = stringBuilder.substring(i, i + 8);
            }
            //将strByte 转成一个byte，放入到huffmanCodeBytes
            huffmanCodeBytes[k] = (byte) Integer.parseInt(strByte, 2);
        }
        return huffmanCodeBytes;
    }

    //为了调用getCodes方便，重载一下：
    private static Map<Byte, String> getCodes(Node node) {
        if (node == null) {
            return null;
        }
        getCodes(node.left, "0", stringBuilder);
        getCodes(node.right, "1", stringBuilder);
        return huffmanCodes;
    }


    //生成赫夫曼树对应的赫夫曼编码
    //思路：
    //1. 将赫夫曼编码表放在Map<Byte,String>  键:值 = ASCII:码  e.g. 97:001
    static Map<Byte, String> huffmanCodes = new HashMap<>();
    //2. 在生成赫夫曼编码表时，需要去拼接路径，故用一个StringBuilder存储某个叶子节点的路径
    static StringBuilder stringBuilder = new StringBuilder();

    /**
     * 得到传入的node节点所有的叶子节点的赫夫曼编码，存放到huffmanCodes中
     *
     * @param node          传入节点
     * @param code          路径(左边为0，右边为1)
     * @param stringBuilder 用于拼接路径
     */
    private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder builder = new StringBuilder(stringBuilder);
        //将code加入到builder
        builder.append(code);
        if (node != null) {//node为空不处理
            if (node.data == null) {//说明node为非叶子节点
                //递归处理
                getCodes(node.left, "0", builder);//向左
                getCodes(node.right, "1", builder);//向右
            } else {//是叶子节点
                huffmanCodes.put(node.data, builder.toString());
            }
        }
    }

    /**
     * 需要对每一个字符出现的次数做统计，统计出来的数字即为weight
     * 换言之，weight反映了这个字符在原数据（str）中出现的频率
     * 频率越高，自然，后续构建赫夫曼树时，就要将它放到距离根节点较近的位置上。
     * @param bytes 接收字节数组
     * @return 返回一个List，形式：[Node[data:97,weight=5], Node[data:32,weight:9],...]
     */
    private static List<Node> getNodes(byte[] bytes) {
        ArrayList<Node> nodes = new ArrayList<>();

        //遍历bytes，统计每一个byte出现的次数->Map
        Map<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) {//Map还没有这个字符数据
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }
        }

        //把每一个键值对转成一个Node对象，并加入到nodes集合
        //遍历map
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    private static Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            Collections.sort(nodes);

            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            Node newNode = new Node(null, leftNode.weight + rightNode.weight);
            newNode.left = leftNode;
            newNode.right = rightNode;

            nodes.remove(0);
            nodes.remove(0);
            nodes.add(newNode);
        }
        return nodes.get(0);
    }
}

class Node implements Comparable<Node> {
    Byte data;//存放数据，如'a'
    int weight;
    Node left, right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    //前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}

数据解压

思路：

  1. 将赫夫曼压缩后的字节数组 转换为 二进制字符串。使用byteToBitString方法
  2. 再将这个二进制字符串 对照 赫夫曼编码 转换为原始字符串。使用decode方法

HuffmanCode

注意：此代码有bug（没修）——如果最后

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
package com.yukinoshita.dataStructure.huffmanCode;

import java.util.*;

public class HuffmanCode {
    public static void main(String[] args) {
        String str = "i like like like java do you like a java";
        byte[] contentBytes = str.getBytes();//得到其byte数组
        byte[] huffmanCodeBytes = huffmanZip(contentBytes);
        System.out.println("压缩后：" + Arrays.toString(huffmanCodeBytes));

        byte[] sourceBytes = decode(huffmanCodes, huffmanCodeBytes);
        System.out.println(new String(sourceBytes));

    }

    /**
     * 对数据解码的方法
     * @param huffmanCodes 赫夫曼编码表map
     * @param huffmanBytes 赫夫曼编码得到的字节数组
     * @return 原来字符串对应的数组
     */
    private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        //1. 先得到huffmanBytes对应的二进制字符串（010100010）
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < huffmanBytes.length; i++) {
            //判断是不是最后一个字节
            boolean flag = (i == huffmanBytes.length - 1);
            byte b = huffmanBytes[i];
            stringBuilder.append(byteToBitString(!flag, b));
        }
//        System.out.println("测试：赫夫曼字节数组对应的二进制字符串"+stringBuilder.toString());
        //把二进制字符串按照赫夫曼表进行解码
        //把赫夫曼表进行调换，因为要反向查询。
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
//        System.out.println("测试："+map);

        //创建一个List，存放byte
        List<Byte> list = new ArrayList<>();
        for (int i = 0; i < stringBuilder.length();) {
            int count = 1;
            boolean flag = true;
            Byte b = null;
            while (flag) {
                String key = stringBuilder.substring(i, i + count);//i不动，让count移动
                b = map.get(key);
                if (b == null) {//说明没有匹配到
                    count++;
                } else {
                    flag = false;
                }
            }
            list.add(b);
            i += count;
        }
        //for结束后，list中就存放了所有的字符
        //还要把list中的数据放入byte[]并返回
        byte[] bytes = new byte[list.size()];
        for (int i = 0; i < bytes.length; i++) {
            bytes[i] = list.get(i);
        }
        return bytes;
    }


    /**
     * 讲一个byte转成一个二进制字符串
     *
     * @param flag 高位需要补位（true），不需要（false）
     * @param b    传入的byte值
     * @return 该byte对应的二进制的字符串（补码形式返回）
     */
    private static String byteToBitString(boolean flag, byte b) {
        int temp = b;//将b转成int
        //如果是正数，还需要补高位
        if (flag) {
            temp |= 256;//按位或256
        }
        String str = Integer.toBinaryString(temp);//返回的是temp对应的二进制的补码
        if (flag || temp < 0) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }

    }

    //将方法进行封装，使得调用方便

    /**
     * @param bytes 原始字符串对应的字节数组
     * @return 经过赫夫曼编码处理后的字节数组
     */
    public static byte[] huffmanZip(byte[] bytes) {
        List<Node> nodes = getNodes(bytes);
        //根据nodes创建huffmanTree
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        //根据huffmanTree获得赫夫曼编码
        Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
        //根据赫夫曼编码对原始数据对应的字节码数组进行压缩
//        byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
//        return huffmanCodeBytes;
        return zip(bytes, huffmanCodes);
    }

    /**
     * 将一个字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回压缩后的byte[]
     *
     * @param bytes        原始字符串对应的byte数组
     * @param huffmanCodes (根据字符串)生成的赫夫曼编码
     * @return 赫夫曼编码压缩处理后的byte数组
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }
//        System.out.println("测试：stringBuilder: "+stringBuilder.toString());
        //将"010001000101010101010..."转成byte数组
        //或者：int len =(stringBuilder.length() + 7) / 8;
        int len;
        if (stringBuilder.length() % 8 == 0) {
            len = stringBuilder.length() / 8;
        } else {
            len = stringBuilder.length() / 8 + 1;
        }
        //创建 存储压缩后的by数组
        byte[] huffmanCodeBytes = new byte[len];
        for (int i = 0, k = 0; i < stringBuilder.length(); i += 8, k++) {//因为是每8位对应一个byte
            String strByte;
            if (i + 8 > stringBuilder.length()) {//不够8位
                strByte = stringBuilder.substring(i);
            } else {
                strByte = stringBuilder.substring(i, i + 8);
            }
            //将strByte 转成一个byte，放入到huffmanCodeBytes
            huffmanCodeBytes[k] = (byte) Integer.parseInt(strByte, 2);
        }
        return huffmanCodeBytes;
    }

    //为了调用getCodes方便，重载一下：
    private static Map<Byte, String> getCodes(Node node) {
        if (node == null) {
            return null;
        }
        getCodes(node.left, "0", stringBuilder);
        getCodes(node.right, "1", stringBuilder);
        return huffmanCodes;
    }


    //生成赫夫曼树对应的赫夫曼编码
    //思路：
    //1. 将赫夫曼编码表放在Map<Byte,String>  键:值 = ASCII:码  e.g. 97:001
    static Map<Byte, String> huffmanCodes = new HashMap<>();
    //2. 在生成赫夫曼编码表时，需要去拼接路径，故用一个StringBuilder存储某个叶子节点的路径
    static StringBuilder stringBuilder = new StringBuilder();

    /**
     * 得到传入的node节点所有的叶子节点的赫夫曼编码，存放到huffmanCodes中
     *
     * @param node          传入节点
     * @param code          路径(左边为0，右边为1)
     * @param stringBuilder 用于拼接路径
     */
    private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder builder = new StringBuilder(stringBuilder);
        //将code加入到builder
        builder.append(code);
        if (node != null) {//node为空不处理
            if (node.data == null) {//说明node为非叶子节点
                //递归处理
                getCodes(node.left, "0", builder);//向左
                getCodes(node.right, "1", builder);//向右
            } else {//是叶子节点
                huffmanCodes.put(node.data, builder.toString());
            }
        }
    }

    /**
     * 需要对每一个字符出现的次数做统计，统计出来的数字即为weight
     * 换言之，weight反映了这个字符在原数据（str）中出现的频率
     * 频率越高，自然，后续构建赫夫曼树时，就要将它放到距离根节点较近的位置上。
     *
     * @param bytes 接收字节数组
     * @return 返回一个List，形式：[Node[data:97,weight=5], Node[data:32,weight:9],...]
     */
    private static List<Node> getNodes(byte[] bytes) {
        ArrayList<Node> nodes = new ArrayList<>();

        //遍历bytes，统计每一个byte出现的次数->Map
        Map<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) {//Map还没有这个字符数据
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }
        }

        //把每一个键值对转成一个Node对象，并加入到nodes集合
        //遍历map
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    private static Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            Collections.sort(nodes);

            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            Node newNode = new Node(null, leftNode.weight + rightNode.weight);
            newNode.left = leftNode;
            newNode.right = rightNode;

            nodes.remove(0);
            nodes.remove(0);
            nodes.add(newNode);
        }
        return nodes.get(0);
    }
}

class Node implements Comparable<Node> {
    Byte data;//存放数据，如'a'
    int weight;
    Node left, right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    //前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}

文件的压缩和解压

zipFile方法和unZipFile方法

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
package com.yukinoshita.dataStructure.huffmanCode;

import java.io.*;
import java.util.*;

public class HuffmanCode {
    public static void main(String[] args) {
        //测试压缩文件
//        String srcFile = "C:\\Users\\26423\\Desktop\\ceshi22.bmp";
//        String dstFile ="C:\\Users\\26423\\Desktop\\ceshi22.zip";
//        zipFile(srcFile, dstFile);
//        System.out.println("压缩文件成功");

        //测试解压文件
        String zipFile = "C:\\Users\\26423\\Desktop\\ceshi22.zip";
        String dstFile = "C:\\Users\\26423\\Desktop\\ceshi2333.bmp";
        unZipFile(zipFile, dstFile);
        System.out.println("解压文件成功");
    }

    /**
     * 完成对文件的解压
     * @param zipFile 准备解压文件
     * @param dstFile 将文件解压到哪个路径
     */
    public static void unZipFile(String zipFile, String dstFile) {
        //定义文件输入流
        InputStream is = null;
        //定义对象输入流
        ObjectInputStream ois = null;
        //定义文件输出流
        OutputStream os = null;

        try{
            //创建文件输入流
            is = new FileInputStream(zipFile);
            //创建一个和 is关联的对象输入流
            ois = new ObjectInputStream(is);
            //读取byte数组 huffmanCodes
            byte[] huffmanBytes = (byte[])ois.readObject();
            //读取赫夫曼编码表
            Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();

            //解码
            byte[] bytes = decode(huffmanCodes, huffmanBytes);
            //将bytes写入到目标文件
            os = new FileOutputStream(dstFile);
            //写数据到dstFile文件
            os.write(bytes);
        }catch(Exception e){
            System.out.println(e.getMessage());
        }finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (IOException e) {
                System.out.println(e.getMessage());
            }
        }


    }

    /**
     * 对文件进行压缩
     * @param srcFile 希望压缩的文件的完整路径
     * @param dstFile 压缩后的文件放到哪个目录下
     */
    public static void zipFile(String srcFile,String dstFile){
        //创建输出流

        //创建文件的输入流
        FileInputStream is = null;
        //创建输出流
        FileOutputStream os = null;
        ObjectOutputStream oos = null;
        try {
            is = new FileInputStream(srcFile);
            //创建一个和源文件大小一样的byte[]
            byte[] b = new byte[is.available()];
            //读取文件
            is.read(b);
            //直接对源文件压缩
            byte[] huffmanBytes = huffmanZip(b);
            //创建文件的输出流,存放压缩文件
            os = new FileOutputStream(dstFile);
            //创建一个和文件输出流关联的ObjectOutputStream
            oos = new ObjectOutputStream(os);
            //把赫夫曼编码后的字节数组写入压缩文件
            oos.writeObject(huffmanBytes);
            //这里以对象流的形式写入 赫夫曼编码（是为了以后恢复源文件时使用）
            //注意一定要把赫夫曼编码写入压缩文件（不然恢复不了）
            oos.writeObject(huffmanCodes);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        } finally {
            try {
                is.close();
                oos.close();
                os.close();
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }
        }
    }

    /**
     * 对数据解码的方法
     * @param huffmanCodes 赫夫曼编码表map
     * @param huffmanBytes 赫夫曼编码得到的字节数组
     * @return 原来字符串对应的数组
     */
    private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        //1. 先得到huffmanBytes对应的二进制字符串（010100010）
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < huffmanBytes.length; i++) {
            //判断是不是最后一个字节
            boolean flag = (i == huffmanBytes.length - 1);
            byte b = huffmanBytes[i];
            stringBuilder.append(byteToBitString(!flag, b));
        }
//        System.out.println("测试：赫夫曼字节数组对应的二进制字符串"+stringBuilder.toString());
        //把二进制字符串按照赫夫曼表进行解码
        //把赫夫曼表进行调换，因为要反向查询。
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
//        System.out.println("测试："+map);

        //创建一个List，存放byte
        List<Byte> list = new ArrayList<>();
        for (int i = 0; i < stringBuilder.length();) {
            int count = 1;
            boolean flag = true;
            Byte b = null;
            while (flag) {
                String key = stringBuilder.substring(i, i + count);//i不动，让count移动
                b = map.get(key);
                if (b == null) {//说明没有匹配到
                    count++;
                } else {
                    flag = false;
                }
            }
            list.add(b);
            i += count;
        }
        //for结束后，list中就存放了所有的字符
        //还要把list中的数据放入byte[]并返回
        byte[] bytes = new byte[list.size()];
        for (int i = 0; i < bytes.length; i++) {
            bytes[i] = list.get(i);
        }
        return bytes;
    }


    /**
     * 讲一个byte转成一个二进制字符串
     *
     * @param flag 高位需要补位（true），不需要（false）
     * @param b    传入的byte值
     * @return 该byte对应的二进制的字符串（补码形式返回）
     */
    private static String byteToBitString(boolean flag, byte b) {
        int temp = b;//将b转成int
        //如果是正数，还需要补高位
        if (flag) {
            temp |= 256;//按位或256
        }
        String str = Integer.toBinaryString(temp);//返回的是temp对应的二进制的补码
        if (flag || temp < 0) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }

    }

    //将方法进行封装，使得调用方便

    /**
     * @param bytes 原始字符串对应的字节数组
     * @return 经过赫夫曼编码处理后的字节数组
     */
    public static byte[] huffmanZip(byte[] bytes) {
        List<Node> nodes = getNodes(bytes);
        //根据nodes创建huffmanTree
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        //根据huffmanTree获得赫夫曼编码
        Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
        //根据赫夫曼编码对原始数据对应的字节码数组进行压缩
//        byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
//        return huffmanCodeBytes;
        return zip(bytes, huffmanCodes);
    }

    /**
     * 将一个字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回压缩后的byte[]
     *
     * @param bytes        原始字符串对应的byte数组
     * @param huffmanCodes (根据字符串)生成的赫夫曼编码
     * @return 赫夫曼编码压缩处理后的byte数组
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }
//        System.out.println("测试：stringBuilder: "+stringBuilder.toString());
        //将"010001000101010101010..."转成byte数组
        //或者：int len =(stringBuilder.length() + 7) / 8;
        int len;
        if (stringBuilder.length() % 8 == 0) {
            len = stringBuilder.length() / 8;
        } else {
            len = stringBuilder.length() / 8 + 1;
        }
        //创建 存储压缩后的by数组
        byte[] huffmanCodeBytes = new byte[len];
        for (int i = 0, k = 0; i < stringBuilder.length(); i += 8, k++) {//因为是每8位对应一个byte
            String strByte;
            if (i + 8 > stringBuilder.length()) {//不够8位
                strByte = stringBuilder.substring(i);
            } else {
                strByte = stringBuilder.substring(i, i + 8);
            }
            //将strByte 转成一个byte，放入到huffmanCodeBytes
            huffmanCodeBytes[k] = (byte) Integer.parseInt(strByte, 2);
        }
        return huffmanCodeBytes;
    }

    //为了调用getCodes方便，重载一下：
    private static Map<Byte, String> getCodes(Node node) {
        if (node == null) {
            return null;
        }
        getCodes(node.left, "0", stringBuilder);
        getCodes(node.right, "1", stringBuilder);
        return huffmanCodes;
    }


    //生成赫夫曼树对应的赫夫曼编码
    //思路：
    //1. 将赫夫曼编码表放在Map<Byte,String>  键:值 = ASCII:码  e.g. 97:001
    static Map<Byte, String> huffmanCodes = new HashMap<>();
    //2. 在生成赫夫曼编码表时，需要去拼接路径，故用一个StringBuilder存储某个叶子节点的路径
    static StringBuilder stringBuilder = new StringBuilder();

    /**
     * 得到传入的node节点所有的叶子节点的赫夫曼编码，存放到huffmanCodes中
     *
     * @param node          传入节点
     * @param code          路径(左边为0，右边为1)
     * @param stringBuilder 用于拼接路径
     */
    private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder builder = new StringBuilder(stringBuilder);
        //将code加入到builder
        builder.append(code);
        if (node != null) {//node为空不处理
            if (node.data == null) {//说明node为非叶子节点
                //递归处理
                getCodes(node.left, "0", builder);//向左
                getCodes(node.right, "1", builder);//向右
            } else {//是叶子节点
                huffmanCodes.put(node.data, builder.toString());
            }
        }
    }

    /**
     * 需要对每一个字符出现的次数做统计，统计出来的数字即为weight
     * 换言之，weight反映了这个字符在原数据（str）中出现的频率
     * 频率越高，自然，后续构建赫夫曼树时，就要将它放到距离根节点较近的位置上。
     *
     * @param bytes 接收字节数组
     * @return 返回一个List，形式：[Node[data:97,weight=5], Node[data:32,weight:9],...]
     */
    private static List<Node> getNodes(byte[] bytes) {
        ArrayList<Node> nodes = new ArrayList<>();

        //遍历bytes，统计每一个byte出现的次数->Map
        Map<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) {//Map还没有这个字符数据
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }
        }

        //把每一个键值对转成一个Node对象，并加入到nodes集合
        //遍历map
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    private static Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            Collections.sort(nodes);

            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            Node newNode = new Node(null, leftNode.weight + rightNode.weight);
            newNode.left = leftNode;
            newNode.right = rightNode;

            nodes.remove(0);
            nodes.remove(0);
            nodes.add(newNode);
        }
        return nodes.get(0);
    }
}

class Node implements Comparable<Node> {
    Byte data;//存放数据，如'a'
    int weight;
    Node left, right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    //前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}

文件压缩注意事项

  1. 如果文件本身就是经过压缩的，那么使用赫夫曼编码压缩后大小不会有明显变化，比如视频、ppt、png。
  2. 赫夫曼编码是按字节来处理的，因此可以处理所有文件（二进制文件、文本文件）(.xml)
  3. 如果一个文件中的内容重复数据不多，压缩效果也不会很明显。

二叉搜索树

基本介绍

二叉搜索树，BST(Binary Search Tree)，对于二叉搜索树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。如果有相同的值，可以放在左子节点或右子节点。

二叉搜索树的创建和遍历

新加入节点时：

  1. 若新加入节点为空，直接返回。
  2. 比较插入值和当前节点值大小，若小于当前节点值，判断左节点是否为空，若为空，直接插入到左节点，否则向左递归地插入
  3. 否则（大于等于），判断右节点是否为空，若为空则直接插入到右节点，否则向右递归地插入

BinarySearchTreeDemo

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
package com.yukinoshita.dataStructure.binarySearchTree;


public class BinarySearchTreeDemo {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] arr = {7, 8, 2, 1, 13, 5};
        for (int i = 0; i < arr.length; i++) {
            bst.add(new Node(arr[i]));
        }
        System.out.println("测试二叉搜索树的中序遍历：");
        bst.inOrder();//发现刚好是升序
    }
}

class BinarySearchTree {
    private Node root;

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.addNode(node);
        }
    }

    public void inOrder() {
        root.inOrder();
    }
}

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    //递归地添加节点的方法
    public void addNode(Node node) {
        if (node == null) return;

        if (this.value < node.value) {
            if (this.right != null) this.right.addNode(node);
            else this.right = node;
        } else {
            if (this.left != null) this.left.addNode(node);
            else this.left = node;
        }
    }

    //中序遍历
    public void inOrder() {
        if (this.left != null) this.left.inOrder();
        System.out.println(this);
        if (this.right != null) this.right.inOrder();
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

二叉搜索树节点的删除

思路分析

由于删除时情况较多（但是不难），所以还是需要理一下所有可能的情况

分以下三种情况：

  1. 删除叶子节点
  2. 删除只有1颗子树的节点
  3. 删除有2颗子树的节点

具体思路：

image-20241108193248201

  1. 若删除叶子节点

    • 先要找到目标节点targetNode
    • 在找的同时，要用parentNode标记其父节点
    • 确定targetNode是parentNode的左子节点还是右子节点，再删除。

  2. 删除只有一颗子树的节点

    • 先要找到目标节点targetNode
    • 在找的同时，要用parentNode标记其父节点
    • 确定targetNode是parentNode的左子节点还是右子节点，以及确定targetNode是有左子树还是右子树
    • 因此有四种情况：
      • targetNode是parentNode的左子节点，targetNode有左子树——parent.left = targetNode.left
      • targetNode是parentNode的左子节点，targetNode有右子树——parent.left = targetNode.right
      • targetNode是parentNode的右子节点，targetNode有左子树——parent.right = targetNode.left
      • targetNode是parentNode的右子节点，targetNode有右子树——parent.right = targetNode.right
    • 删除5为例：image-20241108193304227

  3. 删除有两颗子树的节点

    • 先要找到目标节点targetNode

    • 在找的同时，要用parentNode标记其父节点

    • 从targetNode的右子树里找到最小的节点 （或从targetNode的左子树里找最大的节点（同样的流程））

    • 如图找到：image-20241108193645936

    • 用temp临时存储最小节点minNode的值，删除minNode，这一步删除有点特殊：targetNode.left = minNode.right。这是一句通用的写法，可以适应不同情况：因为既然是在targetNode的右子树里找的minNode，所以其左边必定无节点，且无论其右节点是否为空，都可以这样子写。

    • 如图删除：image-20241108194225832

    • 删除targetNode，即targetNode.value = temp

    • 如图：image-20241108194625603

  4. 特别注意！上述找到的parentNode可能为null，说明要删除的节点是root节点。

思考：上述思路可能有可以改进的地方——也就是"找到要删除的节点的父节点"，为了这个父节点，代码实现中还特地写了一个独立的方法去查找。好处是清晰，坏处是可能效率略降低？（原路多找一次）。

可能的改进思路：可以把search待删除节点的方法作一定修改：可以返回一个集合，里面装两个节点（被删除节点和父节点）；可以直接返回父节点，后续删除时只是需要多判断一下其左右节点哪个是要被删除的，如何保证被删除的节点的稳定——通过if(this.left.value == val)来判断？那么左右节点值都一样呢？（以及万一是根节点要被删除，那么如何返回这个父节点的问题）

代码暂时不作优化。

代码实现

BinarySearchTreeDemo

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
package com.yukinoshita.dataStructure.binarySearchTree;


public class BinarySearchTreeDemo {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] arr = {7, 15, 2, 1, 10, 5, 20, 9, 12, 3, 17, 18};
        for (int i = 0; i < arr.length; i++) {
            bst.add(new Node(arr[i]));
        }
        //测试delNode方法
        System.out.println("删除前：");
        bst.inOrder();
        bst.delNode(7);
        System.out.println("删除后：");
        bst.inOrder();
    }
}

class BinarySearchTree {
    private Node root;

    //删除结点
    public void delNode(int value){
        if(root == null) return;
        Node targetNode = search(value);
        if(targetNode == null) return;//找不到待删除节点
        Node parentNode = searchParent(value);
        if(parentNode == null){
            //说明要删除的节点就是root节点（也要分三种……）
            //如果左右为空，直接删
            if(root.left == null && root.right == null){
                root = null;
            }
            //如果左右都有子树，选取右子树中最小的
            else if(root.left!=null && root.right != null){
                //temp 为 找到的root的右子树的最小节点
                //还要记录其的parent，已正确执行删除这个最小节点的操作
                Node temp = root.right;
                Node parentOfTemp = root;
                while(temp.left!=null){
                    parentOfTemp = temp;
                    temp = temp.left;
                }
                parentOfTemp.left = temp.right;
                root.value = temp.value;
            }
            //如果只有左或右，直接更新root
            else{
                if(root.left != null) root = root.left;
                else root = root.right;
            }
            return;
        }

        //待删除的节点不是root（保证了操作parentNode时不出错）
        //1.待删除节点为叶子节点
        if(targetNode.left == null && targetNode.right == null) {
            if(parentNode.left!=null && parentNode.left.value == value) parentNode.left =null;
            else parentNode.right = null;
        }
        //2.待删除节点有左子树和右子树
        else if(targetNode.left != null && targetNode.right != null) {
            //temp 为 找到的targetNode的右子树的最小节点
            //还要记录其的parent，已正确执行删除这个最小节点的操作
            Node temp = targetNode.right;
            Node parentOfTemp = targetNode;
            while(temp.left!=null){
                parentOfTemp = temp;
                temp = temp.left;
            }
            parentOfTemp.left = temp.right;
            targetNode.value = temp.value;
        }
        //3.待删除节点只有左子树或右子树
        else{
            //目标节点在parentNode的左边
            if(parentNode.left != null && parentNode.left.value == value){
                //目标节点有左子树
                if(targetNode.left!=null){
                    parentNode.left = targetNode.left;
                }else{
                    parentNode.left = targetNode.right;
                }
            }else{//目标节点在parentNode的右边
                if(targetNode.left!=null){
                    parentNode.right = targetNode.left;
                }else{
                    parentNode.right = targetNode.right;
                }
            }
        }
    }

    //查找要删除的节点
    public Node search(int value){
        if(root == null) return null;//我总是忘记--这种判断自身是否为空的操作……但其实很必要加，不然就会报空指针异常
        return root.search(value);
    }

    //查找要删除节点的父节点
    public Node searchParent(int value){
        if(root == null) return null;
        return root.searchParent(value);
    }

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.addNode(node);
        }
    }

    public void inOrder() {
        root.inOrder();
    }
}

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    //查找待删除节点的父节点
    public Node searchParent(int value){
        if((this.left!=null && this.left.value == value) || (this.right != null && this.right.value == value)){
            return this;
        }else{
            //不好的写法，是暴力查找！
//            if(this.left != null) return this.left.searchParent(value);
//            if(this.right != null) return this.right.searchParent(value);

            //效率高的写法：
            //如果要查找的值小于当前的值，且当前节点的左子节点不为空
            if(value < this.value && this.left!=null) return this.left.searchParent(value);
            else if(value >= this.value && this.right!=null) return this.right.searchParent(value);
            return null;
        }
    }

    //查找为value的节点
    public Node search(int value) {
        if (this.value == value) {
            return this;
        } else if (value < this.value) {
            if (this.left == null) return null;//说明找不到
            return this.left.search(value);//递归地继续找
        } else {
            if (this.right == null) return null;
            return this.right.search(value);
        }
    }

    //递归地添加节点的方法
    public void addNode(Node node) {
        if (node == null) return;

        if (this.value < node.value) {
            if (this.right != null) this.right.addNode(node);
            else this.right = node;
        } else {
            if (this.left != null) this.left.addNode(node);
            else this.left = node;
        }
    }

    //中序遍历
    public void inOrder() {
        if (this.left != null) this.left.inOrder();
        System.out.println(this);
        if (this.right != null) this.right.inOrder();
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

后记：代码中有一部分可以拿出来作为一个方法int delRightTreeMin(Node node){}

说明：node为传入的结点，方法作用是删除以node为根节点这棵二叉排序树的最小根节点，最后返回最小节点minNode的值。

ps：该方法可用于替换代码中的两部分——一是待删除结点有左右子树且待删除结点就是root，二是待删除结点有左右子树且待删除结点不是root。

平衡二叉树

问题：

如下图可见二叉搜索树可能存在的问题:

image-20241109195852364

有以下问题：1.左子树都为空，更像单链表；2.插入速度没有影响，但查询速度大幅减低(每次向下一层前还需要和左比较，比链表还慢)，不能发挥BST（BinarySearchTree）的查询优势。

解决方案：平衡二叉树（AVL）

基本介绍

  1. 平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称AVL树，可以保证查询效率较高。
  2. 特点：
    • 是一颗空树或它的左右子树的高度差的绝对值不超过1。
    • 左右子树都是一棵平衡二叉树。
  3. 常用实现算法有：红黑树、AVL、替罪羊树、Treap、伸展树等

为了使得一棵普通的二叉搜索树变成平衡二叉树，也就是让左右子树的高度差降低，我们引出一些方法——e.g.左旋转、右旋转、双旋转

左旋转

适用于右子树高度大于左子树的情况

左旋转步骤：

  1. 保存当前节点的值，已该值创建newNode
  2. 将newNode的left设置为当前节点的左子树
  3. 将newNode的right设置为当前节点的右子树的左子树
  4. 将当前节点的值更新为右子树的值
  5. 将当前节点的right设置为右子树的右子树
  6. 将当前节点的left设置为newNode

左旋转图解：

image-20241110094040328 image-20241110094207819 image-20241110094235038

至此，这棵树就符合平衡二叉树的定义。

可以看出：左旋转用于当一棵树的左子树的高度小于右子树的高度时。（记忆，想象一个旋钮，把它往左边旋转，那么右边就"旋上去"，右边高度就降低了）

代码实现

  1. 新增三个方法height、leftHeight、rightHeight
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//返回右子树的高度
public int rightHeight() {
    if (right == null) {
        return 0;
    }
    return right.height();
}

//返回左子树的高度
public int leftHeight() {
    if (left == null) {
        return 0;
    }
    return left.height();
}

//返回以当前结点为根节点的树的高度
public int height() {
    return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
  1. 左旋转方法leftRotate
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//左旋转方法
private void leftRotate(){
    //1. 创建新节点，记录当前节点的值
    Node newNode = new Node(this.value);
    //2. 将newNode的left设置为当前节点的左子树
    newNode.left = this.left;
    //3. 将newNode的right设置为当前节点的右子树的左子树
    newNode.right = this.right.left;//****这里不用判断有没有右子树，因为如果this.right为空的话，也不可能会导致右子树比左子树高，更不会执行左旋转*****
    //4. 将当前节点的值更新为右子树的值
    this.value = this.right.value;
    //5. 将当前节点的right设置为右子树的右子树
    this.right = this.right.right;
    //6. 将当前节点的left设置为newNode
    this.left = newNode;
}

右旋转

适用于左子树高度大于右子树的情况

右旋转步骤：

  1. 保存当前结点的值，以该值创建newNode
  2. 将newNode的right设置为当前节点的右子树
  3. 将newNode的left设置为当前结点的左子树的右子树
  4. 将当前结点的值更新为左子树的值
  5. 将当前结点的left设置为左子树的左子树
  6. 将当前结点的right设置为newNode

右旋转图解：

image-20241110133603478 image-20241110133631995 image-20241110133707683

代码实现

rightRotate

1
2
3
4
5
6
7
8
9
//右旋转
private void rightRotate(){
    Node newNode = new Node(value);
    newNode.right = this.right;
    newNode.left = this.left.right;
    this.value = this.left.value;
    this.left = this.left.left;
    this.right = newNode;
}

在添加节点时使用左旋转和右旋转方法：

Node.add方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//递归地添加节点的方法
public void add(Node node) {
    if (node == null) return;

    if (this.value < node.value) {
        if (this.right != null) this.right.add(node);
        else this.right = node;
    } else {
        if (this.left != null) this.left.add(node);
        else this.left = node;
    }

    //当添加完一个节点后：右子树高度 - 左子树高度 > 1，左旋转
    if(rightHeight()-leftHeight() > 1){
        leftRotate();
    }
    //当添加完一个节点后：左子树高度 - 右子树高度 > 1，右旋转
    if(leftHeight()-rightHeight() > 1){
        rightRotate();
    }
}

双旋转

有情况下，仅凭一次左旋转或右旋转是无法使的二叉搜索树转换为平衡二叉树的。

e.g.int[] arr={10,11,7,6,8,9};此时发现，经过一次右旋转后，反而使得右子树的高度比左子树的高度大1。

图示：image-20241110141336862

解决方法——双旋转思路+图解：

  1. 当符合右旋转的条件时（this.leftHeight() - this.rightHeight() > 1）
    image-20241110141635728

  2. 且如果它的 左子树的右子树的高度 大于 左子树的左子树的高度，即this.left.rightHeight() > this.left.leftHeight()
    image-20241110142528639

  3. 先需对当前节点的左子树进行左旋转，即this.left.leftRotate()
    image-20241110142933085

  4. 再对当前节点进行右旋转，即this.rightRotate()
    image-20241110143304696

如果是“当符合左旋转”的条件时，且“它的 右子树的左子树的高度 大于 右子树的右子树的高度”

代码实现

Node.add方法的修改，使其能够进行双旋转（可以对比右旋转代码实现里面的add方法，有什么区别）

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
public void add(Node node) {
    if (node == null) return;

    if (this.value < node.value) {
        if (this.right != null) this.right.add(node);
        else this.right = node;
    } else {
        if (this.left != null) this.left.add(node);
        else this.left = node;
    }

    //当添加完一个节点后：右子树高度 - 左子树高度 > 1，左旋转
    if (rightHeight() - leftHeight() > 1) {
        //如果它的右子树的左子树的高度 大于 它的右子树的右子树的高度
        if(this.right!=null && this.right.leftHeight() > this.right.rightHeight()) {
            //先需要对当前节点的右结点 进行右旋转
            this.right.leftRotate();
        }
        leftRotate();
    }
    //当添加完一个节点后：左子树高度 - 右子树高度 > 1，右旋转
    else if (leftHeight() - rightHeight() > 1) {
        //如果它的左子树的右子树的高度 大于 它的左子树的左子树的高度
        if(this.left!=null && this.left.rightHeight() > this.left.leftHeight()){
            //先需要对当前节点的左结点 进行左旋转
            this.left.leftRotate();
        }
        rightRotate();
    }
}

多叉树

二叉树存在问题

image-20241110144142213
  1. 二叉树加载到内存时，如果节点数量过多，会存在问题：
  2. 构建二叉树时，需进行多次i/o操作（海量数据一般在文件或数据库中），对构建效率有影响。
  3. 海量数据也会造成树的高度过大（谁告诉你一定是满二叉树?）

多叉树基本介绍

  1. 在二叉树中，每个结点有数据项，最多有两个子节点。如果允许每个结点可以有更多的数据项和子结点，就是多叉树（Multiway Tree）
  2. 2-3树、2-3-4树就是多叉树，多叉树通过重新组织结点，减少树的高度，能对二叉树进行优化
  3. 举例图：
image-20241110144751794

B树基本介绍

image-20241110115227975
  1. B树通过重新组织结点，降低树的高度，减少了i/o读写次数来提升效率
  2. 文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页(页得大小通常为4k)，这样每个节点只需要一次I/O就可以完全载入
  3. 将树的度M设置为1024，在600亿个元素中最多只需要4次I/O操作就可以读取到想要的元素，B树(B+)广泛应用于文件存储系统以及数据库系统中

2-3树基本介绍

2-3树是最简单的B树结构，具有如下特点:

  1. 2-3树的所有叶子节点都在同一层（B树都满足）
  2. 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点
  3. 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点
  4. 2-3树是由二节点和三节点构成的树。

2-3树

关于三节点的说明：

image-202411101449088307号节点在8号左边，10号介于8和12中间，14在12右边。

构建2-3树：

插入规则：

  1. 2-3树的所有叶子节点都在同一层。（B树都满足这个条件）
  2. 二节点要么没有子节点，要么有两个子节点。
  3. 三节点要么没有子节点，要么有三个子节点。
  4. 当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面3个条件。
  5. 对于三节点的子树的值大小仍然遵守（BST 二叉搜索树）的规则

图解：

以数列${ 16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20 } $为例

  1. 插入16，24，12，32。十分自然：
image-20241110164703683
  1. 插入14（简单）
image-20241110164746993
  1. 插入26（需拆上一层）
image-20241110164905390
  1. 插入34（简单）
image-20241110165036078
  1. 插入10（复杂）
image-20241110165746037
  1. 插入8（自然）
image-20241110170229138
  1. 插入28（中间过程演示）
image-20241110170605919
  1. 插入38（简单）
image-20241110170903042
  1. 插入20（简单）
image-20241110170950636

2-3-4树

2-3-4树概念和2-3树类似，多了一个四节点，也是一种B树

image-20241110121240298

B树

B-tree树即B树，B即Balanced，平衡的意思。有人把B-tree翻译成B-树，容易让人产生误解。会以为B-树是一种树，而B树又是另一种树。实际上，B-tree就是指的B树。（还有写成B-树的，实际上没有"B减树"，就是B树）

  1. B树的阶：节点的最多子节点个数。比如2-3树的阶是3，2-3-4树的阶是4
  2. B树的搜索：从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点
  3. 关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据
  4. 搜索有可能在非叶子结点结束（已找到）
  5. 其搜索性能等价于在关键字全集内做一次二分查找
image-20241110171831364

B+树

B+树是B树的变体，也是一种多路搜索树。

  1. B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找
  2. 所有关键字都出现在叶子结点的链表中（即数据只能在叶子节点【也叫稠密索引】），且链表中的关键字(数据)恰好是有序的。
  3. 不可能在非叶子结点命中
  4. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
  5. 更适合文件索引系统
  6. B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然。
image-20241110172528554

B*树

B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针。

  1. B* 树定义了非叶子结点关键字个数至少为$\frac{2}{3}M$，即块的最低使用率为$\frac{2}{3}$，而B+树的块的最低使用率为B+树的$\frac{1}{2}$。
  2. 从第1个特点我们可以看出，B*树分配新结点的概率比B+树要低，空间使用率更高