Question

（1）代码

#include <iostream>
#include "Heap.h"
using namespace std;

#define N 6
extern int length;
int result[N+1];
//哈夫曼树
struct Huffman_Tree
{
  node *root;
  Huffman_Tree():root(NULL){}
};
//哈夫曼编码
void Huffman(unsigned int *A, Huffman_Tree *T)
{
  int n = N;
  while(n > 1)
  {
    //生成一个新的结点
    node *z = new node;
    //选择堆顶元素作为其左结点
    z->left = (node *)Heap_Extract_Min(A);
    //选择堆顶元素作为其右结点
    z->right = (node *)Heap_Extract_Min(A);
    z->p = z->left->p + z->right->p;
    //将新结点插入堆中
    Min_Heap_Insert(A, (unsigned int)z);
    n--;
  }
  //剩下最后一个结点时，这个结点就是树的根结点
  T->root = (node *)Heap_Extract_Min(A);
}
//输出这棵树上每个字母的编码
void PrintTree(node *t, int cnt)
{
  int i;
  //叶子结点
  if(t->data != -1)
  {
    //输出其值及编码
    cout<<t->data<<' ';
    for(i = 0; i < cnt; i++)
      cout<<result[i];
    cout<<endl;
    return ;
  }
  //非叶子结点，对其孩子进行递归
  result[cnt] = 0;
  PrintTree(t->left, cnt+1);
  result[cnt] = 1;
  PrintTree(t->right, cnt+1);
}
/*
f 5
e 9
c 12
b 13
d 16
a 45
*/
int main()
{
  unsigned int A[N+1] = {};//存储的是结点的地址
  length = N;
  int i;
  char c;
  double p;
  //构造 N 个结点
  for(i = 1; i <= N; i++)
  {
    cin>>c>>p;
    node *z = new node(c, p);
    A[i] = (unsigned int)z;
  }
  //构造最小堆
  Build_Min_Heap(A);
  //构造哈夫曼树
  Huffman_Tree *T = new Huffman_Tree();
  Huffman(A, T);
  //输出编码结果
  PrintTree(T->root, 0);
  return 0;
}

（2）习题

16.3-2

能

16.3-6

#include <iostream>
#include "Heap.h"//选择 p 最小的结点时要借助于堆来实现
using namespace std;

#define N 6
extern int length;
int result[N+1];
//哈夫曼树
struct Huffman_Tree
{
  node *root;
  Huffman_Tree():root(NULL){}
};
//哈夫曼编码
void Huffman(unsigned int *A, Huffman_Tree *T)
{
  int n = N;
  while(n > 1)
  {
    //生成一个新的结点
    node *z = new node;
    if(n--)
    {
      //选择堆顶元素作为其左结点
      z->left = (node *)Heap_Extract_Min(A);
      z->p = z->p + z->left->p;
    }
    if(n--)
    {
      //选择堆顶元素作为其中间结点
      z->middle = (node *)Heap_Extract_Min(A);
      z->p = z->p + z->middle->p;
    }
    if(n--)
    {
      //选择堆顶元素作为其右结点
      z->right = (node *)Heap_Extract_Min(A);
      z->p = z->p + z->right->p;
    }
    //将新结点插入堆中
    Min_Heap_Insert(A, (unsigned int)z);
    n++;
  }
  //剩下最后一个结点时，这个结点就是树的根结点
  T->root = (node *)Heap_Extract_Min(A);
}
//输出这棵树上每个字母的编码
void PrintTree(node *t, int cnt)
{
  int i;
  //叶子结点
  if(t->data != -1)
  {
    //输出其值及编码
    cout<<t->data<<' ';
    for(i = 0; i < cnt; i++)
      cout<<result[i];
    cout<<endl;
    return ;
  }
  //非叶子结点，对其孩子进行递归
  result[cnt] = 0;
  PrintTree(t->left, cnt+1);
  result[cnt] = 1;
  PrintTree(t->middle, cnt+1);
  if(t->right)
  {
    result[cnt] = 2;
    PrintTree(t->right, cnt+1);
  }
}
/*
f 5
e 9
c 12
b 13
d 16
a 45
*/
int main()
{
  unsigned int A[N+1] = {};//存储的是结点的地址
  length = N;
  int i;
  char c;
  double p;
  //构造 N 个结点
  for(i = 1; i <= N; i++)
  {
    cin>>c>>p;
    node *z = new node(c, p);
    A[i] = (unsigned int)z;
  }
  //构造最小堆
  Build_Min_Heap(A);
  //构造哈夫曼树
  Huffman_Tree *T = new Huffman_Tree();
  Huffman(A, T);
  //输出编码结果
  PrintTree(T->root, 0);
  return 0;
}