package shugou;
import java.io.*;
import java.util.*;
/**
* Created by 田曌华 on 2016/6/5.
*/
public class HuffmanTree {
public static BinaryTreeNode buildHuffmanTree(Map map) {
List<BinaryTreeNode> list = new ArrayList<BinaryTreeNode>();
Set set = map.entrySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> entry = (Map.Entry<String, Integer>) iterator.next();
BinaryTreeNode newNode = new BinaryTreeNode(entry.getKey(), entry.getValue());
list.add(newNode);
}
while (list.size()>1) {
int min1 = findMin(list);
BinaryTreeNode leftChild = list.remove(min1);
int min2 = findMin(list);
BinaryTreeNode rightChild = list.remove(min2);
BinaryTreeNode newNode = new BinaryTreeNode(leftChild, rightChild);
list.add(newNode);
}
return list.get(0);
}
public static Map<String,String> getHuffmanCoding( BinaryTreeNode root ){
Map<String,String> map = new HashMap<String,String>();
trans(root, map,"");
return map;
}
private static void trans(BinaryTreeNode root,Map map,String string){
if(root.getLeftChild() == null){
map.put(root.getName(),string);
return ;
}
trans(root.getLeftChild(),map,string+"0");
trans(root.getRightChild(),map,string+"1");
}
public static void transTo(String string,Map map){
File file = new File("d:/temp", "CodeFile.txt");
String str = "";
StringBuffer stringBuffer = new StringBuffer();
// System.out.print("////////////"+string+"////////////");
for (int i = 0;i<string.length();i++){
// System.out.print(String.valueOf(string.charAt(i)));
stringBuffer.append(map.get(String.valueOf(string.charAt(i))));
}
str = String.valueOf(stringBuffer);
try {
file.createNewFile();
}catch (IOException e){
e.printStackTrace();
}
byte bt[] = new byte[1024];
bt = str.getBytes();
try {
FileOutputStream in = new FileOutputStream(file);
try {
in.write(bt, 0, bt.length);
in.close();
} catch (IOException e) {
e.printStackTrace();
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public static void writeToToBeTran(String str){
File file = new File("d:/temp", "ToBeTran.txt");
try {
file.createNewFile();
} catch (IOException e) {
e.printStackTrace();
}
byte bt[] = new byte[1024];
bt = str.getBytes();
try {
FileOutputStream in = new FileOutputStream(file);
try {
in.write(bt, 0, bt.length);
in.close();
} catch (IOException e) {
e.printStackTrace();
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public static void printCodeFile(){
File file = new File("d:/temp", "CodeFile.txt");
String s = "";
try {
FileInputStream out = new FileInputStream(file);
InputStreamReader isr = new InputStreamReader(out);
int ch = 0;
int count = 0;
while ((ch = isr.read()) != -1) {
if (count%50 == 0){
System.out.println();
s = s + "\r\n";
}
System.out.print((char) ch);
count++;
s += String.valueOf((char)ch);
}
} catch (Exception e) {
}
System.out.println(s);
File file1 = new File("d:/temp", "CodePrint.txt");
try {
file1.createNewFile();
} catch (IOException e) {
e.printStackTrace();
}
byte bt[] = new byte[1024];
bt = s.substring(2).getBytes();
try {
FileOutputStream in = new FileOutputStream(file1);
try {
in.write(bt, 0, bt.length);
in.close();
} catch (IOException e) {
e.printStackTrace();
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public void DisplayBinTree(BinaryTreeNode T) {
BinaryTreeNode p;
BinaryTreeNode[] stack = new BinaryTreeNode[100];
int top, n, i;
int[] level = new int[100];
if (T != null) {
top = 1;
stack[top] = T;
level[top] = 3;
while (top > 0) {
p = stack[top];
n = level[top];
for (i = 1; i <= n; i++)
System.out.print(" ");
System.out.println(p.getName());
top--;
if (p.getRightChild() != null) {
top++;
stack[top] = p.getRightChild();
level[top] = n + 3;
}
if (p.getLeftChild() != null) {
top++;
stack[top] = p.getLeftChild();
level[top] = n + 3;
}
}
}
}
private static void writeTohfmTree(Map map){
File file = new File("d:/temp", "hfmTree.txt");
String str = "";
try {
file.createNewFile();
}catch (IOException e){
e.printStackTrace();
}
Set set = map.entrySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> entry = (Map.Entry<String, Integer>) iterator.next();
str += entry.getKey()+","+entry.getValue()+"\r\n";
}
byte bt[] = new byte[1024];
bt = str.getBytes();
try {
FileOutputStream in = new FileOutputStream(file);
try {
in.write(bt, 0, bt.length);
in.close();
} catch (IOException e) {
e.printStackTrace();
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public static int findMin(List<BinaryTreeNode> list){
int index = 0;
int min = list.get(0).getValue();
for( int i = 1 ; i < list.size(); i++ ){
if( list.get(i).getValue() < min ){
min = list.get(i).getValue();
index = i;
}
}
return index;
}
public static Map read(String string){
Map<String, Integer> map = new HashMap<String, Integer>();
for (int i = 0;i<string.length();i++) {
if (map.containsKey(String.valueOf(string.charAt(i))) == false) {
map.put(String.valueOf(string.charAt(i)), 1);
// System.out.println(String.valueOf(string.charAt(i))+" "+String.valueOf(string.charAt(i)).hashCode());
}else{
int a = map.get(String.valueOf(string.charAt(i)));
a++;
map.put(String.valueOf(string.charAt(i)),a);
}
}
// System.out.println(map.toString());
return map;
}
public static Map transToMap(){
Map map = new HashMap<>();
String line = "";
String[] arrs=null;
try {
File file = new File("d:/temp", "hfmTree.txt");
BufferedReader bf= new BufferedReader(new FileReader(file
shugou.rar_4 3 2 1_哈夫曼java
版权申诉
136 浏览量
2022-09-23
01:26:53
上传
评论
收藏 4KB RAR 举报
weixin_42651887
- 粉丝: 79
- 资源: 1万+