c++ - 在 C++ 中的树中分配节点指针

Question

问题可以概括为:如何正确处理递归函数中的指针初始化？

我想这道题很简单，但我还是想不出怎么解。

我有一个树结构定义如下:

class SplitNode{

public:
    Data d;
    SplitNodeParam snp;
    SplitNode* left_; //will stay uninitialized
    SplitNode* right_;}

我使用以下递归函数从根开始构建一棵树:

void buildTree(SplitNode* n){
    findBestSplit(n);
    buildTree(n->left);
    buildTree(n->right); //forget that the tree growing doesnt stop
}

我获取一个节点及其数据，并根据函数对数据进行拆分。我想按如下方式分配当前节点的左右子节点。

void findBestSplit(SplitNode* n){

    //Do stuff with data and parameters

    SplitNodeParam left_parameter(/*Some parameters*/);
    *(n->left)=SplitNode(left_parameter); 

    SplitNodeParam right_parameter(/*Some parameters*/);
    *(n->right)=SplitNode(right_parameter);

}

大问题似乎是我想将空指针 SplitNode 分配给局部变量并希望稍后取回它，这几乎是不可能的。

我在 C 中看到一些示例来做类似的事情(使用 malloc)，但我想知道如何在 C++ 中巧妙地完成这件事

提前致谢。

Answer 1

您不想像此处那样将 n->left 分配给局部变量。我假设此时您尚未在 findBestSplit 中为这些拆分节点分配任何内存。

相反，您必须通过说 n->left = new SplitNode(left_parameter) 来管理内存，然后稍后使用相应的 delete 清理分配的内存称呼。 n->right 也是如此。

您最终可能会得到一个采用根节点的 deleteTree 函数。该根节点将对其子节点递归调用 deleteTree，直到到达叶节点。在叶节点，该节点将删除自身然后返回。这样您就不会忘记所有的树叶，并且可以正确释放所有内存。