用C语言写出给定权值为[1,2,3,4,5,6,7,8,9]，构建一颗哈夫曼树，并且利用先序遍历打印的代码

在C语言中，我们可以使用优先队列（通常用堆数据结构实现）以及递归来构建哈夫曼树并进行先序遍历。以下是一个简单的示例，假设我们有一个数组`weights`存储了权值： ```c #include <stdio.h> #include <stdlib.h> // 结点结构体 typedef struct Node { int weight; char value; struct Node* left, *right; } Node; // 创建一个新的结点 Node* createNode(int weight, char value) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->weight = weight; newNode->value = value; newNode->left = newNode->right = NULL; return newNode; } // 比较两个节点的权重，用于构造最小堆 int compareNodes(const void* a, const void* b) { Node* nodeA = *(Node**)a; Node* nodeB = *(Node**)b; return nodeA->weight - nodeB->weight; } // 插入节点到最小堆 void insertHeap(Node** heap, int weight, char value) { Node* newNode = createNode(weight, value); if (*heap == NULL) *heap = newNode; else { Node* parent = *heap; Node* child = NULL; while (parent && newNode->weight < parent->weight) { child = parent; parent = parent->weight < newNode->weight ? parent->left : parent->right; } if (newNode->weight > child->weight) child = newNode; if (child->weight == parent->weight) parent->right = newNode; else parent->left = newNode; newNode->left = newNode->right = NULL; } } // 从堆顶取出最小元素 Node* extractMin(Node* heap) { if (heap == NULL) return NULL; Node* minNode = heap; heap = heap->left; free(minNode); // 释放堆顶元素 if (heap) heap->left = heap->right; return heap; } // 先序遍历 void preOrderTraversal(Node* root) { if (root != NULL) { printf("%c", root->value); preOrderTraversal(root->left); preOrderTraversal(root->right); } } int main() { int weights[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; int n = sizeof(weights) / sizeof(weights[0]); // 构建最小堆 Node** heap = (Node**)malloc(sizeof(Node*) * n); for (int i = 0; i < n; i++) insertHeap(&heap, weights[i], 'A' + i); // 构建哈夫曼树 Node* huffmanRoot = extractMin(heap); // 打印先序遍历结果 preOrderTraversal(huffmanRoot); // 清理内存 Node* temp = huffmanRoot; while (temp) { Node* nextTemp = temp->right; free(temp); temp = nextTemp; } return 0; } ``` 这个程序首先创建了一个最小堆，然后通过反复提取堆顶元素并与剩余节点合并的方式构造哈夫曼树。最后，它使用先序遍历来打印构建出的哈夫曼树。