huffmantree.cpp

这是一个数据结构课程的关于霍夫曼树问题的源代码

#include <iostream>
#include <stdlib.h>

using namespace std;
// MinHeap
template <class T>
class MinHeap//最小堆类
{
private:
 T *heapArray;
 int CurrentSize;
 int MaxSize;
 void swap(int pos_x, int pos_y);
 void BuildHeap();

public:
 MinHeap(const int n);//构造最小堆
 virtual ~MinHeap() {delete [] heapArray;};//析构

 bool isLeaf(int pos) const {return (pos >= CurrentSize/2) && (pos < CurrentSize);};//是否为叶结点
 int leftchild(int pos) const {return pos*2 + 1;};//左子树
 int rightchild(int pos) const {return pos*2 + 2;};//右子树
 int parent(int pos) const {return (pos - 1) / 2;};//双亲

 bool Remove(int pos, T&node);//删除函数
 bool Insert(const T&newNode);//插入函数
 T &RemoveMin();

 void SiftUp(int position);//自下而上调整函数
 void SiftDown(int left);//自上而下调整函数

 void DisplayHeap();
};

template <class T>
MinHeap<T>::MinHeap(const int n)//最小堆构造函数
{
 if (n <= 0)
  return;

 CurrentSize = 0;
 MaxSize = n;
 heapArray = new T[MaxSize];
 BuildHeap();
}

template <class T>
void MinHeap<T>::BuildHeap()//最小堆调整函数
{
 for (int i = CurrentSize/2 -1; i >= 0; i --)
  SiftDown(i);
}

template <class T>
bool MinHeap<T>::Insert(const T &newNode)//插入函数
{
 if (CurrentSize == MaxSize)
  return false;

 heapArray[CurrentSize] = newNode; // 插在表尾
 SiftUp(CurrentSize);
 CurrentSize ++;
 
 return true;
}

template <class T>
void MinHeap<T>::SiftUp(int position)//自下而上调整
{
 int temppos = position;
 T temp = heapArray[temppos];

 while ((temppos > 0) && (heapArray[parent(temppos)] > temp))
 {
  heapArray[temppos] = heapArray[parent(temppos)];
  temppos = parent(temppos);
 }

 heapArray[temppos] = temp;
}

template <class T>
void MinHeap<T>::SiftDown(int left)//自上而下调整
{
 int i = left;
 int j = leftchild(i);
 T temp = heapArray[i];
 
 while (j < CurrentSize)
 {
  if ((j < CurrentSize - 1) && (heapArray[j] > heapArray[j + 1]))
   j ++;
  
  if (temp > heapArray[j])
  {
   heapArray[i] = heapArray[j];
   i = j;
   j = leftchild(j);
  }
  else
   break;
 }
 
 heapArray[i] = temp;
}

template <class T>
void MinHeap<T>::swap(int pos_x, int pos_y)
{
 T temp = heapArray[pos_x];
 heapArray[pos_x] = heapArray[pos_y];
 heapArray[pos_y] = temp;
}

template <class T>
T &MinHeap<T>::RemoveMin()
{
 if (CurrentSize == 0)
 {
  cout << "Can't delete.\n";
  exit(1);
 }
 else
 {
  swap(0, --CurrentSize);
  if (CurrentSize > 1)
   SiftDown(0);

  return heapArray[CurrentSize];
 }
}

template <class T>
bool MinHeap<T>::Remove(int pos, T&node)
{
 if (pos < 0 || pos >= CurrentSize)
  return false;

 T temp = heapArray[pos];
 heapArray[pos] = heapArray[--CurrentSize];
 SiftUp(pos);
 SiftDown(pos);
 node = temp;
 return true;
}

template <class T>
void MinHeap<T>::DisplayHeap()
{
 T temp;
 int j = CurrentSize;
 for (int i = 0; i < j; i ++)
 {
  temp = RemoveMin();
  cout << temp << " ";
 }

 cout << "\n\n";
}

//Huffman
template <class T> class HuffmanTree;
template <class T>
class HuffmanTreeNode
{
 friend class HuffmanTree<T>;
private:
 T element;
 HuffmanTreeNode<T> *parent;
 HuffmanTreeNode<T> *left;
 HuffmanTreeNode<T> *right;
  
public:
 HuffmanTreeNode() {};

 HuffmanTreeNode<T> *leftchild() {return left};
 HuffmanTreeNode<T> *rightchild() {return right;};
 bool operator > (HuffmanTreeNode<T> &HN) {return element > HN.element;}; 
 bool operator < (HuffmanTreeNode<T> &HN) {return element < HN.element;}; 
 bool operator == (HuffmanTreeNode<T> &HN) {return element == HN.element;};
};

template <class T>
class HuffmanTree
{
private:
 HuffmanTreeNode<T> *root;
 
public:
 HuffmanTree(T weight[], int n);//构造函数
 virtual ~HuffmanTree() {DeleteTree(root);};

 void MergeTree(HuffmanTreeNode<T> &ht1, HuffmanTreeNode<T> &ht2, HuffmanTreeNode<T> *parent);
 void DeleteTree(HuffmanTreeNode<T> *root);//删除根节点函数
 void InOrder(HuffmanTreeNode<T> *root);//中序遍历霍夫曼树
 HuffmanTreeNode<T> *GetRoot() {return root;};
};

template <class T>
void HuffmanTree<T>::DeleteTree(HuffmanTreeNode<T> *root)//删除根结点
{
 if (root)
 {
  DeleteTree(root->left);
  DeleteTree(root->right);
  delete root;
 }
}

template <class T>
void HuffmanTree<T>::InOrder(HuffmanTreeNode<T> *root)//中序遍历
{
 if (root)
 {
  InOrder(root->left);
  cout << root->element << " ";
  InOrder(root->right);
 }
}

template <class T>
void HuffmanTree<T>::MergeTree(HuffmanTreeNode<T> &ht1, HuffmanTreeNode<T> &ht2, HuffmanTreeNode<T> *parent)
{
 HuffmanTreeNode<T> *l = new HuffmanTreeNode<T>();
 HuffmanTreeNode<T> *r = new HuffmanTreeNode<T>();

 *l = ht1; // 不能写为l = &ht1，注意地址引用，开辟的是新空间，或者应用拷贝构造函数，只是有写麻烦
 *r = ht2;
 
 parent->parent = NULL;
 parent->left = l;
 parent->right = r;
 parent->element = ht1.element + ht2.element;
 ht1.parent = ht2.parent = parent; // 指向父节点
}

template <class T>
HuffmanTree<T>::HuffmanTree(T weight[], int n)
{
 MinHeap<HuffmanTreeNode<T> > heap(n); // 注意..>>之间隔开
 HuffmanTreeNode<T> *parent, firstchild, secodechild, firstchild1, secodechild1;
 HuffmanTreeNode<T> *NodeList = new HuffmanTreeNode<T>[n];

 for (int i = 0; i < n; i ++)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      
 {
  NodeList[i].element = weight[i];
  NodeList[i].parent = NodeList[i].left = NodeList[i].right = NULL;
  heap.Insert(NodeList[i]);
 }

 for (i = 0; i < n-1; i ++)
 {
  parent = new HuffmanTreeNode<T>();
  firstchild = heap.RemoveMin();
  secodechild = heap.RemoveMin();
  MergeTree(firstchild, secodechild, parent); // 合并树
  heap.Insert(*parent);
  root = parent;
 }
 delete []NodeList;
}

void main()
{
 int weight[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};
 int n = sizeof(weight)/sizeof(int);
 HuffmanTree<int> aHT(weight, n);
 aHT.InOrder(aHT.GetRoot());
}