注：文章内容来源于网络，真实性有待确认，请自行甄别。
构造赫夫曼树的算法的问题构造赫夫曼树的算法中，有下面这段程序：f
发表于：2024-10-24 00:00:00浏览：15次
问题描述：构造赫夫曼树的中，有下面这段程序：
for(i=n;i<m;++i)
{
select(HT.HTree,i-1,s1,s2);
//在HT.HTree[0..i-1]当前可选的中选择权值最小的两个结点，其序号分别为s1和s2.
HT.HTree[i].lchild=s1;
HT.HTree[i].rchild=s2;
HT.HTree[i].weight=HT.HTree[s1].weight+HT.HTree[s2].weight;
//取左右子树根结构造赫夫曼树的中，有下面这段程序：
for(i=n;i<m;++i)
{
select(HT.HTree,i-1,s1,s2);
//在HT.HTree[0..i-1]当前可选的中选择权值最小的两个结点，其序号分别为s1和s2.
HT.HTree[i].lchild=s1;
HT.HTree[i].rchild=s2;
HT.HTree[i].weight=HT.HTree[s1].weight+HT.HTree[s2].weight;
//取左右子树根结点权值之和
}
我想问的是：
运行完select(HT.HTree,i-1,s1,s2);这句后，s1,s2这两个序号所在的结点还在吗？ 是不是已经删除了？
如果没删除，那下次运行select(HT.HTree,i-1,s1,s2); 这句的时候，最小的两个结点依旧是s1和s2呀．
猜测这两个结点没有被删除（否则lchild和rchild指针都无效了），而是使用了诸如“已被使用”这一类的标签，例如每个结点都带有一个bool变量bUsed，默认值为false, 如果在select中被选中是最小的两个则标记为bUsed=true。
这样在select函数中当前可选的就是那些bUsed的值为false的结点，也即你的描述中提到的“当前可选的”结点。
当然，具体代码的实现细节不知道，感觉上应该是类似的实现策略。
栏目分类全部>