如何在C++中构建右受限Huffman树（左子节点深度不大于右子节点）

方案一：先构建普通Huffman树，后调整为右受限结构 #

实现思路 #

先按常规逻辑构建Huffman树，再递归遍历所有内部节点：比较左右子树的最大深度，若左子树深度大于右子树，则交换左右子节点，确保左子节点深度始终不超过右子节点。

C++ 代码实现 #

节点结构定义

#include <iostream>
#include <vector>
#include <queue>
#include <memory>
#include <algorithm>

// 基类节点
struct Node {
    int weight;
    virtual ~Node() = default;
    virtual int max_depth() const = 0; // 计算子树最大深度
};

// 叶子节点（带符号）
struct LeafNode : Node {
    char symbol;
    LeafNode(char s, int w) : symbol(s), weight(w) {}
    int max_depth() const override { return 0; } // 叶子节点深度为0
};

// 内部节点（含子节点）
struct InternalNode : Node {
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    InternalNode(std::unique_ptr<Node> l, std::unique_ptr<Node> r) 
        : left(std::move(l)), right(std::move(r)) {
        weight = left->weight + right->weight;
    }
    int max_depth() const override {
        return 1 + std::max(left->max_depth(), right->max_depth());
    }
};

普通Huffman树构建

// 构建常规Huffman树
std::unique_ptr<Node> build_normal_huffman(const std::vector<std::pair<char, int>>& symbols) {
    // 最小堆：按权重升序排列
    auto cmp = [](const std::unique_ptr<Node>& a, const std::unique_ptr<Node>& b) {
        return a->weight > b->weight;
    };
    std::priority_queue<std::unique_ptr<Node>, std::vector<std::unique_ptr<Node>>, decltype(cmp)> pq(cmp);

    // 所有叶子节点入堆
    for (const auto& p : symbols) {
        pq.push(std::make_unique<LeafNode>(p.first, p.second));
    }

    // 合并节点生成树
    while (pq.size() > 1) {
        auto left = std::move(const_cast<std::unique_ptr<Node>&>(pq.top()));
        pq.pop();
        auto right = std::move(const_cast<std::unique_ptr<Node>&>(pq.top()));
        pq.pop();
        pq.push(std::make_unique<InternalNode>(std::move(left), std::move(right)));
    }

    return pq.empty() ? nullptr : std::move(const_cast<std::unique_ptr<Node>&>(pq.top()));
}

调整为右受限结构

// 递归调整树，确保左子树深度 ≤ 右子树深度
void adjust_to_right_restricted(std::unique_ptr<Node>& node) {
    if (!node) return;
    InternalNode* internal = dynamic_cast<InternalNode*>(node.get());
    if (!internal) return; // 叶子节点无需调整

    // 先递归调整子节点
    adjust_to_right_restricted(internal->left);
    adjust_to_right_restricted(internal->right);

    // 若左子深度大于右子，交换两者
    int left_depth = internal->left->max_depth();
    int right_depth = internal->right->max_depth();
    if (left_depth > right_depth) {
        std::swap(internal->left, internal->right);
    }
}

测试与验证

// 打印每个符号的Huffman编码
void print_codes(const Node* node, std::string code) {
    if (!node) return;
    const LeafNode* leaf = dynamic_cast<const LeafNode*>(node);
    if (leaf) {
        std::cout << leaf->symbol << ": " << code << std::endl;
        return;
    }
    const InternalNode* internal = dynamic_cast<const InternalNode*>(node);
    print_codes(internal->left.get(), code + "0");
    print_codes(internal->right.get(), code + "1");
}

int main() {
    // 测试用例：符号及对应权重
    std::vector<std::pair<char, int>> symbols = {
        {'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}
    };

    // 构建普通树并调整
    auto tree = build_normal_huffman(symbols);
    adjust_to_right_restricted(tree);

    // 输出编码
    std::cout << "右受限Huffman编码：" << std::endl;
    print_codes(tree.get(), "");

    return 0;
}

方案二：直接构建右受限Huffman树（更高效） #

实现思路 #

在Huffman树的构建阶段直接满足约束：

1. 优先队列排序规则：权重优先升序，权重相同时子树深度小的节点优先取出
2. 合并节点前主动检查深度，若左节点深度更大则交换两者，再完成合并

C++ 代码实现 #

// 直接构建右受限Huffman树
std::unique_ptr<Node> build_right_restricted_huffman(const std::vector<std::pair<char, int>>& symbols) {
    // 最小堆：先按权重升序，权重相同则按子树深度升序
    auto cmp = [](const std::unique_ptr<Node>& a, const std::unique_ptr<Node>& b) {
        if (a->weight != b->weight) {
            return a->weight > b->weight;
        }
        return a->max_depth() > b->max_depth(); // 深度小的节点优先
    };
    std::priority_queue<std::unique_ptr<Node>, std::vector<std::unique_ptr<Node>>, decltype(cmp)> pq(cmp);

    // 叶子节点入堆
    for (const auto& p : symbols) {
        pq.push(std::make_unique<LeafNode>(p.first, p.second));
    }

    // 合并节点，同时保证左子深度 ≤ 右子深度
    while (pq.size() > 1) {
        auto first = std::move(const_cast<std::unique_ptr<Node>&>(pq.top()));
        pq.pop();
        auto second = std::move(const_cast<std::unique_ptr<Node>&>(pq.top()));
        pq.pop();

        // 确保左子节点深度不大于右子节点
        if (first->max_depth() > second->max_depth()) {
            std::swap(first, second);
        }

        pq.push(std::make_unique<InternalNode>(std::move(first), std::move(second)));
    }

    return pq.empty() ? nullptr : std::move(const_cast<std::unique_ptr<Node>&>(pq.top()));
}

方案对比 #

• 方案一：逻辑简单，基于现有普通Huffman树代码修改即可，但需额外遍历调整，适合小规模场景或快速原型开发。
• 方案二：构建过程中直接满足约束，无额外调整开销，性能更优，适合大规模数据处理。

内容的提问来源于stack exchange，提问作者Aerith