用C++实现：给定n个节点的数值，构造哈夫曼树，输出其节点权值之和

好的，我来回答你的问题。构造哈夫曼树的基本思路是将所有节点按照权值从小到大排序，并将最小的两个节点合并成一个新的父节点，并将它们的权值之和作为新节点的权值。重复这个过程直到只剩下一个节点为止，这个节点即为哈夫曼树的根节点。

以下是用 C 语言实现构造哈夫曼树并输出节点权值之和的示例代码：

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

// 定义哈夫曼树节点结构体
typedef struct node {
    int val;    // 节点权值
    struct node *left, *right;    // 左右子节点指针
} node;

// 定义最小堆节点结构体
typedef struct minheapnode {
    node *huffnode;    // 对应哈夫曼树的节点指针
    struct minheapnode *left, *right;    // 左右子节点指针
} minheapnode;

// 定义最小堆结构体
typedef struct minheap {
    int size;    // 最小堆大小
    minheapnode **arr;    // 最小堆节点指针数组
} minheap;

// 创建新节点
node* new_node(int val) {
    node *newnode = (node*) malloc(sizeof(node));
    newnode->val = val;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}

// 创建新最小堆节点
minheapnode* new_minheapnode(node *huffnode) {
    minheapnode *newminheapnode = (minheapnode*) malloc(sizeof(minheapnode));
    newminheapnode->huffnode = huffnode;
    newminheapnode->left = NULL;
    newminheapnode->right = NULL;
    return newminheapnode;
}

// 交换两个最小堆节点指针
void swap_minheapnode_ptr(minheapnode **a, minheapnode **b) {
    minheapnode *temp = *a;
    *a = *b;
    *b = temp;
}

// 最小堆的从下往上调整过程
void minheapify_up(minheap *mh, int idx) {
    int parent = (idx - 1) / 2;
    if (idx > 0 && mh->arr[parent]->huffnode->val > mh->arr[idx]->huffnode->val) {
        swap_minheapnode_ptr(&mh->arr[parent], &mh->arr[idx]);
        minheapify_up(mh, parent);
    }
}

// 最小堆的从上往下调整过程
void minheapify_down(minheap *mh, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    if (left < mh->size && mh->arr[left]->huffnode->val < mh->arr[smallest]->huffnode->val) {
        smallest = left;
    }
    if (right < mh->size && mh->arr[right]->huffnode->val < mh->arr[smallest]->huffnode->val) {
        smallest = right;
    }
    if (smallest != idx) {
        swap_minheapnode_ptr(&mh->arr[smallest], &mh->arr[idx]);
        minheapify_down(mh, smallest);
    }
}

// 将一个最小堆节点插入到最小堆中
void insert_minheapnode(minheap *mh, minheapnode *mhn) {
    mh->size++;
    int i = mh->size - 1;
    while (i > 0 && mh->arr[(i - 1) / 2]->huffnode->val > mhn->huffnode->val) {
        mh->arr[i] = mh->arr[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    mh->arr[i] = mhn;
}

// 从最小堆中取出最小的节点指针
minheapnode* extract_min(minheap *mh) {
    if (mh->size <= 0) {
        return NULL;
    }
    if (mh->size == 1) {
        mh->size--;
        return mh->arr[0];
    }
    minheapnode *root = mh->arr[0];
    mh->arr[0] = mh->arr[mh->size - 1];
    mh->size--;
    minheapify_down(mh, 0);
    return root;
}

// 判断一个最小堆是否只剩下一个节点
int is_minheap_single_node(minheap *mh) {
    return mh->size == 1;
}

// 构造哈夫曼树
node* build_huffman_tree(int *arr, int n) {
    // 将所有节点包装成最小堆节点并插入最小堆中
    minheap *mh = (minheap*) malloc(sizeof(minheap));
    mh->size = 0;
    mh->arr = (minheapnode**) malloc(n * sizeof(minheapnode*));
    for (int i = 0; i < n; i++) {
        mh->arr[i] = new_minheapnode(new_node(arr[i]));
        mh->size++;
    }
    // 不断从最小堆中取出最小的两个节点并合并成新节点，直到只剩下一个节点
    while (!is_minheap_single_node(mh)) {
        minheapnode *left = extract_min(mh);
        minheapnode *right = extract_min(mh);
        minheapnode *parent = new_minheapnode(new_node(left->huffnode->val + right->huffnode->val));
        parent->left = left;
        parent->right = right;
        insert_minheapnode(mh, parent);
    }
    // 最后剩下的节点即为哈夫曼树的根节点
    node *huffroot = mh->arr[0]->huffnode;
    free(mh->arr);
    free(mh);
    return huffroot;
}

// 计算哈夫曼树节点权值之和
int calc_huffman_weight(node *root) {
    if (root == NULL) {
        return 0;
    }
    return root->val + calc_huffman_weight(root->left) + calc_huffman_weight(root->right);
}

int main() {
    int n = 5;
    int arr[] = {1, 3, 4, 5, 7};
    node *root = build_huffman_tree(arr, n);
    int weight = calc_huffman_weight(root);
    printf("The sum of node values in the Huffman tree is %d\n", weight);
    return 0;
}

希望这个代码对你有帮助！如果你有其他问题，可以随时问我。