簡介

昨天剛拿到的需求，要求用二叉樹設計一個huffman算法，主要用于壓縮數(shù)據(jù)，就簡單的用javascript實現(xiàn)了一個，在實現(xiàn)的過程中，畫樹進行的很順利，但在測試編解碼的時候出現(xiàn)了一些問題，也是自己對huffman算法的理解錯誤，好在及時改正。

算法實現(xiàn)

對huffman算法實現(xiàn)原理如果不了解的話最好自己去研究一下在看，否則可能有些地方看不懂，在這不做具體說明。
廢話到此為止了，直接上代碼，如果認為對自己有用的，請點個贊，謝謝

/**
 * 定義一個節(jié)點
 *
 * @param weight 權值
 * @param char 字符
 * */
function node(weight, char) {

    this.left = 0;//左孩子
    this.right = 0;//右孩子
    this.parent = 0;//父節(jié)點
    this.weight = weight || 0;//字符的權值
    this.char = char || '';
}

let nodes = [];
let selectStart = 0;

//
function prepareNodes() {

    const arr = [1, 2, 3, 4, 5];
    const arrChar = ['a', 'b', 'c', 'd', 'e'];
    arr.forEach(function (value, index) {
        nodes.push(new node(value, arrChar[index]));
    })
    return nodes;
}

function buildHTree(nodes) {

    selectStart = 0;
    // const nodes = prepareNodes();
    let left,//左孩子索引
        right;//右孩子

    let n = nodes.length;//外部節(jié)點數(shù)量
    let m = 2 * n - 1;//內部節(jié)點+外部節(jié)點總數(shù)量
    let HT = [];//存儲節(jié)點的對象

    // console.log('n = ',n,'m = ',m,'nodes = ',nodes);
    for (let i = 0; i < m; i++) {//給所有節(jié)點一個默認權值
        HT.push(new node(0, ''));
    }
    //把葉子節(jié)點的值賦值給HT[0,n-1];
    for (let i = 0; i < n; i++) {
        HT[i].char = nodes[i].char;
        HT[i].weight = nodes[i].weight;
    }
    // console.log('HT = ',HT);
    //計算內部節(jié)點的值
    for (let i = n; i < m; i++) {
        left = selectMinWeightNode(HT, i, 0);//獲取HT中權值最小的node下標
        right = selectMinWeightNode(HT, i, 1);
        // console.log('left = ',left,'right = ',right);
        HT[i].left = left || 0;
        HT[i].right = right || 0;
        HT[i].weight = HT[left].weight + HT[right].weight; //計算當前節(jié)點權值

        HT[left].parent = i;
        HT[right].parent = i;

        selectStart += 2;
    }
    return HT;
}

/**
 * 返回權值排名為rank的節(jié)點在HT中的下標（權值從小到大排列）
 *
 * @param HT 所有節(jié)點對象
 * @param rang 處理的節(jié)點范圍
 * @rank left/right*/
function selectMinWeightNode(HT, rang, rank) {

    let copyNodes = [];

    for (let i = 0; i < rang; i++) {
        copyNodes.push(HT[i])
    }
    //sort  小->大
    copyNodes.sort((a, b) => a.weight - b.weight);
    //從未參與合成的節(jié)點中選出最小的值
    const targetNode = copyNodes[rank + selectStart];
    // console.log(targetNode);
    for (let i = 0; i < HT.length; i++) {
        if (targetNode === HT[i]) {
            return i;
        }
    }
    return null;
}


function huffmanCode(char, bit) {
    this.char = char;
    this.bit = bit;
}

/**
 * huffman編碼
 *
 * @param HT huffman樹
 * @param nodes 待編碼數(shù)據(jù)*/
function encode(HT, nodes) {

    let HC = [];
    let HCStr = '';
    let bit = '';
    for (let i = 0; i < nodes.length; i++) {//遍歷葉子節(jié)點
        for (let j = 0; j < HT.length; j++) {
            bit = '';
            let char = nodes[i];
            if (HT[j].char === char) {
                let nodeIndex = j;
                while (HT[nodeIndex].parent !== 0) {
                    let parentIndex = HT[nodeIndex].parent;
                    if (HT[parentIndex].left === nodeIndex) {
                        bit = '0' + bit;
                    } else {
                        bit = '1' + bit;
                    }
                    nodeIndex = parentIndex;
                }
                const code = new huffmanCode(HT[j].char, bit);
                HC.push(code);
                HCStr = HCStr+code.bit;
                break;
            }
        }
    }
    console.log(HC);
    return HCStr;
}

/**
 * huffman解碼
 *
 * @param HT huffman樹
 * @param ecode*/
function decode(HT, ecode) {

    let str = '';
    const bit = ecode;
    let nodeIndex = HT.length - 1;
    //遍歷bit 從根節(jié)點開始遍歷
    for (const c of bit) {
        if (c === '1') {//證明有右節(jié)點
            nodeIndex = HT[nodeIndex].right;
        } else {
            nodeIndex = HT[nodeIndex].left;
        }
        if (HT[nodeIndex].left === 0 && HT[nodeIndex].right === 0) {
            str += HT[nodeIndex].char;
            nodeIndex = HT.length - 1;
        }
    }
    return str;
}


function main() {

    const nodes = prepareNodes();//數(shù)據(jù)準備
    const HT = buildHTree(nodes);//建樹
    const a = encode(HT,'abcdeaabcdddddbe');//編碼
    // const a = decode(HT, '01001100101101001001100101010011');//解碼
    console.log(a);
}

main();

測試結果

01001100101101001001100101010101001111
[ huffmanCode { char: 'a', bit: '010' },
  huffmanCode { char: 'b', bit: '011' },
  huffmanCode { char: 'c', bit: '00' },
  huffmanCode { char: 'd', bit: '10' },
  huffmanCode { char: 'e', bit: '11' },
  huffmanCode { char: 'a', bit: '010' },
  huffmanCode { char: 'a', bit: '010' },
  huffmanCode { char: 'b', bit: '011' },
  huffmanCode { char: 'c', bit: '00' },
  huffmanCode { char: 'd', bit: '10' },
  huffmanCode { char: 'd', bit: '10' },
  huffmanCode { char: 'd', bit: '10' },
  huffmanCode { char: 'd', bit: '10' },
  huffmanCode { char: 'd', bit: '10' },
  huffmanCode { char: 'b', bit: '011' },
  huffmanCode { char: 'e', bit: '11' } ]
?  service-mqtt-backup git:(master) ? node huffman.js
 010 011 00 10 11 010 010 011 00 10 10 10 10 10 011 11
?  service-mqtt-backup git:(master) ?