C++ - 最小堆实现和后序遍历

Question

所以我有这个创建最小堆并根据用户输入插入值的小程序。如果用户说将值 10 更改为 20，则程序应将所有出现的 10 更改为 20，然后堆化。当用户给出打印命令时，程序应该按后序遍历树并打印所有值。所以我写了程序，但是当我打印时它给了我不正确的输出。我在这里做错了什么:

int pArray[500]; 
int i = 0;

//Definition of Node for tree
struct TNode {
    int data; 
    TNode* left;
    TNode* right;
};

void Heapify(TNode* root, TNode* child);

// Function to create a new Node in heap
TNode* GetNewNode(int data) {
    TNode* newNode = new TNode();
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// To insert data in the tree, returns address of root node 
TNode* Insert(TNode* root,int data) {
    if(root == NULL) { // empty tree
        root = GetNewNode(data);
    }
    // if the left child is empty fill that in
    else if(root->left == NULL) {
        root->left = Insert(root->left,data);
    }

    // else, insert in right subtree. 
    else if(root->right == NULL){
        root->right = Insert(root->right,data);
    }

    else {
        root->left = Insert(root->left,data);
    }

    Heapify(root, root->left);
    Heapify(root, root->right);

    return root;
}

void Heapify(TNode* root, TNode* child){
   if(root != NULL && child != NULL){
        if(root->data > child->data){
            int temp = child->data;  
            child->data = root->data;
            root->data = temp;
        }
    } 
}

void Change(TNode* root,int from, int to) {

    if (root == NULL) 
        return;

    else if (root->data == from)
        root->data = to;

    Change(root->left, from, to);
    Change(root->right, from, to);

}

void postOrder(TNode* n){
  if ( n ) {
       postOrder(n->left);
       postOrder(n->right);
       pArray[i] = n->data;
       i++;
    }  
} 

Answer 1

What am I doing wrong here?

我假设您在打印之前已经验证了堆。您的树实现有点困惑，但看起来应该可以。然而，我建议您做的第一件事是在调用您的 Change 方法之前 打印树，只是为了确保您有一个有效的堆。

假设您有一个有效的堆，您的Change 方法有一个问题:它从不调用Heapify。您最终会更改堆中的值而不是重新排列。所以输出的时候当然会乱码。

当您更改一个项目的值时，您必须先将该节点(或该节点的值)移动到它在树中的正确最终位置，然后再更改任何其他值。您可能可以使它与您当前的模型一起工作(通过重复调用 Heapify 直到节点处于正确的位置)。前提是你要增加值(value)。如果您要减小该值(即将 20 更改为 10)，那么您就会遇到问题，因为您的代码无法将项目向上移动到树中。

正如@noobProgrammer 在他的评论中指出的那样，二叉堆通常被实现为数组而不是树。以这种方式实现起来要容易得多，使用的内存更少，而且效率更高。如果您对这是如何完成的感兴趣，您应该阅读我关于堆和优先级队列的多部分博客系列。第一个条目，Priority queues , 描述问题。从那里您可以点击链接了解二进制堆及其实现方式。代码示例使用 C#，但如果您阅读了前两篇介绍性文章并理解了其中的概念，您将能够毫不费力地转换为 C++。