用c语言实现哈佛曼树的建立算法

Question

即输入一个有n个叶结点的权值构造一棵哈夫曼树；（例如：n=8，权值为 5 297814 23319)
(1） 要求程序能够显示出哈夫曼树的构造过程，即每一步选出的两个最小值是谁，以他们做为左右子树构造一棵新的哈夫曼树之后，显示当前还有哪些权值。
(2） 程序要有良好的用户界面，且以与用户交互的方式运行。
实现哈夫曼算法的数据类型定义：
结点应存储四种信息：结点的权值、左右子树地址、及双亲结点地址

Answer 1

附上代码示例，望采纳。

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

// 结点结构体
typedef struct Node {
    int weight;      // 权重
    struct Node *left;   // 左子树
    struct Node *right;  // 右子树 
    struct Node *parent; // 父结点
} Node; 

// 创建叶子结点 
Node* createLeaf(int weight) {
    Node* leaf = (Node*)malloc(sizeof(Node));
    leaf->weight = weight;
    leaf->left = leaf->right = NULL;
    return leaf;
}

// 选择最小的两个结点
void selectMin(Node* leaves[], int n, Node** first, Node** second) {
    *first = *second = NULL;
    for (int i = 0; i < n; i++) {
        if (!*first || leaves[i]->weight < (*first)->weight) 
            *first = leaves[i];
    }
    for (int i = 0; i < n; i++) {
        if (leaves[i] != *first && (!*second || leaves[i]->weight < (*second)->weight))
             *second = leaves[i];
    }
} 

// 创建哈夫曼树    
Node* createHuffman(int weights[], int n) {
    Node* leaves[n];
    for (int i = 0; i < n; i++) leaves[i] = createLeaf(weights[i]);
    
    while (n > 1) { 
        Node *first, *second;
        selectMin(leaves, n, &first, &second); //选择最小的两个结点 
        
        Node* parent = (Node*)malloc(sizeof(Node)); // 创建父结点
        parent->left = first;
        first->parent = parent;
        parent->right = second;
        second->parent = parent;
        parent->weight = first->weight + second->weight;
        
        // 更新leaves[]和n 
        for (int i = 0; i < n; i++) {
            if (leaves[i] == first || leaves[i] == second) {
                leaves[i] = parent;
                break;
            }
        }
        n--;              
        
        // 显示当前步骤选出的结点和剩余的结点
        printf("选出%d和%d,构造父结点%d,剩余:", first->weight, second->weight, parent->weight);
        for (int i = 0; i < n; i++) printf("%d ", leaves[i]->weight);
        printf("\n");
    }
    return leaves[0]; 
}

int main() {
    int weights[] = {5, 29, 7, 8, 14, 2, 13, 3, 19};
    Node* huffman = createHuffman(weights, 9);
    // 显示哈夫曼树的构造过程...
}