根据给定的字符及其权值建立一棵哈夫曼树，并输出已建好的哈夫曼树的各结点的编码。
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
public classHuffmanTree {
/*
* 哈夫曼树的结点
*/
public static class Node {
private char data;
private int weight;
private int parent;
public Node left = null;
public Node right = null;
public Node(int data, int weight, int parent) {
this.data = (char) (data + ‘A’);
this.weight = weight;
this.parent=parent;
}
}
/*
* 非递归创建哈夫曼树，返回权值最大的节点
*/
public Nodecreate(Stack<Integer> stack, int[][] a) {// 创建哈夫曼树
Queue<Node>queue = newLinkedList<Node>();
int weight, data, parent;
Nodetemp = null;
while (!stack.isEmpty()) {
Noderoot = null;
data= -1;// 设置默认符号为@
parent= 0;
/*
* 创建或选择根节点
*/
if (!queue.isEmpty()) {
// 取队头元素为根节点
root= queue.poll();
}else{// 创建根节点，仅执行一次
weight= stack.pop();
for (int i = 0; i < a.length; i++) {
if (a[i][1] == weight) {
data= a[i][0];
}
}
root= newNode(data, weight, parent);
temp= root;
}
/*
* 创建左子树
*/
if (!stack.isEmpty()) {
parent=root.weight;
weight= stack.pop();
for (int i = 0; i < a.length; i++) {
if (a[i][1] == weight) {
data= a[i][0];
}
}
root.left = new Node(data, weight,parent);
queue.add(root.left);
}
/*
* 创建右子树
*/
if (!stack.isEmpty()) {
parent=root.weight;
weight= stack.pop();
for (int i = 0; i < a.length; i++) {
if (a[i][1] == weight) {
data= a[i][0];
}
}
root.right = new Node(data, weight,parent);
queue.add(root.right);
}
}
return temp;
}
/*
* 递归打印哈夫曼树
*/
public static void printTree(Node root) {
if (root.left != null && root.right != null) {// 哈夫曼树没有度为1的点
System.out.println(root.data + “\t” + root.weight + “\t”
+root.parent+ “\t”+ root.left.data + “\t”
+root.right.data);
} else {
// -1代表无子节点
System.out.println(root.data + “\t” + root.weight + “\t”
+root.parent+ “\t”+ “-1”+ “\t”+ “-1”);
}
if (root.left != null) {
printTree(root.left);
}
if (root.right != null) {
printTree(root.right);
}
}
/*
* 处理输入的数组，返回存储权值的栈
*/
public Stack<Integer>dealArray(int[][]a) {
Stack<Integer>stack = newStack<Integer>();
ArrayList<Integer>array = newArrayList<Integer>();
for (int i = 0; i < a.length; i++) {
array.add(a[i][1]);
}
Collections.sort(array);// 排序
int min1;
for (int i = 0; i <array.size() – 1;) {
stack.add(array.get(i));
stack.add(array.get(i+ 1));
int sum = array.get(i) +array.get(i + 1);
array.add(sum);
array.remove(array.get(i));
array.remove(array.get(i));// 一定要为array.get(i)，不能为array.get(i+1)！
Collections.sort(array);
i= 0;
}
stack.add(array.get(0));
return stack;
}
public static void main(String[] args) {
Scannerin = newScanner(System.in);
System.out.println(“请输入需哈夫曼编码的字符及其权值:\n”
+“输入规则如(A1 B2 C3)”);
Strings = in.nextLine();
s= s.replace(” “,“”);
int[][] a = new int[s.length() / 2][2];
int j = 0;
for (int i = 0; i <s.length(); i++) {// 用二维数组存储字符与权值
if (i % 2 == 0) {
a[j][0]= s.charAt(i) – ‘A’;
}else{
a[j][1]= s.charAt(i) – ‘0’;
j++;
}
}
// C3 B4 A5
HuffmanTreetree = newHuffmanTree();
Stack<Integer>stack = tree.dealArray(a);
Noderoot = tree.create(stack, a);
System.out.println(“所带字符\t权值\t双亲节点\t左孩子\t右孩子“);
printTree(root);
System.out.println(“备注：\n字符默认为@\n0代表无双亲节点\n-1代表无孩子“);
}
}