树
线索二叉树
问题引入：在该树中，1，2，3结点的左右指针并没有全部被利用。我们希望充分利用各个结点的左右指针，让各个结点指向自己的前后结点。
解决方法：线索二叉树
介绍线索二叉树
n个结点的二叉链表含有n+1个空指针域。利用二叉链表中的空指针域，存放指向某种遍历次序下的前驱和后继结点的指针。
线索二叉树可分成前序线索二叉树，中序线索二叉树，后序线索二叉树。
如何实现线索二叉树
我们中序遍历树；得到的结果是：3、1、0、4、2、5
3 的 左右结点都为空，那么我们将 3 的左右结点分别指向它的前趋和后继结点。因为3没有前趋结点，则左节点为空。3 的后继结点为1，那么右节点指向1
1 结点的右结点为空，那么右结点指向它的后继结点 0
同理：4 结点 左右指针为空，那么可以指向 0 和 2 ，5结点的左指针为空，那么可以指向2，但没有后继结点，那么右指针为空。
我们可以看到：一个结点的左右指针既可以指向它的子结点，也可以指向某种遍历下的前趋和后继结点，我们如何取区分这两种情况？
我们为每个结点增加了两个线索标志域。比如 ltag和rtag；
if （ ltag == 0） //左指针指向的是左儿子
if （ ltag == 1） //左指针指向的是前趋结点
if （ rtag == 0） //右指针指向的是右儿子
if （ rtag == 1） //右指针指向的是后继结点
赫夫曼树
基本介绍：
路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径，通路中的分支数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1
结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和。记为WPL
最优二叉树：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度（wpl）达到最小。
如何构造一棵赫夫曼树：
这里有五个结点。构造一棵最优二叉树，根据规则，这些结点只能是叶子结点，且WPL必须最小。
示例一：WPL = 3 X (3+2+1+4) + 2 X 5 = 40
示例二：WPL = 5 X 5 + 4 X 4 + 3 X 3 + 2 X 2 + 1 X 1 = 55
我们注意到：要想WPL越小，树的高度尽量小，并且权值大的结点应该越接近根结点
赫夫曼树创建思路：
1、先将结点按权值大小排序，将每个结点都看成一棵二叉树，那么每个结点都看成是根结点。
2、取出权值最小的两个根结点，将他们组成一棵新的二叉树
3、这颗新的二叉树的权值是前面两颗二叉树的权值之和，
4、在将这颗新的二叉树，以根结点的权值再次排序。
5、重复234的步骤，直到最后的二叉树都被处理完。
示例：将以下结点构成一棵赫夫曼树
1、排序
2、取出权值最小的结点构成二叉树，新二叉树的根结点的权值为4
3、根结点再次排序
4、取出权值最小的根结点
5、根结点再次排序
6、取出权值最小的根结点
7、根结点再次排序
8、取出权值最小的根结点
9、根结点再次排序
10、取出权值最小的根结点
11、根结点再次排序
12、取出权值最小的根结点
这就是一棵最优二叉树
代码实现
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
|
class Node implements Comparable<Node>{
private int no;
private String name;
private Node left;
private Node right;
public Node() {
}
public Node(int no) {
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public void perOrder(){
System.out.println(this.no );
if(this.left != null){
this.left.perOrder();
}
if (this.right != null){
this.right.perOrder();
}
}
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 int compareTo(Node o) {
return this.no - o.no;
}
}
public class HuffmanTreeDemo {
public static Node creatHuffmanTree(int arr[]) {
List<Node> nodes = new ArrayList<Node>();
for (int i = 0; i < arr.length; i++) {
nodes.add(new Node(arr[i]));
}
while (nodes.size() > 1) {
Collections.sort(nodes);
Node leftnode = nodes.get(0);
Node rightnode = nodes.get(1);
Node parent = new Node(leftnode.getNo()+rightnode.getNo());
parent.setLeft(leftnode);
parent.setRight(rightnode);
nodes.remove(leftnode);
nodes.remove(rightnode);
nodes.add(parent);
}
return nodes.get(0);
}
public static void main(String[] args) {
int[] arr = new int[]{13,7,8,3,29,6,1};
Node node = creatHuffmanTree(arr);
node.perOrder();
}
}
|
遍历结果：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 67
29
38
15
7
8
23
10
4
1
3
6
13
|