huffman_tree/
lib.rs

1//! #哈夫曼树相关功能
2//!
3//!
4
5struct HuffmanNode {
6	ch:char,
7	weight: usize,
8	parent: usize,
9	lchild: usize,
10	rchild: usize,
11}
12
13impl HuffmanNode {
14	fn new(ch:char,weight:usize,parent:usize,lchild:usize,rchild:usize) ->HuffmanNode{
15		HuffmanNode{
16			ch,
17			weight,
18			parent,
19			lchild,
20			rchild,
21		}
22	}
23}
24
25pub struct HuffmanTree {
26	data:Vec<HuffmanNode>,
27	leaf_num:usize,
28}
29
30impl HuffmanTree{
31	
32	fn set_parent(&mut self,index:usize,parent:usize){
33		self.data[index].parent = parent;
34	}
35
36	fn push(&mut self,node:HuffmanNode){
37		self.data.push(node);
38	}
39	
40	fn len(&self) -> usize{
41		self.data.len()
42	}
43	
44	fn get_parent(&self,index:usize)->usize{
45		self.data[index].parent
46	}
47	
48	fn get_ch(&self,index:usize)->char{
49		self.data[index].ch
50	}	
51	
52	fn get_weight(&self,index:usize)->usize{
53		self.data[index].weight
54	}
55	
56	fn get_ch_index(&self,ch:char)->usize{
57		let mut i = 0;
58		for item in self.data.iter(){
59			if item.ch == ch{
60				return i;
61			}
62			i += 1;
63		}
64		0
65	}
66	
67	fn get_lchild(&self,index:usize)->usize{
68		self.data[index].lchild
69	}
70	
71	fn get_rchild(&self,index:usize)->usize{
72		self.data[index].rchild
73	}	
74	
75	/// 建立哈夫曼树，
76	/// c是字符的列表，w是相应的权重
77	pub fn create(c:&Vec<char>,w:&Vec<usize>) -> HuffmanTree{
78		let mut n = c.len();
79		if w.len() < n{
80			n = w.len();
81		}
82		let mut tree = HuffmanTree{
83			data:Vec::new(),
84			leaf_num:n,
85		};		
86		if n <=1 {
87			return tree;
88		}
89		
90		//留着这个索引0，给parent,lchild,rchild用，以表示没有
91		tree.push(HuffmanNode::new('🐅',0,0,0,0));
92		for i in 0..n{
93			let node = HuffmanNode::new(c[i],w[i],0,0,0);
94			tree.push(node);
95		}
96		
97		loop{
98			let mut s1=0;
99			let mut weight = usize::MAX;
100			for i in 1..(tree.len()){
101				if tree.get_parent(i) == 0 && tree.get_weight(i) < weight {
102					weight = tree.get_weight(i);
103					s1 = i;
104				}
105			}
106			weight = usize::MAX;
107			let mut s2 = 0;
108			for i in 1..(tree.len()){
109				if tree.get_parent(i) == 0 && i != s1 && tree.get_weight(i) < weight {
110					weight = tree.get_weight(i);
111					s2 = i;
112				}
113			}	
114			if s2 == 0{
115					break;
116			}
117			
118			let the_i = tree.len();
119			tree.set_parent(s1,the_i);
120			tree.set_parent(s2,the_i);
121			let node = HuffmanNode::new('🐅',tree.get_weight(s1) + tree.get_weight(s2),0,s2,s1);
122			tree.push(node);
123		}
124		
125		tree
126	}
127}
128
129/// # 根据给定的哈夫曼树，从每个叶子节点出发追溯到树根，逆向找出二叉树中叶子节点的编码
130pub fn encoding(tree:&HuffmanTree,buff:&String)->String{
131	let mut code = String::from("");
132	if tree.leaf_num <=1 {
133		return code;
134	}
135	let mut chars = buff.chars();
136	while let Some(cha) = chars.next(){
137		
138		let mut c = tree.get_ch_index(cha);
139		let mut f = tree.get_parent(c);
140		let mut cd = String::from("");
141		loop{
142			if tree.get_lchild(f) == c{
143				cd.insert(0,'0');
144			}else{
145				cd.insert(0,'1');
146			}
147			c = f;
148			f = tree.get_parent(f);
149			if f == 0{
150				break;
151			}
152		}
153		code.push_str(&cd);
154	}
155	code
156}
157
158/// 利用具有n个节点的最优二叉树进行译码，叶子的下标为1-n，
159///buff是二进制位串编码序列
160pub fn decoding(tree:&HuffmanTree,buff:&String)->String{
161	let mut st = String::from("");
162	let mut p = 2 * tree.leaf_num - 1;
163	for i in 0..(buff.len()){
164		let c = &buff[i..(i+1)];
165		if c == "0" {
166			p = tree.get_lchild(p);
167		}else{
168			p = tree.get_rchild(p);
169		}
170		if tree.get_lchild(p) == 0 && tree.get_rchild(p) == 0{
171			st.push(tree.get_ch(p));
172			p = 2 * tree.leaf_num - 1;
173		}
174	}
175	st
176}
177
178#[cfg(test)]
179mod tests {
180    #[test]
181    fn it_works() {
182        assert_eq!(2 + 2, 4);
183    }
184}
huffman_tree/lib.rs

huffman_tree/
lib.rs
