哈夫曼树构造算法中j<n+i是什么意思

哈夫曼树构造算法中j<n+i是什么意思

先看一下哈夫曼树的构造规则是：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

用数据表示哈夫曼树的话，首先有n个权值点，其初始化就是从 0 到 n -1，先从这里面查找两个权值最小的结点，就是遍历一遍，把最小的值取出来。X1 和X2 要记录着两个权值在哪个位置。
然后把这两个权值加起来的和放回到数组n的位置，然后继续遍历这个数据，现在是从0 到n了，当然原来X1 和X2位置的两个点不用管，已经有父节点了。继续上述过程直到只有一个节点位置。

如 1 2 3 4 5 6构造哈夫曼树，先初始化parent 为 -1
1 2 3 4 5 6
parent -1 -1 -1 -1 -1 -1
先从上述中选取两个权值最小的节点 1 和 2，构造树变为3，放到数组6的位置，原权值序列变为：
1 2 3 4 5 6 3
parent 6 6 -1 -1 -1 -1 -1
继续选取 两个最小权值且parent为-1的点。找到3 和 3，放到数组7的位置，权值序列变为：
1 2 3 4 5 6 3 6
parent 6 6 7 -1 -1 -1 7 -1
继续选取 两个最小权值且parent为-1的点。找到4 和5，到数组8的位置，权值序列变为：
1 2 3 4 5 6 3 6 9
parent 6 6 7 8 8 -1 7 -1 -1
继续选取 两个最小权值且parent为-1的点。找到6 和6，到数组9的位置，权值序列变为：
1 2 3 4 5 6 3 6 9 12
parent 6 6 7 8 8 9 7 9 -1 -1
继续选取 两个最小权值且parent为-1的点。找到9 和12，到数组10的位置，权值序列变为：
1 2 3 4 5 6 3 6 9 12 21
parent 6 6 7 8 8 9 7 9 10 10 -1
结束
所以你说的j < n + i，由于每次选取两个权值的点权值和做为新的节点放在数组后面，当然下一次循环的时候要多一次循环。
X1 和X2要记录下选择两个权值，将其父节点的位置设置为新的权值点位置。