#includeusing namespace std;


class HufTree{public:
    float weight = 0;   // 權(quán)重
    int parent = 0;     // 雙親
    int lchi = 0;       // 左孩子
    int rchi = 0;       // 右孩子
        
    void CreatHT(HufTree* &HT, int n);  // 創(chuàng)建哈夫曼樹方法
    void Select(HufTree* &HT, int k, int &s1, int &s2); // 得到權(quán)重最小的次小的下標方法
    char** Code(HufTree* HT, int n);    //實現(xiàn)哈夫曼編碼方法
};


void HufTree::CreatHT(HufTree* &HT, int n){int s1, s2;     // 聲明權(quán)重最小的下標s1和次小的下標s2
    HT = new HufTree[2 * n];    // 定義數(shù)組長度，0號位置不用，所以數(shù)組長度定義為2n-1+1，2n+1為最終哈夫曼樹的總結(jié)點數(shù)
    // 輸入每個結(jié)點的權(quán)重
    for(int i = 1; i< n + 1; ++i){cout<< "請輸入第 "<< i<< " 個結(jié)點的權(quán)重值："<< endl;
        cin >>HT[i].weight;
    }

    for(int i = n + 1; i< 2 * n; ++i){Select(HT, i - 1, s1, s2);      // 選出權(quán)重最小的兩個結(jié)點
        HT[i].weight = HT[s1].weight + HT[s2].weight;   // 結(jié)合兩個小結(jié)點得到一個新結(jié)點
        HT[i].lchi = s1;    // 新結(jié)點的左孩子為s1
        HT[i].rchi = s2;    // 新結(jié)點的有孩子為s2
        HT[s1].parent = i;  // s1的雙親是i
        HT[s2].parent = i;  // s2的雙親是i
    }
}


void HufTree::Select(HufTree* &HT, int k, int &s1, int &s2){// k為已有結(jié)點的長度加1（因為0號位置未使用）
    float t = 100;  // 初始化一個常數(shù)t
    // 通過比較得出s1
    for(int i = 1; i< k + 1; ++i){if(t >HT[i].weight && HT[i].parent == 0){s1 = i;
            t = HT[i].weight;
        }
    }
    t = 100;    // 重新初始化t
    // 通過跳過s1比較得到s2
    for(int i = 1; i< k + 1; ++i){if(i == s1) continue;
        if(t >= HT[i].weight && HT[i].parent == 0){s2 = i;
            t = HT[i].weight;
        }
    }
}


char** HufTree::Code(HufTree* HT, int n){char** HC = new char* [n + 1];  // 聲明一個二維字符數(shù)組，用以接收原數(shù)組需要編碼的字符的編碼
    char* cd = new char[n];     // 聲明一個一維字符數(shù)組用以儲存
    cd[n - 1] = '\0';   // cd數(shù)組的最后一位加上終止符
    // 遍歷原數(shù)組需要編碼的每個字符
    for(int i = 1; i< n + 1; ++i){int j = i;  // j用于在while循環(huán)內(nèi)實現(xiàn)從葉子結(jié)點找雙親
        int k = n - 2;  // k用于記錄當前cd數(shù)組空的位置，由于從葉子結(jié)點找雙親的話編碼順序是反的，所以要從尾部開始存入0和1
        while(HT[j].parent != 0){// 若當前結(jié)點的雙親為0，說明已遍歷到根結(jié)點，遍歷完畢
            // 若該葉子的雙親結(jié)點的左孩子為該葉子結(jié)點，則cd數(shù)組計入0
            if(HT[HT[j].parent].lchi == j){cd[k] = '0';
                --k; // k指向cd數(shù)組的前一個位置
            }
            // 若該葉子的雙親結(jié)點的右孩子為該葉子結(jié)點，則cd數(shù)組計入1
            if(HT[HT[j].parent].rchi == j){cd[k] = '1';
                --k; // k指向cd數(shù)組的前一個位置
            }
            j = HT[j].parent;   // 此時遍歷的結(jié)點更新為當前結(jié)點的雙親
        }
        HC[i] = new char[n - k];    // 申請一個和當前cd數(shù)組一樣大小的字符數(shù)組，另二維數(shù)組中的第i個一維數(shù)組指針指向該字符數(shù)組
        strcpy(HC[i], &cd[k + 1]);  // 將cd中包括k從k之后的所有字符復(fù)制給HC的第i個字符數(shù)組
    }
    delete [] cd;   // 釋放掉cd數(shù)組的空間
    return HC;  // 返回HC二維指針
}


int main()
{HufTree *a;     // 實例化一個HufTree指針a

    a->CreatHT(a, 7);   // 調(diào)用a中的創(chuàng)建方法創(chuàng)建一棵哈夫曼樹

    char** p = a->Code(a, 7);   // 實例化一個二維數(shù)組指針指向哈夫曼編碼數(shù)組

    // 打印二維數(shù)組
    for(int i = 1; i< 8; ++i){for(int j = 0; j< 7; ++j){cout<< p[i][j];
        }
        cout<< endl;
    }

    delete a;   // 釋放掉a的空間

    // 釋放掉二維數(shù)組p中的指針指向的空間
    for(int i = 0; i< 8; ++i){delete [] p[i];
    }

    delete [] p;    // 釋放掉指向二維數(shù)組p的空間
    return 0;  
}

實現(xiàn)創(chuàng)建包含7個元素的哈夫曼樹以及輸出其對應(yīng)的哈夫曼編碼。如有錯誤的地方，還請不吝賜教。

創(chuàng)新互聯(lián)建站憑借在網(wǎng)站建設(shè)、網(wǎng)站推廣領(lǐng)域領(lǐng)先的技術(shù)能力和多年的行業(yè)經(jīng)驗，為客戶提供超值的營銷型網(wǎng)站建設(shè)服務(wù)，我們始終認為：好的營銷型網(wǎng)站就是好的業(yè)務(wù)員。我們已成功為企業(yè)單位、個人等客戶提供了網(wǎng)站設(shè)計制作、網(wǎng)站設(shè)計服務(wù)，以良好的商業(yè)信譽，完善的服務(wù)及深厚的技術(shù)力量處于同行領(lǐng)先地位。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文題目：C++創(chuàng)建一棵哈夫曼樹以及輸出其哈夫曼編碼-創(chuàng)新互聯(lián)
標題URL：http://weahome.cn/article/gooec.html