E-生成哈夫曼树(100p)

生成哈夫曼树

问题描述

LYA 是一名计算机专业的学生,最近她学习了哈夫曼编码。为了巩固知识,她决定写一个程序来生成哈夫曼树。

给定一个长度为 的正整数数组,每个数字代表二叉树叶子节点的权值。请你帮助 LYA 生成一棵哈夫曼树,并将其按中序遍历的顺序输出。

为了保证输出的哈夫曼树唯一,需要满足以下条件:

1. 树中每个非叶子节点的权值等于其左右子节点权值之和。

2. 对于权值相同的两个节点,左子树的高度应小于等于右子树的高度。

3. 在满足上述条件的前提下,左子节点的权值应小于等于右子节点的权值。

输入格式

第一行包含一个正整数 ,表示叶子节点的个数。

第二行包含 个正整数,表示每个叶子节点的权值,数值之间用空格分隔。

输出格式

输出一行,包含若干个正整数,表示按中序遍历哈夫曼树得到的节点权值序列,数值之间用空格分隔。

样例输入

5
5 15 40 30 10

样例输出

40 100 30 60 15 30 5 15 10

数据范围

权值

题解

本题考查哈夫曼树的构建。哈夫曼树是一种带权最优二叉树,其特点是带权路径长度最短。

构建哈夫曼树的基本步骤如下:

1. 将所有节点看成独立的树,并按照权值从小到大排序。

2. 取出权值最小的两棵树,将它们作为一个新树的左右子树,新树的权值为两棵子树权值之和。

3. 重复步骤 2,直到只剩下一棵树,即为所求的哈夫曼树。

在实现时,我们可以用优先队列来维护节点,每次取出权值最小的两个节点合并。为了保证输出的哈夫曼树唯一,在优先队列中比较两个节点时,先比较权值,权值相同再比较树高,树高也相同则比较左右子树的权值大小关系。

构建完哈夫曼树后,我们再进行一次中序遍历即可得到输出序列。

参考代码

• Python

import heapq


class Node:
    def __init__(self, lc, rc, weight, height):
        self.lc = lc  # 左孩子节点
        self.rc = rc  # 右孩子节点
        self.weight = weight  # 当前节点的权重
        self.height = height  # 当前节点代表子树的高度

    def __gt__(self, other):
        # 优先级比较时，权重小的优先级更高，权重相同时，高度小的优先级更高
        if self.weight != other.weight:
            return self.weight > other.weight
        else:
            return self.height > other.height


# 输入获取
n = int(input())
weights = list(map(int, input().split()))


# 二叉树中序遍历
def midOrder(root, seq):
    # 中序遍历，即先遍历二叉树的左子树，再遍历二叉树的根，最后遍历二叉树的右子树
    if root.lc is not None:
        midOrder(root.lc, seq)

    seq.append(root.weight)

    if root.rc is not None:
        midOrder(root.rc, seq)


# 算法入口
def getResult():
    pq = []

    # 创建n个哈夫曼树节点，并加入优先队列
    for w in weights:
        heapq.heappush(pq, Node(None, None, w, 0))

    # 初始n个节点经过多轮合并，只剩一个节点时，那么该节点就是哈夫曼树的根节点，因此当优先队列中只剩一个节点时即可停止合并
    while len(pq) > 1:
        # 取出优先队列中前两个权值最小的节点，由于优先队列已按照 [节点权重，节点子树高度] 升序优先级，因此先出来的肯定是权重小，或者高度小的节点，即作为新节点的左子树
        lc = heapq.heappop(pq)
        rc = heapq.heappop(pq)

        # 将lc和rc合并，合并后新节点fa的权重，是两个子节点权重之和，fa子树高度 = rc子树高度+1; PS：rc的高度>=lc的高度
        fa_weight = lc.weight + rc.weight
        fa_height = rc.height + 1

        # 将合并后的新节点加入优先队列
        heapq.heappush(pq, Node(lc, rc, fa_weight, fa_height))

    # 最后优先队列中必然只剩一个节点，即哈夫曼树的根节点，此时对此根节点（哈夫曼树）进行中序遍历
    root = heapq.heappop(pq)
    seq = []
    midOrder(root, seq)

    return " ".join(map(str, seq))


# 算法调用
print(getResult())

• Java

import java.util.*;

class Node implements Comparable<Node> {
    Node lc; // 左孩子节点
    Node rc; // 右孩子节点
    long weight; // 当前节点的权重
    int height; // 当前节点代表子树的高度

    public Node(Node lc, Node rc, long weight, int height) {
        this.lc = lc;
        this.rc = rc;
        this.weight = weight;
        this.height = height;
    }

    @Override
    public int compareTo(Node other) {
        // 优先级比较时，权重小的优先级更高，权重相同时，高度小的优先级更高
        if (this.weight != other.weight) {