树和二叉树
树
树（Tree）是
- 有且仅有一个称之为根的结点
- 除根结点外的其余结点可分为
个互不相交的有限集 ，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）
例如，上图中，b 是有 13 个结点的树，其中 B 是根，其余结点分成 3 个互不相交的子集：
基本术语
- 结点：树中的一个独立单元。包含一个数据元素及若干指向其子树的分支，如上图 b 中的 B、C、D、E 等。
- 结点的度：结点拥有的子树数称为结点的度。例如，B 的度是 3，D 的度是 1，G 的度是 0。
- 树的度：树内各结点度的最大值。b 所示的树的度为 3。
- 叶子：度为 0 的结点。也称为终端结点。结点 L、M、G、H、N、J、K 都是叶子。
- 非终端结点：度不为 0 的结点。除根结点之外，非终端结点也称为内部结点。结点 B、C、D、E、F、I 都是非终端结点，其中除了 B 外的结点也称为内部结点。
- 双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。例如，C 的双亲为 B，C 的孩子有 F 和 G。
- 兄弟：同一个双亲的孩子之间互称兄弟。例如，I、J、K 互为兄弟。
- 祖先：从根到该结点所经分支上的所有结点。例如，N 的祖先为 B、E、I。
- 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如 C 的子孙为 F、G、L、M。
- 层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层。树中任一结点的层次等于其双亲结点的层次加 1。
- 堂兄弟：双亲在同一层的结点互为堂兄弟。例如，结点 H 与 F、G、I、J、K 互为堂兄弟。
- 树的深度：树中结点的最大层次称为树的深度或高度。b 所示的树的深度为 4。
- 有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
- 森林：是
棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以用森林和树相互递归的定义来描述树。
就逻辑结构而言，任何一棵树都是一个二元组
存储结构
树的存储结构有多种形式。这里介绍 3 种常用的表示方法。
双亲表示法
以一组连续的存储单元存储树的结点，每个结点除了数据域 data 外，还有一个 parent 域用于指示其双亲结点的位置。
在这种结构下，查询结点的双亲很方便，但查询结点的孩子需要遍历整个结构。
孩子表示法
由于树中每个结点可能有多棵子树，则可用多重链表，即每个结点设置多个指针域，每个指针指向一颗子树的根结点。结点格式如下图。
若采用第一种结点格式，则多重链表中的结点是同构的，其中
若采用第二种结点格式，则多重链表中的结点是不同构的，其中
另一种办法是，把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表做存储结构，则
与双亲表示法相反，此种结构便于查询孩子，但不便于查询双亲。
我们可以把这两种方法结合起来，即将双亲表示和孩子链表合在一起。
孩子兄弟法
又称二叉树表示法，或二叉链表表示法，即以二叉链表做树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子和下一个兄弟结点，分别命名为 firstchild 域和 nextsibling 域，结点形式如下图。
这种结构下，若要访问结点 X 的第
这种存储结构的优点是它和二叉树的二叉链表表示完全一样，便于将一般的树结构转换成二叉树进行处理，利用二叉树的算法来实现对树的操作。因此孩子兄弟法是应用较为普遍的一种树的存储表示方法。
二叉树
二叉树（Binary Tree） 是
- 有且仅有一个称之为根的结点
- 除根结点外的其余结点可分为两个互不相交的子集
和 ，分别称为 的左子树和右子树，且 和 本身又都是二叉树
二叉树与树的区别：
- 二叉树每个结点至多只有两颗子树（即二叉树中不存在度大于 2 的结点）
- 二叉树的子树有左右之分，其次序不能任意颠倒
二叉树的递归定义表明二叉树或为空，或是由一个根结点加上两颗分别称为左子树和右子树的、互不相交的二叉树组成。由于这两颗子树也是二叉树，则由二叉树的定义，它们也可以是空树。
性质
- 在二叉树的第
层上至多有 个结点
证明：利用归纳法易证得此性质。
假设对所有的
由归纳假设：第
- 深度为
的二叉树至多有 个结点
证明：由性质 1 可见，深度为
- 对任何一颗二叉树
，如果其终端结点数为 ，度为 2 的结点数为 ，则
证明：设
再看二叉树中的分支数。除了根结点外，其余结点都有一个分支进入，设
结合上述式子可得
满二叉树
深度为
特点：每一层上的结点数都是最大结点数。
完全二叉树
对满二叉树的结点进行编号，约定编号从根结点起，自上而下，从左至右。
深度为
特点：
- 叶子结点只可能在层次最大的两层上出现
- 对任一结点，若其右分支下的子孙的最大层次为
，则其左分支下的子孙的最大层次必为 或
性质
- 具有
个结点的完全二叉树的深度为
证明：假设深度为
- 如果对一颗有
个结点的深度为 的完全二叉树的结点按层序编号（从第 层到 层，每层从左到右），则对任一结点 ，有
- 如果
，则结点 是树的根，无双亲；如果 ，则其双亲 是结点 - 如果
，则结点 无左孩子（结点 为叶子结点）；否则其左孩子 是结点 - 如果
，则结点 无右孩子；否则其右孩子 是结点
存储结构
顺序存储
顺序存储结构使用一组地址连续的存储单元来存储元素，为了能够在存储结构中反映结点之间的逻辑关系，必须将二叉树中的结点按一定的规律放置。
对于完全二叉树，只要从根起按层序存储即可，依次自上而下、从左到右存储结点，即将完全二叉树上编号为
如下图的完全二叉树
对应的顺序存储结构为
对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组对应的位置中。
如下图的二叉树
对应的顺序存储结构为
从上图可见，这种顺序存储结构仅适用于完全二叉树。因为，在最坏的情况下，一个深度为
链式存储
二叉树的链表中的结点至少包含 3 个域：数据域和左、右指针域。有时，为了便于找到结点的双亲，还可在结点结构中增加一个指向其双亲结点的指针域。利用这两种结点结构得到的存储结构分别称之为二叉链表和三叉链表。容易证得，在含有
在不同的存储结构中，实现二叉树的操作方法也不同。因此，在具体应用中采用什么存储结构，除根据二叉树的形态之外还应考虑需要进行何种操作。
遍历二叉树
遍历二叉树（traversing binary tree）是指按某条搜索路径遍历树中每个结点，使得每个结点都能被且仅被访问一次。遍历是二叉树最基本的操作，也是二叉树其它各种操作的基础，遍历的实质是对二叉树进行线性化的过程，遍历的结果是将非线性结构的树中结点排成一个线性序列。
二叉树由 3 个基本单元组成：根结点、左子树和右子树。因此，若能一次遍历这三个部分，便是遍历了整个二叉树。使用 L、D、R 分别表示遍历左子树、访问根结点和遍历右子树，则有 DLR、LDR、LRD、DRL、RDL、RLD 这 6 种遍历二叉树的方式。若限定先左后右，则只有前 3 种情况，分别称之为先序遍历、中序遍历和后序遍历。
先序遍历
若二叉树为空，则空操作；否则
- 访问根结点
- 先序遍历左子树
- 先序遍历右子树
中序遍历
若二叉树为空，则空操作；否则
- 中序遍历左子树
- 访问根结点
- 中序遍历右子树
后序遍历
若二叉树为空，则空操作；否则
- 后序遍历左子树
- 后序遍历右子树
- 访问根结点
例子
表示表达式
先序遍历：
中序遍历：
后序遍历：
从表达式来看，上述 3 个序列正好是表达式的前缀表示（波兰式）、中缀表示和后缀表示（逆波兰式）。
算法如下：
export function preorderTraverse<T>(
tree?: BiTNode<T>,
pre: (T | undefined)[] = []
) {
if (tree) {
pre.push(tree.data)
preorderTraverse(tree.lchild, pre)
preorderTraverse(tree.rchild, pre)
}
return pre
}export function inorderTraverse<T>(
tree?: BiTNode<T>,
pre: (T | undefined)[] = []
) {
if (tree) {
inorderTraverse(tree.lchild, pre)
pre.push(tree.data)
inorderTraverse(tree.rchild, pre)
}
return pre
}export function postorderTraverse<T>(
tree?: BiTNode<T>,
pre: (T | undefined)[] = []
) {
if (tree) {
postorderTraverse(tree.lchild, pre)
postorderTraverse(tree.rchild, pre)
pre.push(tree.data)
}
return pre
}从上述二叉树遍历的定义可知，3 种遍历算法不同处仅在于访问根结点和遍历左、右子树的先后顺序。
我们还可以使用栈将递归算法改写成非递归算法：
export function preorderTraverse<T>(tree?: BiTNode<T>) {
const result: (T | undefined)[] = []
const stack: BiTNode<T>[] = []
let root = tree
while (root || stack.length) {
if (root) {
result.push(root.data)
stack.push(root)
root = root.lchild
} else {
root = stack.pop()?.rchild
}
}
return result
}export function inorderTraverse<T>(tree?: BiTNode<T>) {
const result: (T | undefined)[] = []
const stack: BiTNode<T>[] = []
let root = tree
let top: BiTNode<T>
while (root || stack.length) {
if (root) {
stack.push(root)
root = root.lchild
} else {
top = stack.pop()!
result.push(top.data)
root = top.rchild
}
}
return result
}export function postorderTraverse<T>(tree?: BiTNode<T>) {
const result: (T | undefined)[] = []
const stack: BiTNode<T>[] = []
let root = tree
let top: BiTNode<T>
while (root || stack.length) {
if (root) {
stack.push(root)
root = root.lchild
} else {
top = stack.pop()!
root = top.rchild
if (!root || root.data === result.at(-1)) {
root = undefined
result.push(top.data)
} else {
stack.push(top)
}
}
}
return result
}无论是递归还是非递归算法，因为每个结点被访问一次，则不论按哪一种次序进行遍历，对含有
除了上述 3 种遍历方式外，还有一种按层次遍历的方式，这种方式按照自上而下，从左到右的顺序遍历。层次遍历不是一个递归过程，算法的实现可以借助队列，此处不做详细讨论。
根据遍历序列确定二叉树
由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一确定一颗二叉树。
根据定义，二叉树的先序遍历是先访问根结点，其次再按先序遍历遍历根结点的左子树，最后按先序遍历遍历根结点的右子树。也就是说，在先序序列中，第一个结点是二叉树的根结点。另外，中序遍历是先遍历左子树，然后访问根结点，最后再遍历右子树。这样，根结点在中序序列中必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，后一个是右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。这样，就确定了二叉树的三个结点。同时，左子树和右子树的根结点又可以分别把左子序列和右子序列划分成两个子序列，如此递归下去，当取尽先序序列中的结点时，便可以得到一颗二叉树。
同理，由二叉树的后序序列和中序序列也可唯一确定一颗二叉树。因为，依据后序遍历和中序遍历的定义，后序序列的最后一个结点，就如同先序序列的第一个结点一样，可将中序序列分成两个子序列，分别为这个结点左子树的中序序列和右子树的中序序列，再拿出后序序列的倒数第二个结点，并继续分割中序序列，如此递归下去，当倒着取尽后序序列中的结点时，便可以得到一颗二叉树。
例子
已知一颗二叉树的中序序列和后序序列分别是 BDCEAFHG 和 DECBHGFA，请画出这颗二叉树。
- 由后序遍历特征，根结点必在后序序列尾部，所以根结点是 A
- 由中序遍历特征，根结点必在其中间，而且其左边必全部是左子树子孙（BDCE），其右边必全部是右子树子孙（FHG）
- 根据后序中的 DECB 子树可确定 B 为 A 的左孩子，根据 HGF 可确定 F 为 A 的右孩子；依此类推，可以唯一确定一颗二叉树
二叉树遍历算法的应用
创建二叉链表
这里我们使用先序遍历的方式建立二叉链表。算法如下：
export function createBiTree<T>(data: T[]) {
const stack: BiTNode<T>[] = []
let tree: BiTNode<T> | undefined
let root = tree
let prop: 'lchild' | 'rchild' = 'lchild'
data.forEach((e) => {
if (e !== null) {
if (tree) {
tree = tree[prop] = new BiTNode(e)
} else {
root = tree = new BiTNode(e)
}
stack.push(tree)
prop = 'lchild'
} else {
if (stack.length) {
tree = stack.pop()
}
prop = 'rchild'
}
})
return root
}复制二叉树
这里我们使用先序遍历的方式复制二叉树。算法如下：
export function copy<T>(tree?: BiTNode<T>) {
if (!tree) return
const root = new BiTNode(tree.data)
root.lchild = copy(tree.lchild)
root.rchild = copy(tree.rchild)
return root
}计算二叉树深度
二叉树的深度为树中结点的最大层次，即左右子树深度的较大者，空树为 0。算法如下：
export function depth<T>(tree?: BiTNode<T>): number {
if (!tree) return 0
const m = depth(tree.lchild)
const n = depth(tree.rchild)
return m > n ? m + 1 : n + 1
}统计二叉树中结点个数
如果是空树，则结点个数为 0；否则，结点个数为左子树的结点数加右子树的结点数加根结点。算法如下：
export function count<T>(tree?: BiTNode<T>): number {
if (!tree) return 0
return count(tree.lchild) + count(tree.rchild) + 1
}线索二叉树
基本概念
遍历二叉树实质上是对一个非线性结构进行线性化操作，使每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。
但是，当以二叉链表作为存储结构时，只能找到结点的左右孩子信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只有在遍历的过程中才能得到，为此引入线索二叉树来保存这些信息。
虽然可以在每个结点中增加两个指针域来存放在遍历时得到的有关前驱和后继信息，但这样做使得结构的存储密度大大降低。由于有
试做如下规定：若结点有左子树，则其 lchild 域指示其左孩子，否则令 lchild 域指示其前驱；若结点有右子树，则其 rchild 域指示其右孩子，否则令 rchild 域指示其后继。为了避免混淆，尚需改变结点结构，增加两个标志域。如下图所示：
使用此种存储结构的二叉链表叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称之为线索二叉树（Threaded Binary Tree）。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。
构造线索二叉树
线索二叉树构造的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。对二叉树使用不同遍历方法可以得到不同的线索二叉树，包括先序线索二叉树、中序线索二叉树和后序线索二叉树。
在这里我们使用中序遍历构造线索二叉树。为了方便，我们在链表上添加一个头结点，令其 lchild 指向根结点，rchild 指向中序序列的最后一个结点；同时，令序列中第一个结点的 lchild 和最后一个结点的 rchild 均指向头结点。这样，我们既可以从第一个结点顺后继进行遍历，也可以从最后一个结点顺前驱进行遍历。
算法如下：
export class ThreadBiTNode<T> extends BiTNode<T> {
/**
*
* @param data
* @param lchild
* @param rchild
* @param ltag 0: 指示结点的左孩子 1: 指示结点的前驱
* @param rtag 0: 指示结点的右孩子 1: 指示结点的后继
*/
constructor(
data: T,
public lchild?: ThreadBiTNode<T>,
public rchild?: ThreadBiTNode<T>,
public ltag?: 0 | 1,
public rtag?: 0 | 1
) {
super(data, lchild, rchild)
}
}
let pre: ThreadBiTNode<any>
function _inorderThreading<T>(tree?: BiTNode<T>) {
if (!tree) return
const threadTree = new ThreadBiTNode(tree.data, tree.lchild, tree.rchild)
if (!tree.lchild) {
threadTree.ltag = 1 // 加上左线索
threadTree.lchild = pre // 指向前驱结点
} else {
threadTree.ltag = 0
threadTree.lchild = _inorderThreading(tree.lchild)
}
if (!pre.rchild) {
pre.rtag = 1 // 加上右线索
pre.rchild = threadTree // 指向后继结点
} else {
pre.rtag = 0
}
pre = threadTree
threadTree.rchild = _inorderThreading(tree.rchild)
return threadTree
}
export function inorderThreading<T>(tree?: BiTNode<T>) {
const headNode = new ThreadBiTNode<T | null>(null)
headNode.ltag = 0 // 头结点有左孩子，若树非空，则左孩子为树根结点
headNode.rtag = 1 // 头结点右孩子为右线索
if (tree) {
pre = headNode
headNode.lchild = _inorderThreading(tree)
pre.rchild = headNode // 上述算法结束后，pre 为最右结点，pre 右线索指向头结点
pre.rtag = 1
headNode.rchild = pre
}
return headNode
}遍历线索二叉树
由于有了前驱和后继信息，线索二叉树的遍历和在指定次序下查找结点的前驱和后继算法都变得简单。因此，若需经常查找结点在所遍历线性序列中的前驱和后继，则采用线索链表作为存储结构。
下面我介绍遍历中序线索二叉树的算法，至于先序线索二叉树和后序线索二叉树，读者可以自行实现。
/**
* 遍历中序线索二叉树
* @param tree 带有头结点的中序线索二叉树
*/
export function inorderTraverseThread<T>(tree: ThreadBiTNode<T>) {
let p = tree.lchild // 指向根结点
const result: (T | undefined)[] = []
while (p !== tree) {
while (p?.ltag === 0) {
p = p.lchild
}
result.push(p?.data)
while (p?.rtag === 1 && p.rchild !== tree) {
p = p.rchild
result.push(p?.data)
}
p = p?.rchild
}
return result
}该算法时间复杂度为
树和森林
森林与二叉树的转换
从树的孩子兄弟法可知，任何一棵和树对应的二叉树，其根结点的右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。如下图所示。
这个一一对应的关系说明森林或树与二叉树可以相互转换。
森林转换成二叉树
如果
- 若
为空，则 为空树 - 若
非空，则 的根 root 即为森林中第一棵树的根 ； 的左子树 是从 中根结点的子森林 转换而成的二叉树；其右子树 是从森林 转换而成的二叉树
二叉树转换成森林
如果
- 若
为空，则 为空 - 若
非空，则 中第一棵树 的根 即为二叉树 的根 root； 中根结点的子树森林 是由 的左子树 转换而成的森林； 中除 之外其余树组成的森林 是由 的右子树 转换而成的森林
从上述递归定义容易写出相互转换的递归算法。同时，森林和树的操作亦可转换成二叉树的操作来实现。
树和森林的遍历
树的遍历
由树结构的定义可引出两种次序遍历树的方法：
- 先根遍历：先访问树的根结点，然后依次先根遍历根的每颗子树
- 后根遍历：先依次后根遍历每棵子树，然后访问根结点
例如，对上图进行先根遍历，可得树的先根序列：RADEBCFGHK
若对此树进行后根遍历，则得树的后根序列：DEABGHKFCR
按照森林和树相互递归的定义，可推出森林的两种遍历方法：先序遍历和中序遍历。
森林的遍历
先序遍历
若森林非空，则可按如下规则遍历：
- 访问森林中第一棵树的根结点
- 先序遍历第一棵树的根结点的子树森林
- 先序遍历除第一棵树之外的剩余的树构成的森林
中序遍历
- 中序遍历森林中第一棵树的根结点的子树森林
- 访问第一棵树的根结点
- 中序遍历除第一棵树之外的剩余的树构成的森林
若对上图所示森林进行先序遍历，可得先序序列：ABCDEFGHIJ
若进行中序遍历，可得中序序列：BCDAFEHJIG
由森林与二叉树之间转换的规则可知，当森林转换成二叉树时，其第一棵树的子树森林转换成左子树，剩余树的森林转换成右子树，则上述森林的先序和中序遍历即为其对应的二叉树的先序和中序遍历。
由此可见，当以二叉链表做树的存储结构时，树的先根遍历和后根遍历可用二叉树的先序遍历和中序遍历实现。
哈夫曼树及其应用
基本概念
哈夫曼（Huffman）树又称最优树，是一类带权路径长度最短的树，在实际中有广泛的用途。哈夫曼树的定义，涉及路径、路径长度、权等概念，下面给出这些概念的定义。
- 路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径
- 路径长度：路径上的分支数目称作路径长度
- 树的路径长度：从树根到每一结点的路径长度之和
- 权：赋予某个实体的一个量，是对实体屙某个或某些属性的数值化描述。在数据结构中，实体有结点（元素）和边（关系）两大类，所以对应有结点权和边权。结点权或边权具体代表什么意义，由具体情况决定。如果在一颗树中的结点上带有权值，则对应的就有带权树等概念
- 结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积
- 树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作
- 哈夫曼树：假设有
个权值 ，可以构造一颗含有 个叶子结点的二叉树，每个叶子结点的权为 ，则其中带权路径长度 最小的二叉树称作最优二叉树或哈夫曼树
如上图所示的 3 棵二叉树，都含 4 个叶子结点 a、b、c、d，分别带权 7、5、2、4，它们的带权路径长度如上图所示，其中（c）树的最小。可以验证，它恰为哈夫曼树。
从上面的例子中，我们可以看出哈夫曼树的特点是权值越大的结点离根结点越近。根据这个特点，哈夫曼最早给出了一个构造哈夫曼树的方法，称哈夫曼算法。
构造算法
构造过程
- 根据给定的
个权值 ，构造 棵只有根结点的二叉树，这 棵二叉树构成森林 - 在森林
中选取两棵根结点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根结点的权值为其左右子树根结点的权值之和 - 在森林
中删除这两棵树，同时将得到的新二叉树加入 中 - 重复 2 和 3，直到
只含一棵树为止。这棵树便是哈夫曼树
过程如下图：
在构造哈夫曼树时，首先选择权小的，这样保证权大的离根较近，这样一来，在计算树的带权路径长度时，自然会得到最小带权路径长度，这种生成算法是一种典型的贪心法。
实现
哈夫曼树是一种二叉树，这意味着我们可以使用之前介绍过的二叉树存储方法，由于哈夫曼树中没有度为 1 的结点，则一棵有
为了实现方便，数组的 0 号单元不使用，从 1 号单元开始使用，所以数组的大小为
export class HTNode {
constructor(
public weight: number,
public parent: number,
public lchild: number,
public rchild: number
) {}
}
function select(
huffmanTrees: HTNode[],
end: number = huffmanTrees.length
): [number, number] {
let p1 = 0
let p2 = 0
for (let i = 1; i <= end; i++) {
const ele = huffmanTrees[i]
if (ele.parent) continue
if (!p1) {
p1 = i
continue
} else if (!p2) {
p2 = i
continue
}
if (huffmanTrees[p1].weight > huffmanTrees[p2].weight) {
;[p1, p2] = [p2, p1]
}
if (ele.weight < huffmanTrees[p1].weight) {
p2 = p1
p1 = i
} else if (ele.weight < huffmanTrees[p2].weight) {
p2 = i
}
}
return [p1, p2]
}
export function createHuffmanTree(weight: number[]) {
const huffmanTrees: HTNode[] = []
const total = 2 * weight.length - 1 // 结点总数
for (let i = 1; i <= total; i++) {
/**
* 从 1 号单元开始，依次将 1 至 2n-1 所有单元中
* 的双亲、左孩子、右孩子的下标都初始化为 0；对
* 前 n 个单元初始化权值
*/
huffmanTrees[i] = new HTNode(weight[i - 1] ?? 0, 0, 0, 0)
}
for (let i = weight.length + 1; i <= total; i++) {
// 从当前森林中选择双亲为 0 且权值最小的两个树根结点
const [p1, p2] = select(huffmanTrees, i - 1)
// 将 i 指向的结点作为这两棵子树的根结点
huffmanTrees[p1].parent = huffmanTrees[p2].parent = i
huffmanTrees[i].lchild = p1
huffmanTrees[i].rchild = p2
huffmanTrees[i].weight = huffmanTrees[p1].weight + huffmanTrees[p2].weight
}
return huffmanTrees
}