决策树-从特定节点删除

Question

我有一个决策树，其中包含节点和将我们引向另一个节点的答案。答案以“：”开头，其余为节点。

我必须执行一个从特定节点删除子树的函数。例如，如果我想删除节点“品牌？”，我希望之后树将从 car-color? 打印到 blue-is-beautiful

我没有以正确的方式成功删除，因为我认为我还必须删除答案 red 并且不知道该怎么做。

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

class Node
{
public:
    Node(string v) { isLeaf = true;  value = v; }
    list<Answer*> answersList;
    string value;
    bool isLeaf;
};
void Tree::del(Node* t)
{
    if (t->isLeaf)
        return;
    for (list<Answer*>::iterator it = t->answersList.begin(); it != t->answersList.end(); it++)
    {
        del((*it)->son);
            delete((*it));
            *it = NULL;
    }
    if (t)
    {
        delete t;
        t = NULL;
    }
}

Answer 1

现在了解了问题（高度限制性要求以及导致您的代码失败的原因），现在我为您提供了答案。

问题是，您需要从存储它的集合中移除您已删除的节点。为此，您需要使用搜索的替代版本来检测哪个 child 具有您要查找的值。

由于'not adding any additional functions'的要求，有两种方法可以解决这个问题。

一种是使用匿名函数进行递归，另一种是'check the child prior to diving into it'。

以下代码片段使用了 DIY-Lambda-Functor，它采用了递归方法。

void Tree::deletefromNode(string val)
{
    bool didFindValue = false;
    std::function<bool (Node *, const string &)> functor;

    class Functor
    {
        public:
            Functor(Tree *owner, bool &didFindValue) : owner(owner), didFindValue(didFindValue)
            {
            }

            bool deleteFromNode(Node *node, const string &value)
            {
                bool foundMatch = false;
                if (node)
                {
                    foundMatch = (node->value == value);

                    if (!foundMatch)
                    {
                        for (list<Answer*>::iterator it = node->answersList.begin(); it != node->answersList.end();)
                        {
                            Node *childNode = (*it)->son;
                            if (deleteFromNode(childNode, value))
                            {
                                owner->del(childNode);
                                it = node->answersList.erase(it);
                                didFindValue = true;
                            }
                            else
                                it++;
                        }
                    }
                }

                return foundMatch;
            }

        private:
            Tree *owner;
            bool &didFindValue;
    };

    Functor(this, didFindValue).deleteFromNode(root, val);
    if (didFindValue)
        cout << "Value not found" << endl;
}

决策树-从特定节点删除

Decision tree- delete from a specific node

c++

tree

recursion