给定几个权值如何构造哈夫曼树

哈夫曼树是一种二叉树，它的每个叶子节点都表示一个权值，而每个非叶子节点都表示两个权值的和。哈夫曼树的构造方法如下：

1. 对于给定的权值，按照权值从小到大排序。

2. 取出权值最小的两个节点，将它们作为左右子节点构造一个新的节点，该节点的权值为这两个节点的权值之和。

3. 将新节点插入到已经排好序的权值序列中，保持序列有序。

4. 重复步骤2和步骤3，直到只剩下一个节点为止，这个节点就是哈夫曼树的根节点。

例如，假设给定的权值为[5, 4, 3, 2, 1]，按照从小到大的顺序排序之后，序列为[1, 2, 3, 4, 5]。按照上述步骤构造哈夫曼树的过程如下：

1. 取出权值最小的两个节点1和2，构造一个新的节点3，该节点的权值为1+2=3。序列变为[3, 3, 4, 5]。

2. 取出权值最小的两个节点3和3，构造一个新的节点6，该节点的权值为3+3=6。序列变为[4, 5, 6]。

3. 取出权值最小的两个节点4和5，构造一个新的节点9，该节点的权值为4+5=9。序列变为[9, 6]。

4. 取出权值最小的两个节点6和9，构造一个新的节点15，该节点的权值为6+9=15。序列变为[15]。

最后得到的哈夫曼树如下所示：

      15
     /  \
    6    9
   / \
  3   3
 / \
1   2

相关问题

给定权值构造哈夫曼树

哈夫曼树是一种带有权值的二叉树，它的构造方法是通过贪心策略，将权值最小的两个节点合并成一个新节点，直到最后只剩下一个节点为止。下面是给定权值构造哈夫曼树的详细步骤：

1. 将所有权值作为叶子节点，构造一个节点集合。

2. 从节点集合中选出两个权值最小的节点，合并成一个新节点，权值为两个节点的权值之和。

3. 将新节点加入节点集合中，并删除原来的两个节点。

4. 重复步骤2和3，直到节点集合中只剩下一个节点为止，这个节点就是哈夫曼树的根节点。

下面是一个示例，假设给定的权值为[5, 9, 12, 13, 16, 45]：

首先构造出6个叶子节点：

   5    9    12    13    16    45
  /    /    /     /     /     /
  A    B    C     D     E     F

然后按照上面的步骤，合并权值最小的两个节点：

   5    9    12    13    16    45
  /    /    /     /          /  
  A    B    C     D     ┌────F
                        │
                       61
                        │
                        └────E

继续合并权值最小的两个节点：

   5    9    12          13    16    45
  /    /    /           /     /     /
  A    B    C     ┌────D     E     F
               │
              25
               │
               └─────┐
                     │
                    36
                     │
                     └────C

继续合并权值最小的两个节点：

   5          9    12          13    16    45
  /           /    /           /     /     /
  A           B    ┌─────┐     D     E     F
                    │     │
                   25    36
                    │     │
                    └─────┘
                        │
                       61
                        │
                        └────C

最后只剩下一个节点，它就是哈夫曼树的根节点：

                             111
                            /   \
                           /     \
                          /       \
                         /         \
                        /           \
                       /             \
                      /               \
                     /                 \
                    /                   \
                   /                     \
                  /                       \
                 /                         \
                /                           \
               /                             \
              /                               \
             /                                 \
            /                                   \
           /                                     \
          /                                       \
         /                                         \
        5                                           106
       / \                                          /   \
      /   \                                        /     \
     /     \                                      /       \
    A       B                                    C         61
                                                 / \
                                                /   \
                                               D     E

因此，给定权值构造出的哈夫曼树就是上面的树形结构。

给定权值构造哈夫曼树C语言代码

### 回答1：
以下是给定权值构造哈夫曼树的C语言代码：

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 1000

typedef struct Node {
    int weight; // 权值
    struct Node *left; // 左子树
    struct Node *right; // 右子树
} Node, *HuffmanTree;

// 找到最小的两个结点
void selectMin(HuffmanTree *h1, HuffmanTree *h2, HuffmanTree *tree, int size) {
    int i;
    *h1 = *h2 = NULL;
    for (i = 0; i < size; i++) {
        if (!tree[i].weight) continue;
        if (*h1 == NULL || tree[i].weight < (*h1)->weight) {
            *h2 = *h1;
            *h1 = &tree[i];
        } else if (*h2 == NULL || tree[i].weight < (*h2)->weight) {
            *h2 = &tree[i];
        }
    }
}

// 构造哈夫曼树
HuffmanTree createHuffmanTree(int *weights, int size) {
    HuffmanTree tree = (HuffmanTree)malloc(sizeof(Node) * MAXSIZE);
    int i;
    for (i = 0; i < size; i++) {
        tree[i].weight = weights[i];
        tree[i].left = NULL;
        tree[i].right = NULL;
    }

    for (i = size; i < 2 * size - 1; i++) {
        HuffmanTree h1, h2;
        selectMin(&h1, &h2, tree, i);
        tree[i].weight = h1->weight + h2->weight;
        tree[i].left = h1;
        tree[i].right = h2;
    }

    return &tree[size - 1];
}

// 打印哈夫曼编码
void printHuffmanCode(HuffmanTree tree, int code[], int top) {
    if (tree->left) {
        code[top] = 0;
        printHuffmanCode(tree->left, code, top + 1);
    }

    if (tree->right) {
        code[top] = 1;
        printHuffmanCode(tree->right, code, top + 1);
    }

    if (!tree->left && !tree->right) {
        int i;
        printf("%d: ", tree->weight);
        for (i = 0; i < top; i++) {
            printf("%d", code[i]);
        }
        printf("\n");
    }
}

int main() {
    int weights[4] = {5, 6, 8, 9};
    HuffmanTree tree = createHuffmanTree(weights, 4);
    int code[MAXSIZE], top = 0;
    printHuffmanCode(tree, code, top);
    return 0;
}

该代码中，首先定义了哈夫曼树的结构体Node，并定义了HuffmanTree为Node指针类型。然后通过selectMin函数找到最小的两个结点，并通过createHuffmanTree函数构造哈夫曼树。最后通过printHuffmanCode函数打印哈夫曼编码。在main函数中，我们给出了一个示例，即有4个权值分别为5、6、8、9的结点构成的哈夫曼树。

### 回答2：
下面是一个使用C语言构造哈夫曼树的简单实现：

#include <stdio.h>
#include <stdlib.h>

// 定义哈夫曼树结点的结构体
typedef struct HuffmanNode {
    int weight;
    struct HuffmanNode* left;
    struct HuffmanNode* right;
} HuffmanNode;

// 创建一个哈夫曼树结点
HuffmanNode* createHuffmanNode(int weight) {
    HuffmanNode* node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
    node->weight = weight;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 构造哈夫曼树
HuffmanNode* constructHuffmanTree(int *weights, int n) {
    HuffmanNode** nodes = (HuffmanNode**)malloc(n * sizeof(HuffmanNode*));
    for (int i = 0; i < n; i++) {
        nodes[i] = createHuffmanNode(weights[i]);
    }
    
    while (n > 1) {
        // 找到权值最小的两个结点
        int i1 = 0, i2 = 1;
        if (nodes[i1]->weight > nodes[i2]->weight) {
            int temp = i1;
            i1 = i2;
            i2 = temp;
        }
        
        // 找到权值第二小的结点
        for (int i = 2; i < n; i++) {
            if (nodes[i]->weight < nodes[i1]->weight) {
                i2 = i1;
                i1 = i;
            } else if (nodes[i]->weight < nodes[i2]->weight) {
                i2 = i;
            }
        }
        
        // 创建新的父结点，权值为两个子结点的权值之和
        HuffmanNode* parent = createHuffmanNode(nodes[i1]->weight + nodes[i2]->weight);
        parent->left = nodes[i1];
        parent->right = nodes[i2];
        
        // 将父结点放入数组，删除原来的两个结点
        nodes[i1] = parent;
        nodes[i2] = nodes[n-1];
        n--;
    }
    
    return nodes[0];
}

int main() {
    int weights[] = {4, 2, 7, 9, 1, 5};
    int n = sizeof(weights) / sizeof(int);
    
    HuffmanNode* root = constructHuffmanTree(weights, n);
    
    printf("构造哈夫曼树成功\n");
    
    return 0;
}

以上是一个简单的使用C语言构造哈夫曼树的代码，首先定义了哈夫曼树的结点结构体，包含权值和左右子结点的指针。然后定义了创建哈夫曼树结点的函数createHuffmanNode，接受一个权值作为参数，返回一个新创建的结点。

接下来是构造哈夫曼树的函数constructHuffmanTree，接受一个权值数组和权值个数作为参数，返回构造好的哈夫曼树的根结点。在这个函数中，首先根据权值数组创建相应数量的结点，并存放在一个数组中。然后进行迭代，每次找到权值最小的两个结点，将它们合并为一个父结点，并将父结点放入数组中。最终，数组中只剩下一个结点，即为构造好的哈夫曼树的根结点。

在main函数中，我们给出一个权值数组，调用constructHuffmanTree函数构造哈夫曼树，并打印构造成功的提示信息。

### 回答3：
下面是一个用C语言实现的构造哈夫曼树的代码：

#include <stdio.h>
#include <stdlib.h>

// 哈夫曼树节点的结构体
typedef struct TreeNode {
int weight;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;

// 根据给定的权值数组构造哈夫曼树
TreeNode* buildHuffmanTree(int weights[], int n) {
// 创建存放n个哈夫曼树节点的数组
TreeNode **nodes = (TreeNode**)malloc(n * sizeof(TreeNode*));
for (int i = 0; i < n; i++) {
nodes[i] = (TreeNode*)malloc(sizeof(TreeNode));
nodes[i]->weight = weights[i];
nodes[i]->left = NULL;
nodes[i]->right = NULL;
}

while (n > 1) {
// 找到权值最小的两个节点
int minIndex1 = 0;
int minIndex2 = 1;
if (nodes[minIndex1]->weight > nodes[minIndex2]->weight) {
int temp = minIndex1;
minIndex1 = minIndex2;
minIndex2 = temp;
}
for (int i = 2; i < n; i++) {
if (nodes[i]->weight < nodes[minIndex1]->weight) {
minIndex2 = minIndex1;
minIndex1 = i;
} else if (nodes[i]->weight < nodes[minIndex2]->weight) {
minIndex2 = i;
}
}

// 创建一个新的节点作为两个最小节点的父节点
TreeNode *parent = (TreeNode*)malloc(sizeof(TreeNode));
parent->weight = nodes[minIndex1]->weight + nodes[minIndex2]->weight;
parent->left = nodes[minIndex1];
parent->right = nodes[minIndex2];

// 将新节点加入数组，并将最小节点从数组中删除
nodes[minIndex1] = parent;
nodes[minIndex2] = nodes[n - 1];

// 更新节点个数
n--;
}

// 返回哈夫曼树的根节点
return nodes[0];
}

// 打印哈夫曼树
void printHuffmanTree(TreeNode *root) {
if (root == NULL) {
return;
}

printf("%d\n", root->weight);
printHuffmanTree(root->left);
printHuffmanTree(root->right);
}

int main() {
int weights[] = {3, 5, 8, 2, 9};
int n = sizeof(weights) / sizeof(weights[0]);

TreeNode *root = buildHuffmanTree(weights, n);
printHuffmanTree(root);

return 0;
}

这段代码首先定义了一个哈夫曼树节点的结构体，包含权值和左右孩子节点指针。然后，根据给定的权值数组构造哈夫曼树的函数buildHuffmanTree被实现。在这个函数中，首先根据权值数组创建哈夫曼树节点，并将这些节点存放在一个数组中。然后，使用while循环找到数组中权值最小的两个节点，并将它们合并为一个新的父节点，并将新节点加入数组并删除原来的两个节点。当节点个数减少到1时，循环结束，返回哈夫曼树的根节点。最后，在main函数中定义一个权值数组并调用buildHuffmanTree函数构造哈夫曼树，然后调用printHuffmanTree函数打印哈夫曼树的权值。