C++实现决策树指定节点子树删除的功能问题

你当前的实现存在三个核心问题，导致无法完成预期的删除、重连逻辑：

1. 仅递归删除了目标节点及其子树资源，没有处理目标节点的父节点的指向边，会出现野指针，也无法实现重连需求
2. 函数参数Node* t是值传递，函数内的t = NULL操作无法修改外部持有的指针，属于无效操作
3. 叶子节点直接返回的逻辑会导致叶子节点本身的内存泄漏

实现思路 #

要完成你要求的删除后自动重连的逻辑，首先需要能获取到待删除节点的父节点信息，这里推荐给Node类新增父节点指针，节点创建时直接赋值，后续处理效率更高。处理逻辑顺序如下：

• 先找到待删除节点对应的父节点中的Answer边
• 根据需求选择直接删除该边，或者将边的指向重连到待删除节点的子节点
• 再递归释放待删除节点及其子树的所有资源，避免内存泄漏

完整修改代码 #

类定义修改 #

class Answer
{
public:
    string ans;
    Node* son;
    Answer(string s, Node* p) { ans = s; son = p; }
};

class Node
{
public:
    // 构造函数新增父节点参数，默认值为空
    Node(string v, Node* p = nullptr) { 
        isLeaf = true;  
        value = v; 
        parent = p;
    }
    list<Answer*> answersList;
    string value;
    bool isLeaf;
    Node* parent; // 新增父节点指针成员
};

删除函数实现 #

void Tree::del(Node* t)
{
    if (!t) return;
    // 处理父节点的指向边
    if (t->parent) {
        for (auto it = t->parent->answersList.begin(); it != t->parent->answersList.end(); ) {
            if ((*it)->son == t) {
                // 符合你示例的重连逻辑：待删除节点只有一个子路径时，直接将父节点边连到孙子节点
                if (!t->isLeaf && t->answersList.size() == 1) {
                    (*it)->son = t->answersList.front()->son;
                    (*it)->son->parent = t->parent; // 同步更新孙子节点的父指针
                } else {
                    // 不需要重连时直接删除该Answer边
                    delete *it;
                    it = t->parent->answersList.erase(it);
                    continue;
                }
            }
            ++it;
        }
    }
    // 递归释放所有子节点资源
    for (auto it = t->answersList.begin(); it != t->answersList.end(); ++it) {
        del((*it)->son);
        delete *it;
    }
    t->answersList.clear();
    // 释放当前节点本身
    delete t;
}

可选方案 #

如果你不想修改Node类的结构新增父指针，可以额外实现一个查询父节点的函数，从决策树根节点递归遍历所有节点，找到指向待删除节点的父节点后再做边处理，逻辑和上面一致。

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