C++實現Huffman最優二叉樹

Huffman最優二叉樹對於壓縮編碼具有重要作用

本文利用C++實現了Huffman二叉樹做學習參考

[cpp]
/*huffman樹——最優二叉樹*/ 
#include <iostream>  
#include <vector>  
#include <algorithm>  
 
using namespace std; 
 
//定義節點結構體類型  
typedef struct Node { 
    int val;     
    Node *left, *right, *parent;  //左右節點和父節點指針  
    void set(int value, Node *lft, Node *rgt) {  
        val = value;  
        left = lft;  
        right = rgt;  
        parent = NULL; 
    }; 
    Node() { 
        val = -1; 
        left = right = parent = NULL; 
    } 
} Node; 
 
//存放節點的向量  
vector<Node> nodes; 
//存放節點編號的向量  
vector<int> pnodes; 
//初始化最小帶權路徑和  
int sum = 0; 
//按照節點編號對應節點的值對編號進行排序  
bool sortpnode(int a, int b) 
{ 
    return nodes[a].val < nodes[b].val; 
} 
 
//利用遞歸遍歷huffman樹實現輸出  
void output(Node *tree) 
{ 
    Node *ptr; 
    //若當前節點為空，退出  
    if (tree == NULL) 
        return; 
    //否則，輸出當前根節點的值  
    cout << tree->val << "-> Left: " << (tree->left ? tree->left->val : -1) << ", Right: " << (tree->right ? tree->right->val : -1) << endl; 
    //若左孩子不為空，則通過遞歸遍歷左子樹  
    if (tree->left)  
        output(tree->left); 
    //若左孩子已遍歷，且右子樹不為空，則通過遞歸遍歷右子樹  
    if (tree->right) 
        output(tree->right); 
    //若當前節點的左右孩子都為空，則說明該節點是葉子節點  
    //此時，計算其帶權路徑並求和  
    if (!tree->left && !tree->right) 
    { 
        //計算到根節點的長度  
        int level = 0; 
        ptr = tree->parent; 
        while(ptr != NULL) 
        { 
            level++; 
            ptr = ptr->parent; 
        }        
        //用葉子深度乘以  
        sum += level * tree->val;         
        cout << "深度：" << level << ", 節點值：" << tree->val << "，帶權路徑和=" << sum << endl;        
    } 
} 
 
int main() 
{ 
    int values[] = {1, 2, 3, 4, 5, 30, 5, 8},  
        n = sizeof(values)/sizeof(int);  
    int cnt = n; 
    Node *tnode; 
    //直接在nodes中放入(2 + n) * n / 2  
    nodes.resize(2 * n - 1); 
    //為pnodes設置n個元素，且每個元素——即節點編號為-1  
    pnodes.resize(n, -1); 
    //為節點賦值  
    for(int i = 0; i < n; i++) 
    {        
        nodes[i].val = values[i];        
        pnodes[i] = i; 
    } 
    //循環  
    while(pnodes.size() > 1) 
    { 
        //按照節點編號所對象節點的值對節點編號排序  
        sort(pnodes.begin(), pnodes.end(), sortpnode); 
        //0--n-1為已處理節點，cnt編號對應的為待處理節點  
        tnode = &nodes[cnt]; 
        //為派生節點賦值並指定左、右孩子及父節點  
        tnode->val = nodes[pnodes[0]].val + nodes[pnodes[1]].val; 
        tnode->left = &nodes[pnodes[0]]; 
        tnode->right = &nodes[pnodes[1]]; 
        tnode->parent = NULL; 
        //將派生節點編號加入pnodes向量  
        pnodes.insert(pnodes.begin(), cnt); 
        //設置孩子節點的父節點地址  
        nodes[pnodes[1]].parent = &nodes[cnt]; 
        nodes[pnodes[2]].parent = &nodes[cnt]; 
        //從pnodes中刪除已處理的節點編號  
        pnodes.erase(pnodes.begin() + 1); 
        pnodes.erase(pnodes.begin() + 1); 
        //設置下一個派生節點的編號  
        cnt++; 
    } 
    //nodes[cnt-1]為樹的根節點  
    //輸出樹  
    output(&nodes[cnt-1]); 
    //輸出huffman樹的最小帶權路徑長度  
    cout << "最小帶權路徑長為：" << sum << endl; 
    return 0; 
} 

/*huffman樹——最優二叉樹*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//定義節點結構體類型
typedef struct Node {
 int val; 
 Node *left, *right, *parent;  //左右節點和父節點指針
 void set(int value, Node *lft, Node *rgt) {
  val = value;
  left = lft;
  right = rgt;
  parent = NULL;
 };
 Node() {
  val = -1;
  left = right = parent = NULL;
 }
} Node;

//存放節點的向量
vector<Node> nodes;
//存放節點編號的向量
vector<int> pnodes;
//初始化最小帶權路徑和
int sum = 0;
//按照節點編號對應節點的值對編號進行排序
bool sortpnode(int a, int b)
{
 return nodes[a].val < nodes[b].val;
}

//利用遞歸遍歷huffman樹實現輸出
void output(Node *tree)
{
 Node *ptr;
 //若當前節點為空，退出
 if (tree == NULL)
  return;
 //否則，輸出當前根節點的值
 cout << tree->val << "-> Left: " << (tree->left ? tree->left->val : -1) << ", Right: " << (tree->right ? tree->right->val : -1) << endl;
 //若左孩子不為空，則通過遞歸遍歷左子樹
 if (tree->left)
  output(tree->left);
 //若左孩子已遍歷，且右子樹不為空，則通過遞歸遍歷右子樹
 if (tree->right)
  output(tree->right);
 //若當前節點的左右孩子都為空，則說明該節點是葉子節點
 //此時，計算其帶權路徑並求和
 if (!tree->left && !tree->right)
 {
  //計算到根節點的長度
  int level = 0;
  ptr = tree->parent;
  while(ptr != NULL)
  {
   level++;
   ptr = ptr->parent;
  }  
  //用葉子深度乘以
  sum += level * tree->val;  
  cout << "深度：" << level << ", 節點值：" << tree->val << "，帶權路徑和=" << sum << endl;  
 }
}

int main()
{
 int values[] = {1, 2, 3, 4, 5, 30, 5, 8},
     n = sizeof(values)/sizeof(int); 
 int cnt = n;
 Node *tnode;
 //直接在nodes中放入(2 + n) * n / 2
 nodes.resize(2 * n - 1);
 //為pnodes設置n個元素，且每個元素——即節點編號為-1
 pnodes.resize(n, -1);
 //為節點賦值
 for(int i = 0; i < n; i++)
 {  
  nodes[i].val = values[i];  
  pnodes[i] = i;
 }
 //循環
 while(pnodes.size() > 1)
 {
  //按照節點編號所對象節點的值對節點編號排序
  sort(pnodes.begin(), pnodes.end(), sortpnode);
  //0--n-1為已處理節點，cnt編號對應的為待處理節點
  tnode = &nodes[cnt];
  //為派生節點賦值並指定左、右孩子及父節點
  tnode->val = nodes[pnodes[0]].val + nodes[pnodes[1]].val;
  tnode->left = &nodes[pnodes[0]];
  tnode->right = &nodes[pnodes[1]];
  tnode->parent = NULL;
  //將派生節點編號加入pnodes向量
  pnodes.insert(pnodes.begin(), cnt);
  //設置孩子節點的父節點地址
  nodes[pnodes[1]].parent = &nodes[cnt];
  nodes[pnodes[2]].parent = &nodes[cnt];
  //從pnodes中刪除已處理的節點編號
  pnodes.erase(pnodes.begin() + 1);
  pnodes.erase(pnodes.begin() + 1);
  //設置下一個派生節點的編號
  cnt++;
 }
 //nodes[cnt-1]為樹的根節點
 //輸出樹
 output(&nodes[cnt-1]);
 //輸出huffman樹的最小帶權路徑長度
 cout << "最小帶權路徑長為：" << sum << endl;
 return 0;
}