2020-04-02

Essay

24 分钟读完 (大约 3653 个字)

树、森林与二叉树之间的转换

本章我们主要来看一下树、森林和二叉树之间的相互转换以及赫夫曼树的相关概念

普通树转换为二叉树

我们借助图片来进行了解，首先下图是一颗普通的树，它有三个结点，所以明显不是二叉树

如果将其转换成相应的二叉树分为两个步骤

在树中所有的兄弟结点之间加一连线
对每个结点，除了保留与其长子的连线外，去掉该结点与其他孩子的连线

所以我们首先执行『在兄弟结点之间添加连线』

然后在去除『非长子外』的连线

最后，我们在稍微调整一下位置，就可以得出我们想要的二叉树

总结一下，基本的步骤如下

加线，在所有兄弟结点之间加一条连线
去线，对树中每个结点，只保留它与第一孩子结点的连线，删除它与其他孩子结点之间的连线
层次调整，以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明

森林转换为二叉树

同样的还是借助图片来进行了解，首先下图是三颗普通的树，三棵树构造在一起就成了一个森林

如果将其转换成相应的二叉树分为两个步骤

先将森林中的每棵树变为二叉树
再将各二叉树的根结点视为兄弟从左到右连在一起，就形成了一颗二叉树

所以我们首先将森林中的每棵树变为二叉树，方式和我们之前实现的方式是一致的

然后将它们的『根结点』依次连在一起

最后老规矩，在稍微调整一下位置

总结一下，基本的步骤如下

把每棵树转换为二叉树
第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来

二叉树转换为树、森林

二叉树转换为普通树本质上就是之前的逆过程，步骤也就是反过来做而已，判断一棵二叉树能够转换成一棵树还是森林，标准很简单，那就是『只要看这棵二叉树的根结点有没有右孩子，有的话就是森林，没有的话就是一棵树』，如下，是一个二叉树

第一步，若结点 x 是其双亲 y 的左孩子，则把 x 的右孩子，右孩子的右孩子等等等等，依次都与 y 用连连连接起来，如下

第二步，去掉所有双亲到右孩子之间到连线（也就是之前到逆向）

最后老规矩，调整一下，就变成了我们之前的森林

树与森林的遍历

简单来说，树的遍历分为两种方式，一种是先根遍历，另一种是后根遍历

先根遍历，先访问树的根结点，然后再依次先根遍历根的每棵子树
后根遍历，先依次遍历每棵子树，然后再访问根结点

比如下面这棵树

我们按照两种遍历方式如下

先根遍历结果为 A ==> B ==> E ==> F ==> C ==> G ==> D ==> H ==> I ==> J
后根遍历结果为 E ==> F ==> B ==> G ==> C ==> H ==> I ==> J ==> D ==> A

相对于森林的遍历也分为前序遍历和后序遍历，其实就是按照树的先根遍历和后根遍历依次访问森林的每一棵树，这里有一个需要注意的地方，注意比较下面两个图，前面一个是一棵树，而后面那颗则是树转换为二叉树以后的模样

仔细观察我们可以发现

树、森林的前根（序）遍历和二叉树的前序遍历结果相同
树、森林的后根（序）遍历和二叉树的中序遍历结果相同

这样一来，我们就可以将对树和森林遍历这种复杂问题转换为一种相对比较简单的处理方式

赫夫曼树

在数据膨胀、信息爆炸的今天，数据压缩的意义不言而喻，谈到数据压缩，就不能不提赫夫曼（Huffman）编码，赫夫曼编码是首个实用的压缩编码方案，即使在今天的许多知名压缩算法里，依然可以见到赫夫曼编码的影子

另外，在数据通信中，用二进制给每个字符进行编码时不得不面对的一个问题是如何使电文总长最短且不产生二义性，根据字符出现频率，利用赫夫曼编码可以构造出一种不等长的二进制，使编码后的电文长度最短，且保证不产生二义性

关于赫夫曼编码的内容会在最后进行介绍，在此之前，我们先来了解一下什么是赫夫曼树，先来看下面这个计算成绩的示例

if(a < 60)
  printf("不及格")
else if(a < 70)
  printf("及格")
else if(a < 90)
  printf("良好")
else
  printf("优秀")

如果我们将其转化为二叉树的显示方式，是下面这样的

如果按照上面这个流程，比如某个同学的成绩是 85 分的话，则需要进行三次判断才能得出他的成绩，那么我们是否可以稍微的调整一下，让这个判断流程减少一些呢，那就有了下图这样的二叉树

如果我们把判断流程改为像上图这样，那么可以发现效果有比较明显的改善，即我们只需要两次判断就可以得出我们想要的结果，但是我们如何区分到底应该采用哪种判断流程呢？所以这种情况要按实际情况来进行考虑，如下图

可以发现，一个班级的成绩一般来说，达到良好的人数应该占班级总人数的绝大数，有了这个概念以后，我们就可以先把这两棵二叉树简化成『叶子结点带权』的二叉树（树结点间的连线相关的数叫做权，Weight），就是把我们对应分数的所占比例给带入到二叉树当中，结果如下图

针对于上图，我们需要介绍几个基本的概念，如下

结点的路径长度，表示从根结点到该结点的路径上的连接数
树的路径长度，表示树中每个叶子结点的路径长度之和
结点带权路径长度，表示结点的路径长度与结点权值的乘积
树的带权路径长度（WPL，Weighted Path Length），表示的是树中所有叶子结点的带权路径长度之和
如果 WPL 的值越小，说明构造出来的二叉树性能越优

有了这些概念以后，我们就可以来分别计算上诉两种情况

针对第一种情况，它的 WPL 是 5 * 1 + 15 * 2 + 70 * 3 + 10 * 3 = 275

针对第二种情况，它的 WPL 是 10 * 1 + 70 * 2 + 15 * 3 + 5 * 3 = 210

可以发现，针对成绩的判断流程，采取后面的一种方式是更为合理的，那么现在问题来了，因为在一棵树的所有构成形状当中，有各种各样的构成方式，那么我们如才能何构造出最优的赫夫曼树呢（也就是所谓的最优二叉树）？看下面流程

假设有一片森林，如上图所示，有四颗小树（只有一个根结点的树），它们的权也分别标注了出来，然后我们挑选出权值最小的两棵树，小的放左边，大的放右边，然后模拟出一个新的结点作为新二叉树的根，这个新的结点连接着它们两个，如下所示，而新的树的权值为它的左右孩子的权值之和

然后同理操作，继续在剩余树林当中挑选出权值最小的那一颗，按照我们之前的逻辑继续连接，也就是下面这样

依次执行下去，最后的结果如下

这样就形成了一颗赫夫曼树，也就是所谓的最优二叉树，因为如果用其他的方式使用 ABCD 来进行构造所形成的二叉树的 WPL 是不会小于上图当中所实现的方式的

赫夫曼编码

在之前的章节当中，我们已经介绍了赫夫曼树的基本原理和构造方式，而赫夫曼编码可以很有效地压缩数据（通常可以节省 20% ~ 90% 的空间，具体压缩率依赖于数据的特性），下面我们来看几个经常会遇到的名词

定长编码，比如像 ASCII 编码就是定长编码，如果我们有一百个字符，并且都是 A 的话，那么则需要八百位才能存放的下
变长编码，单个编码的长度不一致，可以根据整体出现频率来调节，比如我们要发生的信息都是 A，那么我们可以使用 0 或者 1 来代表 A（因为这个规则我们已经事先约定好了）
前缀码，所谓的前缀码，就是没有任何码字是其他码字的前缀，比如我们的赫夫曼编码（其实就是非前缀码，但是业界之中都叫前缀码）

下面我们来看看如何用代码进行实现，我们首先来定义哈夫曼树节点 HuffmanTreeNode

function HuffmanTreeNode(weight, char) {
  this.l = null              // 左子树
  this.r = null              // 右子树
  this.weight = weight || 0  // 字符的度量值，也就是字符在文本中出现的频次
  this.char = char || ''     // 字符
}

然后我们再来定义一个最小堆 heapMin，主要用于在创建哈夫曼树过程中获取度量值 weight（字符出现的频次）最小的节点

/**
 * 定义一个最小堆对象
 */
var heapMin = function () {
  this.set = []
}

/**
 * 调整堆使其满足最小堆性质
 */
heapMin.prototype.adjust = function (index) {
  let len = this.set.length
  let l = index * 2 + 1
  let r = index * 2 + 2
  let min = index
  let node = null

  if (l <= len - 1 && this.set[min].weight > this.set[l].weight) {
    min = l
  }

  if (r <= len - 1 && this.set[min].weight > this.set[r].weight) {
    min = r
  }

  if (min != index) {
    node = this.set[index];
    this.set[index] = this.set[min]
    this.set[min] = node
    this.adjust(min)
  }
}

/**
 * 插入一个元素
 */
heapMin.prototype.push = function (node) {
  this.set.push(node)
  for (let i = Math.floor(this.set.length / 2); i >= 0; i--) {
    this.adjust(i)
  }
}

/**
 * 移除最小元素
 */
heapMin.prototype.pop = function () {
  let node

  node = this.set.shift()
  this.adjust(0)

  return node
}

/**
 * 获取当前堆大小
 */
heapMin.prototype.size = function () {
  return this.set.length
}

/**
 * 堆是否为空
 */
heapMin.prototype.empty = function () {
  return this.set.length === 0 ? true : false
}

再来定义哈夫曼编码对象 HuffmanCode

function HuffmanCode() {
  this.codeTable = []      // 当前的编码表
  this.huffmanTree = null  // 当前的哈夫曼树
}

生成字符频次最小堆，因为 JavaScript 中的数组实质上是一个散列数组，因此我们可以将字符直接作为键进行索引

/**
 * 统计字符出现的频次，生成字符频次最小堆
 * 
 * options  要进行编码的字符串
 * 返回值    返回一个字符串出现频次的最小堆
 */
HuffmanCode.calcHeap = function (str) {
  let heap = new heapMin()
  let set = []

  for (let i = str.length - 1; i >= 0; i--) {
    if (set[str[i]]) {
      set[str[i]].num++
    } else {
      set[str[i]] = { num: 1, char: str[i] }
    }
  }

  Object.values(set).forEach((value) => {
    heap.push(new HuffmanTreeNode(value.num, value.char))
  })

  return heap
}

创建哈夫曼树

/**
 * 创建哈夫曼树
 *
 * options  要进行哈夫曼编码的字符串
 * return   哈夫曼编码树
 */
HuffmanCode.prototype.createHuffmanTree = function (str) {
  let heap = HuffmanCode.calcHeap(str)

  while (heap.size() > 1) {
    let min1 = heap.pop()
    let min2 = heap.pop()
    let parent = new HuffmanTreeNode(min1.weight + min2.weight, '')

    if (min1.weight < min2.weight) {
      parent.l = min1
      parent.r = min2
    } else {
      parent.l = min2
      parent.r = min1
    }

    heap.push(parent)
  }

  this.huffmanTree = heap.pop()
}

递归哈夫曼树，生成编码表

/**
 * 递归哈夫曼树，生成编码表
 *
 * node  当前要递归的结点
 * arr   编码表
 * code  编码字符串
 */
HuffmanCode.traverseTree = function (node, arr, code) {
  if (node.l !== null && node.r != null) {
    HuffmanCode.traverseTree(node.l, arr, code + '0')
    HuffmanCode.traverseTree(node.r, arr, code + '1')
  }
  arr[node.char] = code
}

哈夫曼编码

/**
 * 哈夫曼编码
 */
HuffmanCode.prototype.encode = function (str) {
  this.createHuffmanTree(str)
  let res = []

  HuffmanCode.traverseTree(this.huffmanTree, this.codeTable, '')

  for (let i = str.length - 1; i >= 0; i--) {
    res.push(this.codeTable[str[i]])
  }

  return res.join('')
}

哈夫曼解码

/**
 * 哈夫曼解码，编码前的字符串
 */
HuffmanCode.prototype.decode = function (str) {
  if (this.huffmanTree === null) {
    console.error('Please create HuffmanTree!');
  }

  let node = this.huffmanTree
  let res = []

  for (let len = str.length, i = 0; i < len; i++) {
    if (str[i] === '0') {
      node = node.l
    } else {
      node = node.r
    }

    if (node.l === null && node.r === null) {
      res.push(node.char)
      node = this.huffmanTree
    }
  }

  return res.join('')
}

测试

let huffmanCode = new HuffmanCode()

huffmanCode.encode('赫夫夫夫夫夫曼编编编编编编编编编编码')
console.log(huffmanCode)

huffmanCode.decode('0011111111111100001010101010010')

# Essay