Home > Net >  Decision tree- delete from a specific node
Decision tree- delete from a specific node

Time:10-20

I have a decision tree that includes node and answer that leads us to another nodes. Answers begin with ":" and nodes are the rest.

enter image description here

I have to do a function that delete a subtree from a specific node. For example If I want to delete node "brand?", I want that after that the tree will print from car-color? to blue-is-beautiful

I don't success doing this deletion in the right way because I think I have to delete also the answer red and don't know how to do that.

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;
    }
}

CodePudding user response:

Now having understood the problems (highly restrictive requirements and what is causing your code to fail), I now have an answer for you.

The issue is, that you need to remove the node you've deleted from the collection it is stored in. For this purpose, you need to use an alternate version of your search to detect, which child has the value you are looking for.

Due to the requirement of 'not adding any additional functions', there are two ways to go about this.

One is to employ recursion using an anonymous function, the other is 'check the child prior to diving into it'.

The following code fragment uses a DIY-Lambda-Functor, which employs the recursion method.

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;
}
  • Related