基于数组构建MaxHeap树失败，请求排查createHeapTree函数问题

核心问题拆解 #

1. createHeapTree函数的逻辑错误 #

• 函数中错误使用类成员root赋值左右子树，而非当前递归节点root1。比如root->left = ...应改为root1->left = ...，否则所有递归创建的节点都会挂载到类的根节点上，导致树结构完全混乱。
• 参数root1为传值传递，函数内对它的赋值不会影响外部，且函数开头直接重新赋值root1 = new Enode(arr[idx]);，该参数完全多余，可直接移除。

2. Heaptree类的根节点未正确初始化 #

• main函数中，createHeapTree返回的节点仅赋值给局部变量Root，未更新h1的成员root。因为getRoot()返回的是指针副本，修改副本不会改变类内部的root，需添加设置根节点的方法，或让createHeapTree直接修改类的root成员。

3. heapify函数实现错误 #

• 当前实现从数组头部到尾部遍历，仅能保证单个节点的左右子节点更小，但无法保证整个数组是合法最大堆。标准最大堆堆化需从最后一个非叶子节点（索引为n/2 - 1）开始，倒序遍历到根节点，对每个节点执行下沉操作。

修正后的完整代码 #

#include <bits/stdc++.h>

using namespace std;

class Enode{
private: 
    int data;
    Enode* left;
    Enode* right;
    
    Enode(int d){
        data = d;
        left = right = NULL;
    }
    
    friend class Heaptree;
};

// MAX HEAP STRUCTURE, ROOT NODE IS MAX
class Heaptree{
private:
    Enode* root;
    
    // 辅助递归函数，移除多余参数
    Enode* buildTree(int arr[], int idx, int n){
        if(idx >= n){
            return NULL;
        }
        
        Enode* curr = new Enode(arr[idx]);
        curr->left = buildTree(arr, 2*idx + 1, n);
        curr->right = buildTree(arr, 2*idx + 2, n);
        
        return curr;
    }
    
public:
    Heaptree(){
        root = NULL;
    }
    
    // 直接构建并更新类的根节点
    void createHeapTree(int arr[], int n){
        root = buildTree(arr, 0, n);
    }
    
    Enode* getRoot(){
        return root;
    }
    
    void printLevelOrder(){
        if(root == nullptr){
            cout << "Tree is empty" << endl;
            return;
        }
        Enode* temp;
        queue <Enode*> Q;
        Q.push(root);
        while(!Q.empty()){
            temp = Q.front();
            cout << temp->data << " ";
            Q.pop();
            if(temp->left != nullptr){
                Q.push(temp->left);
            }
            if(temp->right != nullptr){
                Q.push(temp->right);
            }
        }
        cout << endl;
    }
};

// 修正后的最大堆堆化函数
void heapify(int arr[], int n){
    // 从最后一个非叶子节点开始倒序遍历
    for(int i = n/2 - 1; i >= 0; i--){
        int largest = i; // 初始化最大元素为当前节点
        int left = 2*i + 1;
        int right = 2*i + 2;
        
        // 找到左右子节点中更大的那个
        if(left < n && arr[left] > arr[largest]){
            largest = left;
        }
        if(right < n && arr[right] > arr[largest]){
            largest = right;
        }
        
        // 如果最大元素不是当前节点，交换并继续堆化受影响的子树
        if(largest != i){
            swap(arr[i], arr[largest]);
            heapify(arr, n); // 递归堆化交换后的子树
        }
    }
}

int main(){
    int n;
    Heaptree h1;
    cin >> n;
    int comparray[n];
    for(int i = 0; i < n; i++){
        cin >> comparray[i];
    }
    
    heapify(comparray, n);
    
    cout << "Heapified array: ";
    for(int i = 0; i < n; i++){
        cout << comparray[i] << " ";
    }
    cout << endl;
    
    // 直接调用类的方法构建树，自动更新根节点
    h1.createHeapTree(comparray, n);
    cout << "Level order traversal of heap tree: ";
    h1.printLevelOrder();
    
    return 0;
}

关键修复说明 #

• createHeapTree重构：将递归逻辑拆分到私有辅助函数buildTree，直接返回当前节点的左右子树，避免错误使用类的根节点。新增公共方法createHeapTree直接更新类的root成员，无需外部手动赋值。
• 根节点初始化修复：main函数中不再手动处理根节点指针，直接调用h1.createHeapTree完成树的构建与根节点设置。
• heapify函数修正：改为从最后一个非叶子节点倒序处理，确保每个节点正确下沉，构建合法最大堆。
• printLevelOrder添加空树判断：避免空指针访问崩溃。

内容的提问来源于stack exchange，提问作者Yash Mehta