这段代码在原来的程序中出现了死循环,请修改: void ConstructHT(node *HT) //负责构建哈夫曼树,//约定:权重小的子树放父节点的左子枝,大的放右子枝;如果左右子树权重相同,则根据子树根节点在二叉树节点数组中的索引存放,左小右大 { int i, j, m1, m2, x1, x2; for (i = N; i < 2 * N - 1; i++) { m1 = m2 = INT_MAX; x1 = x2 = -1; // 将 x1 和 x2 的初始值设置为 -1,以便在循环中判断是否已找到两个最小权重的节点 for (j = 0; j < i; j++) { if (HT[j].parent == -1) { if (HT[j].weight < m1) { m2 = m1; x2 = x1; m1 = HT[j].weight; x1 = j; } else if (HT[j].weight < m2) { m2 = HT[j].weight; x2 = j; } } } HT[x1].parent = i; HT[x2].parent = i; HT[i].lchild = x1; HT[i].rchild = x2; HT[i].weight = HT[x1].weight + HT[x2].weight; } }
时间: 2024-02-10 15:07:33 浏览: 21
void ConstructHT(node *HT)
{
int i, j, m1, m2, x1, x2;
for (i = N; i < 2 * N - 1; i++)
{
m1 = m2 = INT_MAX;
x1 = x2 = -1;
for (j = 0; j < i; j++)
{
if (HT[j].parent == -1)
{
if (HT[j].weight < m1)
{
m2 = m1;
x2 = x1;
m1 = HT[j].weight;
x1 = j;
}
else if (HT[j].weight < m2)
{
m2 = HT[j].weight;
x2 = j;
}
}
}
HT[x1].parent = i;
HT[x2].parent = i;
HT[i].lchild = x1;
HT[i].rchild = x2;
HT[i].weight = HT[x1].weight + HT[x2].weight;
// 新建的节点的parent为-1,当i为2*N-2时,构建完成哈夫曼树
HT[i].parent = -1;
}
}
在构建哈夫曼树时,需要新建非叶子节点,而新建的节点的parent为-1,当i为2*N-2时,构建完成哈夫曼树。在原来的程序中没有将新建的节点的parent赋值为-1,导致程序出现死循环。以上是修改后的代码。