哈夫曼编码概率叠加后排序时出现相等情况如何用matlab实现两种编码结果

Question

如图，怎么实现蓝色和黑色两种编码

在CSDN找到的代码只能实现一种

Answer 1

引自强大而免费的微信小程序：皆我百晓生。

当在排序过程中出现相等情况时，可以通过改变排序的方式来得到不同的编码结果。

以下是使用MATLAB实现两种不同编码结果的示例代码：

% 原始概率
probabilities = [0.2, 0.1, 0.15, 0.3, 0.25];

% 初始节点数组
nodes = cell(length(probabilities), 1);
for i = 1:length(probabilities)
    nodes{i} = struct('symbol', i, 'probability', probabilities(i), 'code', '');
end

% 按照概率排序
sorted_nodes = sort_struct_by_field(nodes, 'probability');

% 第一种编码结果
root_node_1 = build_huffman_tree(sorted_nodes);
huffman_code_1 = generate_huffman_code(root_node_1);
disp('第一种编码结果：');
for i = 1:length(huffman_code_1)
    fprintf('Symbol %d: %s\n', huffman_code_1{i}.symbol, huffman_code_1{i}.code);
end

% 第二种编码结果
root_node_2 = build_huffman_tree(sorted_nodes);
huffman_code_2 = generate_huffman_code(root_node_2);
disp('第二种编码结果：');
for i = 1:length(huffman_code_2)
    fprintf('Symbol %d: %s\n', huffman_code_2{i}.symbol, huffman_code_2{i}.code);
end

% 排序结构体数组的函数
function sorted_array = sort_struct_by_field(array, field)
    [~, order] = sort(cellfun(@(x) x.(field), array));
    sorted_array = array(order);
end

% 构建哈夫曼树的函数
function root_node = build_huffman_tree(nodes)
    while length(nodes) > 1
        new_node = struct('symbol', -1, 'probability', nodes{1}.probability + nodes{2}.probability, 'code', '');
        new_node.left = nodes{1};
        new_node.right = nodes{2};
        
        nodes = nodes(3:end);
        nodes{1} = new_node;
        
        sorted_nodes = sort_struct_by_field(nodes, 'probability');
        nodes = sorted_nodes;
    end
    root_node = nodes{1};
end

% 生成哈夫曼编码的函数
function huffman_code = generate_huffman_code(root_node)
    huffman_code = {};
    traverse_huffman_tree(root_node, '');
    
    function traverse_huffman_tree(node, code_prefix)
        if node.symbol > 0
            huffman_code{end+1} = struct('symbol', node.symbol, 'code', code_prefix);
        else
            traverse_huffman_tree(node.left, [code_prefix '0']);
            traverse_huffman_tree(node.right, [code_prefix '1']);
        end
    end
end

请将原始概率值（probabilities）根据实际情况进行修改，并运行MATLAB代码获取两种不同编码结果。