C++實現哈夫曼樹算法

如何建立哈夫曼樹的，網上搜索一堆，這裡就不寫了，直接給代碼。
1.哈夫曼樹結點類：HuffmanNode.h
2.哈夫曼樹最小堆：HuffmanMinHeap.h
#ifndef HuffmanMinHeap_h 

#define HuffmanMinHeap_h 

#include "HuffmanNode.h" 

#include

using namespace std; c

onst int DefaultSize = 100; 

templateclass MinHeap { public: MinHeap(); // 構造函數 

~MinHeap(); // 析構函數 

void Insert(HuffmanNode*current); // 插入 

HuffmanNode*getMin(); // 獲取最小結點 

private: HuffmanNode*heap; // 動態數組存儲最小堆 

int CurrentSize; // 目前最小堆的結點數 

void ShiftUp(int start); // 向上調整 

void ShiftDown(int start, int m); // 下滑 }; // 構造函數

 templateMinHeap::MinHeap() { 

heap = new HuffmanNode[DefaultSize]; 

// 創建堆空間 

CurrentSize = 0; } // 析構函數 

templateMinHeap::~MinHeap() { delete []heap; 

// 釋放空間 

} 

// 插入 templatevoid MinHeap::Insert(HuffmanNode*current) { if(CurrentSize == DefaultSize) { cout << "堆已滿" << endl; return; } 

// 把current的數據複製到“數組末尾” heap[CurrentSize] = *current; // 向上調整堆 ShiftUp(CurrentSize); CurrentSize++; }

 // 獲取最小結點並在堆中刪除該結點 templateHuffmanNode*MinHeap::getMin() { if(CurrentSize == 0) { cout << "堆已空!" << endl; return NULL; } HuffmanNode*newNode = new HuffmanNode(); if(newNode == NULL) { cerr << "存儲空間分配失敗！" << endl; exit(1); } *newNode = heap[0]; // 將最小結點的數據複製給newNode heap[0] = heap[CurrentSize-1]; // 用最後一個元素填補 CurrentSize--; ShiftDown(0, CurrentSize-1); // 從0位置開始向下調整 

return newNode; } // 向上調整 templatevoid MinHeap::ShiftUp(int start) { // 從start開始，直到0或者當前值大於雙親結點的值時，調整堆 int j = start, i = (j-1)/2; // i是j的雙親 

HuffmanNodetemp = 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; } 

// 向下調整 

templatevoid MinHeap::ShiftDown(int start, int m) { int i = start, j = 2 * i + 1; // j是i的左子女 

HuffmanNodetemp = heap[i]; while(j <= m) { if(j < m && heap[j].weight > heap[j+1].weight) j++; 

// 選兩個子女中較小者 if(temp.weight <= heap[j].weight) break; else { heap[i] = heap[j]; i = j; j = 2 * j + 1; } } heap[i] = temp; } #endif /* HuffmanMinHeap_h */