数据结构——二叉树(一)

从工作到辞职到现在插本入读本科,整整两个月的时间,没有对自己遇到和学到的东西进行总结回顾,一方面是在工作的时候懒得写,另一方面还是懒得写,现在闲下来回归大学生活,该干点正事,总结一下学习,为一年后找工作做好万全的准备了。

哈夫曼树

今天呢,上午没课,抽出空来完成了搜索二叉树及哈夫曼树,哈夫曼树仅仅简单的写了个创建。下面先介绍一下这个哈夫曼树的简单实例。

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
package tree;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class HaffmanTree<T> {

public static void main(String[] args) {
LinkedList<HaffmanTreeNode<Integer>> queue = new LinkedList<>();
HaffmanTreeNode<Integer>[] list = new HaffmanTreeNode[10];
for (int i = 0; i < 10; i++) {
HaffmanTreeNode<Integer> node = new HaffmanTreeNode<>(i, (int) (i * Math.random() * 10 + 1));
queue.add(node);
list[i] = node;
}
queue.sort(Comparator.comparingInt(o -> o.weight));
HaffmanTree<Integer> haffmanTree = new HaffmanTree<>(queue);
haffmanTree.preOrder();
}

private HaffmanTreeNode<T> root;

public HaffmanTree(LinkedList<HaffmanTreeNode<T>> queue) {
while(queue.size() > 1) {
HaffmanTreeNode<T> first = queue.pollFirst();
HaffmanTreeNode<T> second = queue.pollFirst();
HaffmanTreeNode<T> node = new HaffmanTreeNode<>(null, first.weight + second.weight);
node.left = first;
node.right = second;
if(queue.size() == 2) {
this.root = node;
}
queue.addFirst(node);
queue.sort(Comparator.comparingInt(o -> o.weight));
}
}


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

public void preOrder(HaffmanTreeNode<T> node) {
if (node != null) {
System.out.println("(" + node.data + ", " + node.weight + ")");
preOrder(node.left);
preOrder(node.right);
}
}

private static class HaffmanTreeNode<T> {
public T data;
public int weight;
public HaffmanTreeNode<T> left;
public HaffmanTreeNode<T> right;

public HaffmanTreeNode(T data, int weight) {
this.data = data;
this.weight = weight;
}
}
}

看完这一段,如果不了解树、二叉树相关概念的话,将会一脸懵逼。所以在这里解释一下关键的概念,其他不懂的该上百度查查了,这里不作过多解释。

二叉树图片
二叉树图片

路径:路径就是说从根节点到某个节点所经过的节点集合。如上图到G节点的路径就是AEFG。

WPL:带权路径长度,计算方法为路径长度权值。假设G的权值为7,则G的WPL=4\7=28。

其实哈夫曼树理解了还是挺容易的,简单说就是拿个队列从小到大排序,然后每次拿前面两个元素进行权值相加,生成一个父节点,并且这个父节点的左右子节点为这两个元素。如图示:

哈夫曼树生成过程图片
哈夫曼树生成过程图片

如此循环,直到队列元素为空。通过这样的方式,生成出来的树为最优二叉树。哈夫曼树的理解就到这了,简单的理解了一下什么是哈夫曼树,并且完成了它的创建,剩下的交给大家,完成了教教我。下面介绍搜索二叉树。

搜索二叉树

搜索二叉树原理很简单,每一个节点的左子树都小于自己,右子树都大于自己。于是它的中序遍历就是一个从小到大排序好的线性表了。搜索二叉树在创建、插入和修改上的难度都不大,在删除操作上略有点小复杂,之前一直没想明白,我现在是第三次探索搜索二叉树,终于把它的删除给理解了。

先展示一下代码:

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
package tree;

public class SearchBinaryTree<T extends Comparable<T>> {

public static void main(String[] args) {
Integer[] arr = new Integer[] {
5, 3, 1, 4, 7, 6, 8, 0, 2, 9
};
SearchBinaryTree<Integer> searchBinaryTree = new SearchBinaryTree<>(arr);
searchBinaryTree.midTraversal();
System.out.println();
searchBinaryTree.delete(5);
searchBinaryTree.midTraversal();
System.out.println();
searchBinaryTree.insert(2);
searchBinaryTree.midTraversal();
}

private BinaryTreeNode<T> root;

public SearchBinaryTree(T[] data) {
for (T datum : data) {
BinaryTreeNode<T> node = createNode(datum);
if (isEmpty()) {
this.root = node;
} else {
insert(datum);
}
}
}

public BinaryTreeNode<T> createNode(T data) {
return new BinaryTreeNode<>(data, null, null, null);
}

public boolean isEmpty() {
return this.root == null;
}

public BinaryTreeNode<T> delete(T data) {
BinaryTreeNode<T> del = search(data);
if (del == null) {
throw new RuntimeException("未找到节点!");
}
BinaryTreeNode<T> parent = del.parent;
BinaryTreeNode<T> replace = null;
if (del.left == null) {
replace = del.right;
} else if (del.right == null) {
replace = del.left;
} else {
// 左右节点都不为空的情况
BinaryTreeNode<T> cur = del.right;
while (cur.left != null) {
cur = cur.left;
}
replace = delete(cur.data);
replace.left = del.left;
}
if (parent != null) {
if (parent.right == del) {
parent.right = replace;
} else {
parent.left = replace;
}
del.right = null;
del.left = null;
} else {
replace.left = this.root.left;
replace.right = this.root.right;
this.root.left = null;
this.root.right = null;
this.root = replace;
}

return del;
}

public boolean insert(T data) {
BinaryTreeNode<T> node = createNode(data);
BinaryTreeNode<T> current = this.root;
BinaryTreeNode<T> prev = current;
while (current != null) {
prev = current;
if (current.data.compareTo(data) < 0) {
current = current.right;
} else if (current.data.compareTo(data) > 0) {
current = current.left;
} else {
prev = null;
break;
}
}
if (prev != null) {
node.parent = prev;
if (prev.data.compareTo(data) < 0) {
prev.right = node;
} else {
prev.left = node;
}
return true;
}
return false;
}

public BinaryTreeNode<T> search(T data) {
BinaryTreeNode<T> current = this.root;
while (current != null) {
System.out.print("current: " + current.data + "\t");
if (current.data.compareTo(data) > 0) {
System.out.print("go left \n");
current = current.left;
} else if (current.data.compareTo(data) < 0) {
System.out.print("go right \n");
current = current.right;
} else {
System.out.println("got you \n");
return current;
}
}
return null;
}

public void preTraversal() {
preTraversal(this.root);
}

public void midTraversal() {
midTraversal(this.root);
}

public void postTraversal() {
postTraversal(this.root);
}

private void preTraversal(BinaryTreeNode<T> node) {
if (node != null) {
System.out.print(node.data + "\t");
preTraversal(node.left);
preTraversal(node.right);
}
}

private void midTraversal(BinaryTreeNode<T> node) {
if (node != null) {
midTraversal(node.left);
System.out.print(node.data + "\t");
midTraversal(node.right);
}
}

private void postTraversal(BinaryTreeNode<T> node) {
if (node != null) {
postTraversal(node.left);
postTraversal(node.right);
System.out.print(node.data + "\t");
}
}

public static class BinaryTreeNode<T extends Comparable<T>> {
T data;
BinaryTreeNode<T> parent;
BinaryTreeNode<T> left;
BinaryTreeNode<T> right;

public BinaryTreeNode(T data,
BinaryTreeNode<T> parent,
BinaryTreeNode<T> left,
BinaryTreeNode<T> right) {
this.data = data;
this.parent = parent;
this.left = left;
this.right = right;
}
}

}

首先是搜索二叉树的创建和插入,首先创建一个节点出来,如果根节点为空,则将让根节点指向这个节点,然后剩余的则通过插入的方式接入到树中。插入时,需要对节点进行比较,如果插入的值大于该节点,则向右走,如果小于,则向左走,相等直接返回,循环直到节点为空,将记录下的父节点与该节点连接。搜索方法与插入方法相似,循环比较搜索的值与节点值,小于则向左走,大于向右走,直到找到或者结束,最后将搜索结果返回。修改则在搜索的基础上进行修改,修改方法在文中没有进行实现,有兴趣的朋友可以尝试一下。

接下来所要说的就是删除操作了,删除操作有4种情况,分别为左右子节点存在,左右子节点不存在,左节点或右节点不存在。先从最简单的说起,那就是节点有不存在的情况。仅当左节点不存在时,将右节点顶替上去;仅当右节点不存在时,将左节点顶替上去;当左右节点都不存在时,直接删除该节点即可。复杂的地方就在于左右节点都存在时,我们需要找到左子树最大节点或者右子树最小节点,让这个节点顶替上去,即将这个节点位置移动到被删除节点上,这种操作本质上也是一个删除操作,即删除后再增加。不清楚?如图:

删除节点示意图
删除节点示意图

如果被顶替的点也属于左右节点都存在的情况,对该节点执行相同的操作就完事了。

本次的二叉树学习也就到这里结束了,数据结构这东西需要花时间去理解,后面还有图和算法,生活不易,一起努力!文中有些表述不到位的或者是错误的地方可以通过qq、邮箱与我进行联系,希望大家能够共同学习,共同进步!