构造哈夫曼树序号小的放左边用c++写出来

以下是构造哈夫曼树序号小的放左边的C代码实现：

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

#define MAX_NUM_NODES 100

typedef struct {
    char symbol;
    int freq;
} Node;

typedef struct {
    int parent;
    int left;
    int right;
} TreeNode;

void huffman_encoding(Node *nodes, int num_nodes, TreeNode *tree) {
    int i, j, min1, min2;
    int freq[MAX_NUM_NODES];
    int parent[MAX_NUM_NODES];
    int left[MAX_NUM_NODES];
    int right[MAX_NUM_NODES];
    int num_codes = num_nodes - 1;

    for (i = 0; i < num_nodes; i++) {
        freq[i] = nodes[i].freq;
    }

    for (i = 0; i < num_codes; i++) {
        min1 = min2 = -1;
        for (j = 0; j < num_nodes; j++) {
            if (freq[j] > 0) {
                if (min1 == -1 || freq[j] < freq[min1]) {
                    min2 = min1;
                    min1 = j;
                } else if (min2 == -1 || freq[j] < freq[min2]) {
                    min2 = j;
                }
            }
        }
        freq[min1] += freq[min2];
        freq[min2] = 0;
        parent[min1] = num_nodes + i;
        parent[min2] = num_nodes + i;
        if (nodes[min1].symbol < nodes[min2].symbol) {
            left[num_nodes + i] = min1;
            right[num_nodes + i] = min2;
        } else {
            left[num_nodes + i] = min2;
            right[num_nodes + i] = min1;
        }
    }

    memcpy(tree[0].parent, parent, sizeof(int) * num_nodes);
    memcpy(tree[0].left, left, sizeof(int) * num_codes);
    memcpy(tree[0].right, right, sizeof(int) * num_codes);
}

int main() {
    Node nodes[] = {
        {'A', 45},
        {'B', 13},
        {'C', 12},
        {'D', 16},
        {'E', 9},
        {'F', 5}
    };
    int num_nodes = sizeof(nodes) / sizeof(nodes[0]);
    TreeNode tree[num_nodes - 1];
    int i, j;

    huffman_encoding(nodes, num_nodes, tree);

    printf("Symbol\tFrequency\tEncoding\n");
    for (i = 0; i < num_nodes; i++) {
        printf("%c\t%d\t\t", nodes[i].symbol, nodes[i].freq);
        for (j = num_nodes - 2; j >= 0; j--) {
            if (tree[j].left == i) {
                printf("0");
            } else if (tree[j].right == i) {
                printf("1");
            }
        }
        printf("\n");
    }

    return 0;
}

在这段代码中，我们使用了一个 `Node` 结构体表示每个节点的信息，包括符号和频率。使用一个 `TreeNode` 结构体数组来表示哈夫曼树的结构，包括父节点、左子树和右子树的索引。`huffman_encoding` 函数是构造哈夫曼树的主函数，其中使用了哈夫曼编码的经典算法。

在这个算法中，我们先将节点的频率信息保存在一个数组 `freq` 中，然后不断选择频率最小的两个节点进行合并，直到只剩下一个根节点为止。在合并的过程中，我们需要记录每个节点的父节点、左子树和右子树的索引，以便后面进行哈夫曼编码。

在选择左右子树的时候，我们使用了题目中要求的规则，即序号小的放在左边。最后，我们将构造好的哈夫曼树的结构信息保存在 `TreeNode` 结构体数组中，然后就可以使用这个哈夫曼树进行编码了。