本文實(shí)例為大家分享了哈夫曼樹java代碼，供大家參考，具體內(nèi)容如下
|
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
|
package boom; import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.Queue; class Node<T> implements Comparable<Node<T>>{ private T data; private int weight; private Node<T> left; private Node<T> right; public Node (T data,int weight){ this.data = data; this.weight = weight; } public int compareTo(Node<T> other) { if(this.weight > other.getWeight()){ return -1; }if(this.weight < other.getWeight()){ return 1; } return 0; } public T getData() { return data; } public void setData(T data) { this.data = data; } public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; } public Node<T> getLeft() { return left; } public void setLeft(Node<T> left) { this.left = left; } public Node<T> getRight() { return right; } public void setRight(Node<T> right) { this.right = right; } public String toString(){ return "data:"+this.data+";weight:"+this.weight; } } public class huffuman<T> { static <T> Node<T> create(List<Node<T>> nodes){ while(nodes.size()>1){ Collections.sort(nodes); Node<T> left = nodes.get(nodes.size()-1); Node<T> right = nodes.get(nodes.size()-2); Node<T> parent = new Node<T>(null,left.getWeight()+right.getWeight()); parent.setRight(right); parent.setLeft(left); nodes.remove(left); nodes.remove(right); nodes.add(parent); } return nodes.get(0); } static<T> List<Node<T>> breadth(Node<T> root){ List<Node<T>> list = new ArrayList<Node<T>>(); Queue<Node<T>> queue = new ArrayDeque<Node<T>>(); queue.offer(root); while(queue.size()>0){ Node<T> out = queue.poll(); list.add(out); if(out.getLeft()!=null){ queue.offer(out.getLeft()); } if(out.getRight()!=null){ queue.offer(out.getRight()); } } return list; } public static void main(String[] args) { // TODO Auto-generated method stub List<Node<String>> list = new ArrayList<Node<String>>(); list.add(new Node<String>("a",7)); list.add(new Node<String>("b",5)); list.add(new Node<String>("c",4)); list.add(new Node<String>("d",2)); Node<String> root =huffuman.create(list); System.out.println(huffuman.breadth(root)); // System.out.println(list); } } |
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
