0

I'm trying to write a function for my binary tree class, which deletes all node with only one child. My teacher said, I should use a pointer to pointer to do it. But I have some problems. My function doesn't do it right. I used a function for deleting a node by its key from the binary tree, which worked well:

bool remove(int iKey) {
    Node** pTmp = &pRoot;
    //searching for a key in the tree
    ...
    //there's no right child
    Node* pNew = nullptr;
    pNew = (*pTmp)->m_pLeft;

    delete *pTmp;
    *pTmp = pNew;
    return true;
    ...
}

Here's my function for removing one child node:

void BinTree::deleteSingle(Node* root)
{
    if (root != nullptr)
    {
        if (root->getLeft() != nullptr)
            deleteSingle(root->getLeft());
        if (root->getRight() != nullptr)
            deleteSingle(root->getRight());
        //there's only left child
        if (root->getLeft() != nullptr && root->getRight() == nullptr)
        {
            //1 version: this doesn't work for me
            /*Node** tmp = &root;
            Node* child = root->pLeft;
            delete *tmp;
            *tmp = child;*/

            //2 version: but this workes great
            Node* child = root->pLeft;
            delete root;
            *root = *child;
        }
        //if there's only right child - remove the node analogical
    }
}

Here's my destructor for Node class and an assignment operator. The BinTree class has Node* pRoot; as a private member.

Node::~Node()
{
    pLeft = nullptr;
    pRight = nullptr;
}
Node& Node::operator=(const Node& node)
{
    key = node.key;
    data = node.data;
    pLeft = nullptr;
    pRight = nullptr;
    if (node.pLeft != nullptr)
        pLeft = new Node(node.pLeft->key, node.pLeft->data);
    if (node.pRight != nullptr)
        pRight = new Node(node.pRight->key, node.pRight->data);
    return *this;
}

I don't understand why I do need remove a node using pointer to pointer, if my 2 version works good and needs less memory. Maybe because I need also have a destructor and an assignment operator for the Node class? And I still can't understand, why my first version doesn't work and what should I do. I hope you could help me or show me some other correct method to delete one child nodes

__________________UPDATE_____________________

I've found out an other method to do it, but I'm not using pointer to pointer here (I'm still interested in it also, if anyone could show me it). Here I just copy the data and the pointers of the child and delete the child node.

if (root->getLeft() != nullptr && root->getRight() == nullptr)
{
    Node* child = root->pLeft;
    root->key = child->key;
    root->data = child->data;
    root->pLeft = child->pLeft;
    root->pRight = child->pRight;
    delete child;
}
V_swan
  • 21
  • 6
  • The usage of `Node** pTmp = &pRoot` and `Node** tmp = &root` does not make to much sense in the shown code. You would need to ask your teacher why you are expected to use it that way. Besides that dereferencing a pointer (`*root`) after a delete (`delete root;`) is invalid, so your code results into undefined behavior. It is not even clear what you want to achieve with `*root = *child`. And there a various other mistakes in your code, which could result into leaking or double frees. – t.niese Sep 29 '19 at 12:43
  • I would suggest that you read a decent book about c++ ([The Definitive C++ Book Guide and List](https://stackoverflow.com/questions/388242)) I may be wrong about your teacher, but it seems to me that he doesn't teach good c++. In modern c++ you won't use `new` and `delete` to manage memory and object lifetimes, you instead utilize smart pointers. And if you want to teach the usage of `new` and `delete`, you first should ensure that lifetime of objects are clear, when you are allowed to dereference pointers, the rules of three and five and other things. – t.niese Sep 29 '19 at 12:54
  • @t.niese I know about existing structures for trees and so on for c++, but I have to learn it this way (I guess for better understanding data structures in c++). I know about rule of 3 (I'm learning c++11). Anyway, maybe you could help me and explain my mistakes further or maybe suggest clear method for deleting one child nodes from the binary tree – V_swan Sep 29 '19 at 13:03
  • @L.F. yes, sorry, since c++11 there's rule of 5 as I read. But I've implemented my classes by rule of 3 for now – V_swan Sep 29 '19 at 14:09
  • @L.F. What do you want to say with that comment? That the rules of three, five and zero are not part of the language standard (no matter which version). Or that what the rule of three is about does not apply to c++11 (and newer) anymore? – t.niese Sep 29 '19 at 16:19
  • @L.F. The rules say if you have a user-defined _destructor_ then you most likely also need to implement the _copy constructor_ and _copy assignment operator_ (hench rule of three), to produce logically correct code. And that is still valid in c++20. But if you implement those and you also want to (which is not a requirement) support move semantics, then you also need to implement the _move constructor and _move assignment operator_ (so the rule of five), but not implementing them is not an error it just might prevent some optimizations. The rule of four (and a half) is just a variation. – t.niese Sep 30 '19 at 10:03
  • @L.F. that's what is referred to as rule of three by [cppreference.com](https://en.cppreference.com/w/cpp/language/rule_of_three) and also what is referred to as rule of three when it is mentioned in the cppcon talks. – t.niese Sep 30 '19 at 10:31
  • @t.niese OK, I will retract my comments and follow the standard terminology then. – L. F. Sep 30 '19 at 10:35

0 Answers0