C++替罪羊树中TreeNode模板的数组初始化实现问题

问题核心 #

在开发C++替罪羊树（ScapegoatST）时，rebuild函数中的TreeNode<T>* a = new TreeNode<T>[ns]()代码触发构造函数初始化错误——原因是TreeNode<T>类仅定义了带参数的构造函数，而动态数组初始化必须调用默认构造函数（无参构造）。

出错代码片段 #

Rebuild函数关键代码 #

template <typename T>
void ScapegoatST<T>::rebuild(TreeNode<T>* node){
    int ns = getHeight(node);
    TreeNode<T>* p = node->getParent();
    TreeNode<T>* a  = new TreeNode<T>[ns](); // 此处触发构造函数错误
    TreeNode<T>* r;
    
    packintoArray(node,a,0);
    if (p == NULL){
        r = buildBalanced(a,0,ns);
        r->setParent(NULL);
    } else if (p->getRight() == node){
        TreeNode<T>* Tr = buildBalanced(a, 0, ns);
        p->setRight(Tr);
        p->getRight()->setParent(p);
    } else {
        p->setLeft(buildBalanced(a,0,ns));
        p->getLeft()->setParent(p);
    }
    
}

TreeNode类定义（.h文件） #

#ifndef TREE_NODE_H
#define TREE_NODE_H

#include <cstdlib>
#include <iostream>
using namespace std;

template <typename T>
class TreeNode{
public:
    TreeNode(T nData); // 仅存在带参数的构造函数
    virtual ~TreeNode();
    
    T getData();
    TreeNode<T>* getLeft();
    TreeNode<T>* getRight();
    TreeNode<T>* getParent();
    
    void setData(T nData);
    void setLeft(TreeNode<T>* nleft){left=nleft;};
    void setRight(TreeNode<T>* nright){right=nright;};
    void setParent(TreeNode<T>* nparent){parent=nparent;};
    
    template <typename S>
    friend class ScapegoatST;
    
private:
    T data;
    TreeNode<T>* left;
    TreeNode<T>* right;
    TreeNode<T>* parent;
};

template <typename T>
TreeNode<T>::TreeNode(T nData){
    data = nData;
    left = NULL;
    right = NULL;
}

template <typename T>
TreeNode<T>::~TreeNode(){
    delete left;
    delete right;
    delete parent; // 存在双重释放风险
    data = NULL; // 仅对指针类型T合法，非指针类型会报错
}

template <typename T>
T TreeNode<T>::getData(){
    return data;
}

template <typename T>
void TreeNode<T>::setData(T nData){
    data = nData;
}

#endif

解决方法 #

1. 为TreeNode添加默认构造函数 #

修改TreeNode类的构造函数声明，新增无参构造：

// 在TreeNode类的public区域添加
TreeNode();
TreeNode(T nData);

实现默认构造函数，合理初始化成员变量：

template <typename T>
TreeNode<T>::TreeNode(){
    left = NULL;
    right = NULL;
    parent = NULL;
    // 若T为自定义类型，需确保T本身也有默认构造函数
}

2. 修复析构函数的潜在问题 #

原析构函数中delete parent会导致双重释放（父节点析构时也会处理子节点），data = NULL仅对指针类型合法，需修改：

template <typename T>
TreeNode<T>::~TreeNode(){
    // 仅递归删除左右子节点，不要操作父节点
    delete left;
    delete right;
}

3. 可选：改用vector替代动态数组 #

若不想修改TreeNode构造函数，可使用std::vector存储节点指针，避免直接创建TreeNode数组：

template <typename T>
void ScapegoatST<T>::rebuild(TreeNode<T>* node){
    int ns = getHeight(node);
    TreeNode<T>* p = node->getParent();
    vector<TreeNode<T>*> a(ns); // 存储指针，无需TreeNode默认构造
    TreeNode<T>* r;
    
    packintoArray(node, &a[0], 0); // 调整packintoArray参数适配指针数组
    // 后续逻辑保持不变
}

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