题目描述:
根据给定的叶结点字符及其对应的权值创建哈夫曼树。
输入:
第一行为叶子结点的数目n(1<=n<=100)。第二行为一个字符串,包含n个字符,每个字符对应一个叶子结点,第三行为每个叶子结点的概率(即权值),要求根据各叶结点构造哈夫曼树。构造哈夫曼树的原则是先两个最小的,构造一个父结点,其中最小的结点为左孩子,次小的为右孩子,如果两个最小的叶结点相等,则取排在前一个位置的为左孩子。
输出:
哈夫曼树的权值,左孩子,右孩子及其对应的父亲,相邻数据之间用空格隔开;
输入样例:
5
abcde
15 25 15 20 25
输出样例:
15 0 0 6
25 0 0 7
15 0 0 6
20 0 0 7
25 0 0 8
30 1 3 8
45 4 2 9
55 5 6 9
根据给定的叶结点字符及其对应的权值创建哈夫曼树。
输入:
第一行为叶子结点的数目n(1<=n<=100)。第二行为一个字符串,包含n个字符,每个字符对应一个叶子结点,第三行为每个叶子结点的概率(即权值),要求根据各叶结点构造哈夫曼树。构造哈夫曼树的原则是先两个最小的,构造一个父结点,其中最小的结点为左孩子,次小的为右孩子,如果两个最小的叶结点相等,则取排在前一个位置的为左孩子。
输出:
哈夫曼树的权值,左孩子,右孩子及其对应的父亲,相邻数据之间用空格隔开;
输入样例:
5
abcde
15 25 15 20 25
输出样例:
15 0 0 6
25 0 0 7
15 0 0 6
20 0 0 7
25 0 0 8
30 1 3 8
45 4 2 9
55 5 6 9
100 7 8 0
思路:就是选择两个最小的结点,并且没有父亲的结点。不断的拼凑就可以,
主要点:
相同的结点权值:选择下标小的,在前面。
交换的时候:第二个最小的可以直接赋值,第一个交换的时候,要判断第二个与第一个的之前的判断,在将新的值赋给第一个结点。
代码如下:
import java.util.Scanner; public class buildHuffmanTree { public static class huffmanTreeNode { int father; int lchild;/// 最小的 int rchild;/// 最大的 int value; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); huffmanTreeNode huffmanTreeArray[]; int number; String ti; number = sc.nextInt(); ti = sc.next(); huffmanTreeArray = new huffmanTreeNode[number * 2 + 1]; for (int i = 0; i <= number * 2; i++) huffmanTreeArray[i] = new huffmanTreeNode(); for (int i = 1; i <= number; i++) { huffmanTreeArray[i].father = 0; huffmanTreeArray[i].lchild = 0; huffmanTreeArray[i].rchild = 0; huffmanTreeArray[i].value = sc.nextInt(); } int min, max, t; for (int i = 1; i <= number - 1; i++) { /// 刚开始找两个没有父亲的作为最小最大的初始值 min = max = t = 0; for (int j = 1; j <= number + i - 1; j++) { if (huffmanTreeArray[j].father != 0) continue; if (t == 0) max = j; else min = j; t = t + 1; if (t == 2) break; } /// 先判断是不是要交换一下位置 if (huffmanTreeArray[min].value > huffmanTreeArray[max].value) { int k = min; min = max; max = k; } /// 下面就是正确的寻找最小和第二小的 for (int j = 1; j <= number + i - 1; j++) { if (huffmanTreeArray[j].father != 0 || j == min || j == max) continue; if (huffmanTreeArray[j].value < huffmanTreeArray[min].value) { if (huffmanTreeArray[min].value <= huffmanTreeArray[max].value) max = min; min = j; } else if (huffmanTreeArray[max].value > huffmanTreeArray[j].value) max = j; } /// 现在就是开始赋予孩子和父亲 huffmanTreeArray[min].father = number + i; huffmanTreeArray[max].father = number + i; huffmanTreeArray[number + i].value = huffmanTreeArray[max].value + huffmanTreeArray[min].value; if (huffmanTreeArray[max].value == huffmanTreeArray[min].value) { if (max < min) { huffmanTreeArray[number + i].rchild = min; huffmanTreeArray[number + i].lchild = max; } else { huffmanTreeArray[number + i].rchild = max; huffmanTreeArray[number + i].lchild = min; } } else { if (huffmanTreeArray[max].value > huffmanTreeArray[min].value) { huffmanTreeArray[number + i].lchild = min; huffmanTreeArray[number + i].rchild = max; } else { huffmanTreeArray[number + i].lchild = max; huffmanTreeArray[number + i].rchild = min; } } } /// 下面就是开始输出 for (int i = 1; i <= number * 2 - 1; i++) System.out.println(String.format("%d %d %d %d", huffmanTreeArray[i].value, huffmanTreeArray[i].lchild, huffmanTreeArray[i].rchild, huffmanTreeArray[i].father)); } }