#ifndef HuffmanNode_h
#define HuffmanNode_h
 
template <class T>
struct HuffmanNode {
 T weight; // 存儲(chǔ)權(quán)值
 HuffmanNode<T> *leftChild, *rightChild, *parent; // 左、右孩子和父結(jié)點(diǎn)
};
 
#endif /* HuffmanNode_h */

#ifndef HuffmanMinHeap_h
#define HuffmanMinHeap_h
 
#include "HuffmanNode.h"
#include <iostream>
using namespace std;
 
const int DefaultSize = 100;
 
template <class T>
class MinHeap {
public:
 MinHeap(); // 構(gòu)造函數(shù)
 ~MinHeap(); // 析構(gòu)函數(shù)
 void Insert(HuffmanNode<T> *current); // 插入
 HuffmanNode<T> *getMin(); // 獲取最小結(jié)點(diǎn)
private:
 HuffmanNode<T> *heap; // 動(dòng)態(tài)數(shù)組存儲(chǔ)最小堆
 int CurrentSize; // 目前最小堆的結(jié)點(diǎn)數(shù)
 void ShiftUp(int start); // 向上調(diào)整
 void ShiftDown(int start, int m); // 下滑
};
 
// 構(gòu)造函數(shù)
template <class T>
MinHeap<T>::MinHeap() {
 heap = new HuffmanNode<T>[DefaultSize]; // 創(chuàng)建堆空間
 CurrentSize = 0;
}
 
// 析構(gòu)函數(shù)
template <class T>
MinHeap<T>::~MinHeap() {
 delete []heap; // 釋放空間
}
 
// 插入
template <class T>
void MinHeap<T>::Insert(HuffmanNode<T> *current) {
 if(CurrentSize == DefaultSize) {
  cout << "堆已滿" << endl;
  return;
 }
 // 把current的數(shù)據(jù)復(fù)制到“數(shù)組末尾”
 heap[CurrentSize] = *current;
 // 向上調(diào)整堆
 ShiftUp(CurrentSize);
 CurrentSize++;
}
 
// 獲取最小結(jié)點(diǎn)并在堆中刪除該結(jié)點(diǎn)
template <class T>
HuffmanNode<T> *MinHeap<T>::getMin() {
 if(CurrentSize == 0) {
  cout << "堆已空!" << endl;
  return NULL;
 }
 HuffmanNode<T> *newNode = new HuffmanNode<T>();
 if(newNode == NULL) {
  cerr << "存儲(chǔ)空間分配失??！" << endl;
  exit(1);
 }
 *newNode = heap[0]; // 將最小結(jié)點(diǎn)的數(shù)據(jù)復(fù)制給newNode
 heap[0] = heap[CurrentSize-1]; // 用最后一個(gè)元素填補(bǔ)
 CurrentSize--;
 ShiftDown(0, CurrentSize-1); // 從0位置開始向下調(diào)整
 return newNode;
}
 
// 向上調(diào)整
template <class T>
void MinHeap<T>::ShiftUp(int start) {
 // 從start開始，直到0或者當(dāng)前值大于雙親結(jié)點(diǎn)的值時(shí)，調(diào)整堆
 int j = start, i = (j-1)/2; // i是j的雙親
 
 HuffmanNode<T> temp = heap[j];
 while(j > 0) {
  if(heap[i].weight <= temp.weight)
   break;
  else {
   heap[j] = heap[i];
   j = i;
   i = (j - 1) / 2;
  }
 }
 heap[j] = temp;
}
 
// 向下調(diào)整
template <class T>
void MinHeap<T>::ShiftDown(int start, int m) {
 int i = start, j = 2 * i + 1; // j是i的左子女
 
 HuffmanNode<T> temp = heap[i];
 while(j <= m) {
  if(j < m && heap[j].weight > heap[j+1].weight)
   j++; // 選兩個(gè)子女中較小者
  if(temp.weight <= heap[j].weight)
   break;
  else {
   heap[i] = heap[j];
   i = j;
   j = 2 * j + 1;
  }
 }
 heap[i] = temp;
}
 
 
#endif /* HuffmanMinHeap_h */

#ifndef HuffmanTree_h
#define HuffmanTree_h
 
 
#include "HuffmanMinHeap.h"
#include "HuffmanNode.h"
 
template <class T>
class HuffmanTree {
public:
 HuffmanTree(); // 構(gòu)造函數(shù)
 ~HuffmanTree(); // 析構(gòu)函數(shù)
 void Create(T w[], int n); // 創(chuàng)建哈夫曼樹
 void Merge(HuffmanNode<T> *first, HuffmanNode<T> *second, HuffmanNode<T> *parent); // 合并
 void PreOrder(); // 前序遍歷Huffman樹
private:
 HuffmanNode<T> *root; // 根結(jié)點(diǎn)
 void Destroy(HuffmanNode<T> *current); // 銷毀哈夫曼樹
 void PreOrder(HuffmanNode<T> *current); // 前序遍歷Huffman樹
};
 
// 構(gòu)造函數(shù)
template <class T>
HuffmanTree<T>::HuffmanTree() {
 root = NULL;
}
 
// 析構(gòu)函數(shù)
template <class T>
HuffmanTree<T>::~HuffmanTree() {
 Destroy(root); // 銷毀哈夫曼樹
}
 
// 銷毀哈夫曼樹
template <class T>
void HuffmanTree<T>::Destroy(HuffmanNode<T> *current) {
 if(current != NULL) { // 不為空
  Destroy(current->leftChild); // 遞歸銷毀左子樹
  Destroy(current->rightChild); // 遞歸銷毀右子樹
  delete current; // 釋放空間
  current = NULL;
 }
}
 
// 創(chuàng)建哈夫曼樹
template <class T>
void HuffmanTree<T>::Create(T w[], int n) {
 int i;
 MinHeap<T> hp; // 使用最小堆存放森林
 HuffmanNode<T> *first, *second, *parent = NULL;
 HuffmanNode<T>*work = new HuffmanNode<T>();
 
 if(work == NULL) {
  cerr << "存儲(chǔ)空間分配失??！" << endl;
  exit(1);
 }
 for(i = 0; i < n; i++) {
  work->weight = w[i];
  work->leftChild = work->rightChild = work->parent = NULL;
  hp.Insert(work); // 插入到最小堆中
 }
 for(i=0; i < n-1; i++) { // 做n-1趟，形成Huffman樹
  first = hp.getMin(); // 獲取權(quán)值最小的樹
  second = hp.getMin(); // 獲取權(quán)值次小的樹
  parent = new HuffmanNode<T>();
  if(parent == NULL) {
   cerr << "存儲(chǔ)空間分配失??！" << endl;
   exit(1);
  }
  Merge(first, second, parent); // 合并
  hp.Insert(parent); // 重新插入到最小堆中
 }
 root = parent; // 根結(jié)點(diǎn)
}
// 合并
template <class T>
void HuffmanTree<T>::Merge(HuffmanNode<T> *first, HuffmanNode<T> *second, HuffmanNode<T> *parent) {
 parent->leftChild = first; // 左子樹
 parent->rightChild = second; // 右子樹
 parent->weight = first->weight + second->weight; // 父結(jié)點(diǎn)權(quán)值
 first->parent = second->parent = parent; // 父指針
}
 
// 前序遍歷Huffman樹
template <class T>
void HuffmanTree<T>::PreOrder() {
 PreOrder(root);
}
 
// 前序遍歷Huffman樹
template <class T>
void HuffmanTree<T>::PreOrder(HuffmanNode<T> *current) {
 if(current != NULL) {
  cout << current->weight << " "; // 訪問當(dāng)前結(jié)點(diǎn)數(shù)據(jù)
  PreOrder(current->leftChild); // 遞歸遍歷左子樹
  PreOrder(current->rightChild); // 遞歸遍歷右子樹
 }
}
#endif /* HuffmanTree_h */

#include "HuffmanTree.h"
 
int main(int argc, const char * argv[]) {
 int arr[] = {7, 5, 2, 4};
 int len = sizeof(arr) / sizeof(arr[0]); // 數(shù)組長(zhǎng)度
 HuffmanTree<int> tree; // Huffman樹的對(duì)象
 
 tree.Create(arr, len); // 創(chuàng)建Huffman樹
 tree.PreOrder(); // 前序遍歷Huffman樹
 return 0;
}