我在从霍夫曼树中正确弹出时遇到问题。现在我正在创建一个基于 minheap 的 Huffman 树,我想做以下事情:
如果我们假设 A 和 B 是两个不同的子树,我会说如果 A 的频率小于 B 的频率,则 A 将首先弹出。如果它们具有相同的频率,那么我会在 A 的任何叶节点中找到 ASCII 值中的最小字符。然后我会看看 A 中最小的字符叶节点是否小于 B 的任何叶节点中的那个。如果是这样,我会在 B 之前弹出 A。如果不是,我会弹出 B。 <-这就是我遇到的麻烦。
例如:
假设我输入:
eeffgghh\n (every letter except for \n's frequency which is 1 is 2)
进入我的霍夫曼树。然后我的树看起来像这样:
9
/ \
5 4
/ \ / \
3 h g f
/\
e \n
下面是我从 Huffman minheap 中弹出的尝试。我在比较两个字母的频率是否相同时遇到了麻烦。如果有人可以提供帮助,那就太好了。谢谢!
void minHeap::heapDown(int index)
{
HuffmanNode *t = new HuffmanNode();
if(arr[index]->getFreq() == arr[left]->getFreq() || arr[index]->getFreq() == arr[right]->getFreq()) //arr is an array of HeapNodes
{
if(arr[left]->getLetter() < arr[right]->getLetter())
{
t = arr[index]; //equals operator is overloaded for swapping
arr[index] = arr[left];
arr[left] = t;
heapDown(left);
}
else
{
t = arr[index];
arr[index] = arr[right];
arr[right] = t;
heapDown(right);
}
}
if(arr[index]->getFreq() > arr[left]->getFreq() || arr[index]->getFreq() > arr[right]->getFreq())
{
if(arr[left]->getFreq() < arr[right]->getFreq())
{
t = arr[index];
arr[index] = arr[left];
arr[left] = t;
heapDown(left);
}
else
{
t = arr[index];
arr[index] = arr[right];
arr[right] = t;
heapDown(right);
}//else
}//if
}