实现哈夫曼树,设n=4,w={5,29,7,8},输出huffman树的一维数组

### 回答1：
首先，根据哈夫曼编码的规则，字符的编码是由叶子节点到根节点的路径上的“0”和“1”组成的。每个节点都是其左右子树的权值之和。因此，我们可以根据题目给定的n和w数组构建哈夫曼树。

首先，我们将w数组从小到大排序，得到{5,7,8,29}。然后，我们可以用一个数组freq来记录每个节点的权值。对于叶子节点，其权值就是对应字符在字符串中出现的频率；对于非叶子节点，其权值就是其左右子树的权值之和。初始时，freq数组的前四个元素就是w数组中的元素。

接下来，我们可以用一个数组parent来记录每个节点的父亲节点。初始时，所有节点都没有父亲节点，因此parent数组的值均为-1。然后，我们可以循环四次，每次找出freq数组中最小的两个元素，将它们合并成一个新节点，并把新节点的权值填入freq数组的下一个空位。然后，将这两个最小值对应的节点的parent数组更新为新节点的下标。直到最后只剩下一个节点，即为根节点。

最后，我们可以根据parent数组来构造哈夫曼树的一维数组表示。具体地，我们从根节点开始，依次遍历每个节点，并将其左右子树在数组中的下标填入对应位置。如果一个节点没有左子树或右子树，则在对应位置填-1。最终得到的数组就是一维数组表示的哈夫曼树。

### 回答2：
哈夫曼树又称最优二叉树，它是一种按照带权路径长度最小原则构建的二叉树。构造哈夫曼树需要一组带权的输入数据，假设共有 n 个输入数据，每个数据都有一个权重 w_i，那么构造哈夫曼树的过程如下：

1. 将这 n 个数据视为 n 棵只有根节点的二叉树 T1, T2, ..., Tn。

2. 在 n 棵二叉树中选取两棵根节点权值最小的树，作为左右子树构造一棵新的二叉树，其根节点权值为两棵子树的根节点权值之和。

3. 将新的二叉树加入到已有的二叉树集合中，重复 2,3 步，直到只剩下一棵二叉树为止，这棵二叉树就是哈夫曼树。

对于本题数据 w={5, 29, 7, 8}，我们可以按照如下步骤构造哈夫曼树：

1. 将这 4 个数据视为 4 棵只有根节点的二叉树 T1={5}, T2={29}, T3={7}, T4={8}。

2. 选取 T3, T4，构造新的二叉树 T34，其根节点权值为 7+8=15，T34={15}，此时剩下 T1={5}, T2={29}, T34={15}。

3. 选取 T1, T34，构造新的二叉树 T134，其根节点权值为 5+15=20，T134={20}，此时剩下 T2={29}, T134={20}。

4. 选取 T2, T134，构造新的二叉树 T1234，其根节点权值为 20+29=49，T1234={49}。

5. 构造完毕，T1234 就是哈夫曼树。

根据哈夫曼树的构造，我们可以得到哈夫曼树的一维数组表示。对于节点 i，如果它是叶子节点，则其数组下标是 i-n（n 为叶子节点个数），其权值为 w_i；如果它是非叶子节点，则其数组下标是 i，其权值为通往左子树和右子树的边权之和。

对于本题数据，哈夫曼树的一维数组表示为 [15, 20, 49, 5, 29, 7, 8]，其中叶子节点为 5, 29, 7, 8，非叶子节点为 15, 20, 49。

### 回答3：
哈夫曼树是一种二叉树，它的叶子节点是字符，每个叶子节点都有一个权值。哈夫曼树的构造过程是将权值最小的两个节点合并成一个新节点，其权值为两个节点权值之和，并将其作为新的叶子节点插入到原来的节点集合中。重复此过程，最终形成一棵哈夫曼树。

根据题目中给出的数据，我们可以先将其排序，得到w={5，7，8，29}。然后，我们可以按照哈夫曼树的构造过程进行如下操作：

1. 将权值最小的两个节点5和7合并成一个节点，它的权值为12。此时，节点集合变成了{12, 8, 29}。
2. 再将权值最小的两个节点8和12合并成一个节点，它的权值为20。此时，节点集合变成了{20, 29}。
3. 最后将权值最小的两个节点20和29合并成一个节点，它的权值为49。此时，节点集合中只剩下根节点。

我们可以得到构造出的哈夫曼树如下图所示：

49
/ \
20 29
/ \
12 8
/ \
5 7

根据哈夫曼树的定义，我们可以将其表示为一维数组。假设哈夫曼树有n个叶子节点，则其一维数组的长度为2n-1，其中前n个元素表示叶子节点及其权值，后n-1个元素表示非叶子节点及其权值。

根据题目数据，我们可以构造出哈夫曼树的一维数组为：

[5, 7, 8, 29, 12, 20, 49]

其中，前四个元素表示叶子节点及其权值，后三个元素表示非叶子节点及其权值。可以发现，这个一维数组的前四个元素与给定的权值数组w相同，只是顺序有所不同。