 chatGPT答： |
8v6.cn |
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int n;
static char[] chs;
static int[] w, p, l, r;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
chs = new char[n];
w = new int[n];
p = new int[2 * n - 1];
l = new int[2 * n - 1];
r = new int[2 * n - 1];
for (int i = 0; i < n; i++) {
chs[i] = sc.next().charAt(0);
w[i] = sc.nextInt();
p[i] = -1;
l[i] = -1;
r[i] = -1;
}
for (int i=n;i<2*n-1;i++) {
// 找到权值最小的两个结点
int minIndexOne=-1,minIndexTwo=-1,minValueOne=Integer.MAX_VALUE,minValueTwo=Integer.MAX_VALUE;
for(int j=0;j<i;j++){
if(p[j]==-1){
if(w[j]<minValueOne){
minIndexTwo=minIndexOne; minValueTwo=minValueOne;
minIndexOne=j; minValueOne=w[j];
}else if(w[j]<minValueTwo){
minIndexTwo=j; minValueTwo=w[j];
}
}
}
// 合并这两个结点，构造新的父节点
w[i]=minValueOne+minValueTwo;p[minIndexOne]=i;p[minIndexTwo]=i;l[i]=minIndexOne;r[i]=minIndexTwo;
}
// 输出哈夫曼树
for(int i=0;i<n;i++){
System.out.print(w[i]+" ");
print(l,r,i);
System.out.println(p[p.length-2]);
}
}
private static void print(int[] l,int[] r,int index){
if(l[index]!=-1 && r[index]!=-1){
System.out.print((l[index]+r[index])+" ");
print(l,r,l[index]);
print(l,r,r[index]);
}else{
System.out.print("0 "+index+" "+index+" ");
}
}
}
|
