已知下列字符a、b、c、d、e、f、g的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树ht的存储结构的初态和终态。

### 回答1：
初态：
ht[]：3 1 2
ht[1]：12
ht[2]：7
ht[3]：4
ht[4]：2
ht[5]：8
ht[6]：11

终态：
ht[]：45 1 2 3 4 5 6
ht[1]：12
ht[2]：7
ht[3]：4
ht[4]：2
ht[5]：8
ht[6]：11

### 回答2：
哈夫曼树是一种用于数据压缩的树形结构，通过将频繁出现的字符对应的编码设置短一些，减少录入数据的大小，使得数据传输更快速，节省传输资源。在这里，已知字符a、b、c、d、e、f、g的权值分别为3、12、7、4、2、8，11，我们需要填写出其对应的哈夫曼树ht的存储结构的初态和终态。

初态：首先，把所有字符权值作为叶节点，构成 n 颗只含单个节点的树。然后，将相邻的两棵权值最小的树通过一条新的线合并，并且合并后的树权值为两棵树的权值之和，同时把新的树插入到森林中，在此过程中，我们还需要记录下来每次合并两颗树的顺序，这个记录就是存储哈夫曼树ht的初态。

初始森林中一共有7棵树，然后依次完成下面的合并过程：
1.找到最小的两棵树，它们分别是‘e’和‘g’。这两棵树合并，权值之和为2+11=13，得到一棵新树。
2.找到最小的两棵树，它们分别是‘a’和新树。这两棵树合并，权值之和为3+13=16，得到一棵新树。
3.找到最小的两棵树，它们分别是’f‘和新树。这两棵树合并，权值之和为8+16=24，得到一棵新树。
4.找到最小的两棵树，它们分别是‘d’和新树。这两棵树合并，权值之和为4+24=28，得到一棵新树。
5.找到最小的两棵树，它们分别是‘c’和新树。这两棵树合并，权值之和为7+28=35，得到一棵新树。
6.找到最小的两棵树，它们分别是‘b’和新树。这两棵树合并，权值之和为12+35=47，得到一棵新树。

经过上述的六次合并，我们最终得到了一颗完整的哈夫曼树，它的存储结构为：

终态：
47
/ \
/ \
35 b
/ \
/ \
28 c
/ \
/ \
24 d
/ \
/ \
16 f
/ \
/ \
e g

从上图中可以看出，整个哈夫曼树的权值是47，权值小的字符对应的编码长度短一些，而权值大的字符对应的编码长度长一些。在数据传输中使用哈夫曼编码的方式进行压缩，就可以实现数据的高效传输。

### 回答3：
初态：
哈夫曼树的初始状态为空树，没有任何节点。

终态：
根据哈夫曼树的构建算法，最小权值的节点会先被合并，所以先将权值从小到大排序：
a（3）- e（2）- d（4）- g（11）- c（7）- f（8）- b（12）

1. 先将权值最小的a和e合并，权值为5，生成一个父节点，节点权值为5，左孩子为a，右孩子为e。
2. 再将权值为4的d和权值为5的合并，生成一个父节点，节点权值为9，左孩子为d，右孩子为父节点a-e。
3. 将权值为7的c和权值为8的f合并，生成一个父节点，节点权值为15，左孩子为c，右孩子为f。
4. 将权值为9的a-e-d和权值为11的g合并，生成一个父节点，节点权值为20，左孩子为a-e-d，右孩子为g。
5. 最后将权值为12的b和节点权值为15的c-f合并，生成一个父节点，节点权值为27，左孩子为b，右孩子为c-f。

最终的哈夫曼树ht存储结构的初态为：空树。
最终的哈夫曼树ht存储结构的终态为：

27
/ \
12 15
/ \
c f
/ \
7 8
/ \
a-e-d g

其中，0代表左孩子，1代表右孩子。用数组表示，存储结构如下：

ht[0].weight = 27;
ht[0].lchild = 1;
ht[0].rchild = 2;

ht[1].weight = 12;
ht[1].lchild = -1; //叶子节点没有子节点，左右孩子均为-1
ht[1].rchild = -1;

ht[2].weight = 15;
ht[2].lchild = 3;
ht[2].rchild = 4;

ht[3].weight = 7;
ht[3].lchild = 5;
ht[3].rchild = 6;

ht[4].weight = 8;
ht[4].lchild = 7;
ht[4].rchild = 8;

ht[5].weight = 3;
ht[5].lchild = -1;
ht[5].rchild = -1;

ht[6].weight = 4;
ht[6].lchild = -1;
ht[6].rchild = -1;

ht[7].weight = 11;
ht[7].lchild = -1;
ht[7].rchild = -1;

ht[8].weight = 2;
ht[8].lchild = -1;
ht[8].rchild = -1;