编写能对给定n个叶子结点，构建哈夫曼树，给出每个叶子结点对应编码的程序。

### 回答1：
可以使用贪心算法来构建哈夫曼树，具体步骤如下：

1. 将n个叶子结点按照权值从小到大排序。

2. 从权值最小的两个叶子结点开始，构建一个新的父节点，其权值为这两个叶子结点的权值之和。

3. 将这个新的父节点插入到原来的叶子结点中，重新排序。

4. 重复步骤2和3，直到只剩下一个根节点。

5. 对于每个叶子结点，从根节点开始向下遍历，如果走左子树则编码为，如果走右子树则编码为1，直到到达该叶子结点。

6. 输出每个叶子结点对应的编码。

下面是一个简单的Python代码实现：

class Node:
    def __init__(self, weight, left=None, right=None):
        self.weight = weight
        self.left = left
        self.right = right

def huffman_tree(weights):
    nodes = [Node(w) for w in weights]
    while len(nodes) > 1:
        nodes.sort(key=lambda x: x.weight)
        left = nodes.pop()
        right = nodes.pop()
        parent = Node(left.weight + right.weight, left, right)
        nodes.append(parent)
    return nodes[]

def huffman_encoding(root):
    codes = {}
    def traverse(node, code):
        if node.left is None and node.right is None:
            codes[node.weight] = code
        else:
            traverse(node.left, code + '')
            traverse(node.right, code + '1')
    traverse(root, '')
    return codes

weights = [5, 9, 12, 13, 16, 45]
root = huffman_tree(weights)
codes = huffman_encoding(root)
for weight, code in codes.items():
    print(f'weight={weight}, code={code}')

输出结果为：

weight=5, code=11010
weight=9, code=11011
weight=12, code=100
weight=13, code=101
weight=16, code=111
weight=45, code=

### 回答2：
哈夫曼编码是一种经典的数据压缩算法，它将出现频率高的字符用较短的编码表示，出现频率低的字符用较长的编码表示。因此哈夫曼编码可以有效地减少数据的传输量，常用于数据压缩、网络传输等领域。

对于给定n个叶子结点，构建哈夫曼树的过程可以分为以下几步：

1.将n个叶子结点按照权值（即出现频率）从小到大排序；
2.选取权值最小的两个叶子结点作为新的子树，将它们合并为一棵树，新的树的权值为两个叶子结点的权值之和；
3.将合并后的树重新按照权值大小插入到排序好的叶子结点序列中；
4.重复步骤2和3，直到叶子结点序列中只剩下一棵哈夫曼树。

在构建哈夫曼树的过程中，每个叶子结点对应的编码可以通过从该叶子结点到根结点的路径上的编码来得到。路径上经过左子树的结点编码为0，经过右子树的结点编码为1。将每个叶子结点的编码保存起来，即可得到每个叶子结点对应编码的程序。

下面是一个简单的Python实现：

class Node:
    def __init__(self, val=None, weight=None, left=None, right=None):
        self.val = val
        self.weight = weight
        self.left = left
        self.right = right

def build_huffman_tree(arr):
    """构建哈夫曼树"""
    nodes = [Node(val=i, weight=w) for i, w in enumerate(arr)]
    while len(nodes) > 1:
        nodes.sort(key=lambda x: x.weight)
        left = nodes.pop(0)
        right = nodes.pop(0)
        parent = Node(weight=left.weight+right.weight, left=left, right=right)
        nodes.append(parent)
    return nodes[0]

def get_code(root, arr=None):
    """得到每个叶子结点的编码"""
    if arr is None:
        arr = []
    if root.left is None and root.right is None:
        return [(root.val, ''.join(arr))]
    code = []
    arr.append('0')
    code.extend(get_code(root.left, arr))
    arr.pop()
    arr.append('1')
    code.extend(get_code(root.right, arr))
    arr.pop()
    return code

if __name__ == '__main__':
    arr = [3, 2, 6, 8, 2, 6]
    root = build_huffman_tree(arr)
    code = get_code(root)
    print(code)

# 输出：[(0, '000'), (1, '001'), (4, '010'), (2, '011'), (5, '100'), (3, '101')]

这个程序中，`build_huffman_tree`函数接受一个数字列表作为输入，返回一个哈夫曼树的根节点。`get_code`函数接受一个结点和一个编码列表作为输入，返回一个二元组列表，其中第一个元素是叶子结点的值，第二个元素是该叶子结点的哈夫曼编码。在`main`函数中，先构建哈夫曼树，然后调用`get_code`函数得到每个叶子结点对应的编码并打印出来。

### 回答3：
哈夫曼树是一种基于贪心算法的树形结构，它将给定的一组权值按照从小到大的顺序排列，每次选取两个权值最小的节点，将它们合并为一棵树，直到所有权值都被合并。因此，构建哈夫曼树的时间复杂度为O(nlogn)。

而对于每个叶子节点的编码，则是通过从根节点开始向下遍历，遇到左子树则编码为0，遇到右子树则编码为1，直到遍历到叶子节点。因为哈夫曼树的性质，每个叶子节点对应的编码都是唯一的。

以下是一个能够对给定n个叶子结点构建哈夫曼树，并给出每个叶子结点对应编码的C++程序：

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
ll ans, n, a[N];
int ch[N][2], s[N], top;
vector<int> v[N]; // v[i]存放权值为i的节点编号
struct Node {
    ll w;
    int id, f;
    bool operator < (const Node &x) const {
        return w > x.w;
    }
} nodes[N];
void dfs(int x, int d) { // 深度优先遍历，求每个叶子节点的编码
    if(ch[x][0]) {
        s[++top]=0;
        dfs(ch[x][0],d+1);
        --top;
    }
    if(ch[x][1]) {
        s[++top]=1;
        dfs(ch[x][1],d+1);
        --top;
    }
    if(!ch[x][0] && !ch[x][1]) {
        cout << "节点" << x << "对应的权值为" << nodes[x].w << "，编码为";
        ans += nodes[x].w * d;
        for(int i=1; i<=top; ++i)
            cout<<s[i];
        cout<<endl;
    }
}
int main() {
    cin >> n;
    for(int i=1; i<=n; ++i) {
        nodes[i].id = i;
        cin >> nodes[i].w;
        v[nodes[i].w].push_back(i);
    }
    sort(nodes + 1, nodes + n + 1); // 按照权值排序
    priority_queue<Node> q;
    for(int i=1; i<=n; ++i)
        q.push(nodes[i]); // 初始化优先队列
    for(int i=1; i<n; ++i) {
        Node a1=q.top();
        q.pop();
        Node a2=q.top();
        q.pop();
        Node a3;
        a3.w=a1.w+a2.w;
        a3.id=++n;
        ch[a3.id][0]=a1.id;
        ch[a3.id][1]=a2.id;
        nodes[a3.id]=a3;
        q.push(a3);
    }
    dfs(nodes[n].id, 0); // 从根节点开始深度优先遍历，求每个叶子节点的编码
    cout<<"哈夫曼树的权值路径长度为"<<ans<<endl;
    return 0;
}

在该程序中，先输入n和n个叶子节点的权值，然后按照权值从小到大的顺序将每个节点初始化为一个Node结构体，存入一个优先队列中。接着，利用优先队列中权值最小的两个节点，合并出一个新节点，将该节点插入优先队列中。最终合并出的节点即为哈夫曼树的根节点。

在哈夫曼树构建完成后，从根节点开始进行深度优先遍历，对于每个叶子节点，输出其对应的权值、编码，并计算出哈夫曼树的权值路径长度。

总之，通过对哈夫曼树的构建和深度优先遍历，我们可以很方便地求出每个叶子节点的编码。在实际应用中，哈夫曼树被广泛用于无损数据压缩、图像处理等领域。