為使得哈夫曼樹唯一,我們通正常定左子樹的權值小于右子樹
import java.util.*;
public class Build_huffman_tree {
public static void main(String args[]){
Scanner in=new Scanner(System.in);
while(in.hasNext()){
int n=in.nextInt();
Queue<Integer> queue=new PriorityQueue<Integer>(); //優先隊列建構哈夫曼樹
for(int i=0;i<n;i++)
queue.offer(in.nextInt());
Tree root[]=new Tree[2*n-1];
int temp1=0,temp2=0,sum=0;
int cnt=2*n-2;
//每次從隊列裡取出最小的兩個,構成一個新的節點
while(queue.size()>1){
temp1=queue.poll();
temp2=queue.poll();
sum+=temp1+temp2;
root[cnt-1]=new Tree(temp1);
root[cnt]=new Tree(temp2);
cnt-=2;
queue.offer(temp1+temp2);
}
root[0]=new Tree(queue.poll());
System.out.println("最短路徑和為:"+sum);
//建構哈夫曼樹
for(int i=0;i<2*n-2;i+=2){
root[i].left=root[i+1];
root[i].right=root[i+2];
}
System.out.println("先序周遊");
f_pre(root[0]);
System.out.println("中序周遊");
f_in(root[0]);
System.out.println("後序周遊");
f_post(root[0]);
System.out.println("層次周遊");
f_ceng(root[0]);
}
}
//先序周遊
public static void f_pre(Tree root){
if(root!=null){
System.out.println(root.value);
f_pre(root.left);
f_pre(root.right);
}
}
//中序周遊
public static void f_in(Tree root){
if(root!=null){
f_pre(root.left);
System.out.println(root.value);
f_pre(root.right);
}
}
//後序周遊
public static void f_post(Tree root){
f_pre(root.left);
f_pre(root.right);
System.out.println(root.value);
}
//層次周遊
public static void f_ceng(Tree root){
if(root!=null){
Queue<Tree> ans=new LinkedList<Tree>();
ans.offer(root);
while(ans.size()>0){
Tree temp1=ans.poll();
System.out.println(temp1.value);
if(temp1.left!=null){
ans.offer(temp1.left);
}
if(temp1.right!=null){
ans.offer(temp1.right);
}
}
}
}
}
//定義資料結構
class Tree{
Tree left;
Tree right;
int value;
Tree(int value){
this.value=value;
this.left=null;
this.right=null;
}
}