C++霍夫曼树和指针

Question

我正在创建一个霍夫曼树,为此我开始制作一个Min Heap.堆已设置并按文档中的频率对值进行排序,但是当我尝试开始创建树时出现问题.

我正在从堆中弹出前两个项目并在它们上面放置一个节点并重新插入堆中.堆是基于数组的,因此它不会触及节点的*left和*right指针.当堆只有一个节点时,它的左右节点指针都是空的,所以我相信它可能是我指针的问题......？我是java新手,因为我犯了愚蠢的错误.

 while(theHeap.getheapSize() > 1)
    {
        Node top;
        Node *min1=new Node(theHeap.topandPop());
        Node *min2=new Node(theHeap.topandPop());
        top.left=min1;
        top.right=min2;
        top.freq=min1->freq+min2->freq;
        theHeap.insert(top);
    }
    Node r=theHeap.topAndPop(); //null pointers for left and right children

--------------------------------------
    //code for heap.  arr is in the header file is Node *arr;

void Heap::insert(Node c)
{
    if (heapSize != arrSize)
    {
        heapSize=heapSize+1;
        arr[heapSize - 1] = c; //does this call copy constructor???
        percolateUp(heapSize - 1);
    }
}
void Heap::percolateUp(int nodeIndex) {

    int parentIndex;
    Node tmp;
    if (nodeIndex != 0)
    {
        parentIndex = getParentPos(nodeIndex);
        if (arr[parentIndex].freq > arr[nodeIndex].freq)
        {
            tmp = arr[parentIndex];
            arr[parentIndex] = arr[nodeIndex];
            arr[nodeIndex] = tmp;
            percolateUp(parentIndex);

        }
    }
}

Answer 1

首先，我建议不要混合实例和指针，如果您选择一个，您的任务会简单得多。在这种情况下，我认为在堆中存储指向 Node 的指针而不是实例是合适的，额外的好处是指针的行为更像你习惯的 Java，无需担心复制构造和赋值。您只需要记住删除它们（与 Java 不同），这可以在堆的 dtor 中完成。

其次，回答代码注释中的问题：不，在 Heap::insert() 中不会调用复制构造函数，而是调用赋值运算符。这是否是一个问题取决于您的 Node 类是什么样的。