数据结构与算法-构造哈弗曼树【十二】

爱被打了一巴掌 2023-02-22 08:14 23阅读 0赞

### 哈弗曼树的定义 ###

哈佛曼树的定义： 带权路径长度最短的树。

每一个叶子节点有一个权重值，权重值 乘以 路径长度【路径长度指的是根节点到该节点的路径长度】 ，所有叶子节点的 **带权路径长度** 之和最小的树，称之为哈弗曼树，也称之为最优二叉树。

n为所有叶子节点的个数，w为该叶子节点的权重，length©为该叶子节点的路径长度，图来自于维基百科。

![在这里插入图片描述][20200702155056599.png]

给定一组有特定权重值的节点，构造一棵哈弗曼树。 可以用最简单的想法来：权重最大的叶子节点离根节点最近，权重最小的叶子节点离根节点最远。

前景提要： 给定n个具有特定权重的叶子节点。

思路：  
     1，根据`n`个给定的权重值 \{w1, w2, w3 … wn \}，构造`具有n`棵只有根节点的二叉树组成的森林。F = \{ T1, T2, T3…Tn \}, 其中Ti 为只有一个根节点并且权重值为wi的根节点（实际上也是一棵只有根节点的树）。  
     2，在F中选取权重值最小的两个节点，作为左右子树构造一棵新树，这棵树的根节点的权重值为左右子树的权重值之和。  
     3，将森林中的删除第二步合并的两棵树，将新树添加到森林F中。  
     4，重复第二，三步骤，直到森林中只有一棵树为止。

#### 口诀 ####

1，构造森林全是根。  
    2，选用两小造新树。  
    3，删除两小添新人。  
    4，重复2，3剩单根。

这个过程中：

每一次要合并两个节点，到一棵新的树里面，`n`个节点，要合并`n-1`次，直到最后只有 `1`棵树。

一共合并n-1次，会有新的节点`n-1`个，所以有`n`个叶子节点的哈夫曼树，一共有`n + ( n- 1 )`个 也就是 `2n - 1`节点。

并且这`2n-1`个节点中，有`n`个度为`0`的叶子节点，以及`n-1`个度为`2`的节点。

哈弗曼树的节点的度数【儿子节点】个数只会是0 或者 2，不存在度为1的节点。

--------------------

#### 算法实现 - JAVASCRIPT ####

二叉树的节点定义

function TreeNode(val, left, right) { 
      this.val = (val===undefined ? 0 : val)
      this.left = (left===undefined ? null : left)
      this.right = (right===undefined ? null : right)
    }

javascript 算法实现：

// 给定一组权重值
    const contructHaffumanTree = (weightArr) => { 
      if (!weightArr || weightArr.length <= 0) {  return null }
      let n = weightArr.length
    
      // 先对权重进行排序，构造哈夫曼树从权重最小的节点开始
      // 排序之后，依次从数组的头部获取即可。
      // 排序算法有多种，这里使用js默认方法
      const sortedWeightArr = weightArr.sort((num1, num2)=>num1 - num2)
      
    
      // 1， 构造森林
      let forest =  sortedWeightArr.map(v => new TreeNode(v))
    
    
      // 2,3 选取最小权重的两个节点，构造新树添加到森林中，删掉以前的两棵树
      // 合并n-1次，循环n-1次 直到森林中只有一棵树
     for (let i = 1; i < n ; i++) { 
        let minNode1 = forest.shift()
        let minNode2 = forest.shift()
    
        let newNode = new TreeNode()
        newNode.val = minNode1.val +  minNode2.val
        newNode.left = minNode1
        newNode.right = minNode2
        forest.push(newNode); 
        // 为了后续的循环直接获取数组头部的元素（权重值最小的两个节点），这里直接再排一次序
        forest.sort((n1, n2) =>n1.val - n2.val)  
      }
      // 4，森林里只有一颗树
      return forest[0]
    }
    
    
    // test case
    contructHaffumanTree([7,5,2,4])

[资料： 构造哈夫曼树][Link 1]

[20200702155056599.png]: https://img-blog.csdnimg.cn/20200702155056599.png
[Link 1]: https://www.bilibili.com/video/av35817147