Thread: Copy control of Binary Tree

Hi, I have implemented a copy control version of binary tree.. As I am a Beginner. I think i have made my mistake. But I cant figure it out.

Code:

#include <iostream>
#include <string>
class TreeNode{
TreeNode(const std::string &val):value(val),count(new int(1)){}
TreeNode(const TreeNode& rhs):value(rhs.value),count(count),left(rhs.left),right(rhs.right){++*count; }

TreeNode& operator=(const TreeNode &rhs)
{
     ++*rhs.count;
     if(--*count==0)
     {
         delete left;
         delete right;
         delete count;
     }
     left=rhs.left;
     right=rhs.right;
     value=rhs.value;
    count=rhs.count;

}
~TreeNode()
  {
       if(--*count==0)
       {
           delete left;
           delete right;
           delete count;
       }
  }
private:
   std::string value;
   int *count;
   TreeNode *left;
   TreeNode *right;
};
using namespace std;

int main()
{
    cout << "Hello world!" << endl;
    return 0;
}

is there any wrong.?

Assuming it compiles (if it doesn't compile, you should post your error messages), then the first obvious mistake is your main only prints "Hello world!" and makes NO attempt to use your tree code.

I'm still trying to figure out what "a copy control version of binary tree" means.

BTW... now I have revised my class.. And I get segmentation fault.. why I am getting segmentation fault

Code:

struct TreeNode{
    TreeNode()=default;

TreeNode& operator=(const TreeNode &rhs)
{
     ++*rhs.count;
     if(--*count==0)
     {
         delete left;
         delete right;
         delete count;
     }
     left=rhs.left;
     right=rhs.right;
     value=rhs.value;
return *this;

}

    TreeNode root3;
    root3=root2;

After using my debugger, (a skill which you should cultivate) I found that the segmentation fault was generated on the line highlighted in red. The reason is simple. The root3 variable was default constructed; when you got to the line in red, you dereferenced the count pointer before it was allocated/initialized. Doing that can generate a segmentation fault.

Default construction is not good enough for your tree. You need to initialize every pointer at the very least, no matter what.

That error was solved but there is a new problem,

Code:

#include <iostream>
#include <string>
using namespace std;
struct TreeNode{
    TreeNode():value("A"),count(new int(1)),right(NULL),left(NULL) {cout<<"Creating"<<endl;}
TreeNode(const std::string &val):value(val),count(new int(1)){cout<<"Creating"<<endl;}
TreeNode(const TreeNode& rhs):value(rhs.value),count(rhs.count),left(rhs.left),right(rhs.right){++*count; cout<<"Impicit copy"<<endl; }

TreeNode& operator=(const TreeNode &rhs)
{
    cout<<"Explicit copy"<<endl;
     ++*rhs.count;
     if(--(*count)==0)
     {
         delete left;
         delete right;
         delete count;
     }
     left=rhs.left;
     right=rhs.right;
     value=rhs.value;
return *this;

}
~TreeNode()
  {
      cout<<"Destroying"<<endl;
       if(--*count==0)
       {
           cout<<"Destroying all"<<endl;
           delete left;
           delete right;
           delete count;
       }
  }
//private:
   std::string value;
   int *count;
   TreeNode *left;
   TreeNode *right;
};
using namespace std;

int main()
{

    TreeNode root("root");
    TreeNode root2(root);
    TreeNode root3;
    root3=root2;
    root3.left=&root;
    root3=root3;

}

in line 30 I have put a marker when the reference count goes down to 0. But when I run the program it never shows that message("Destroying all"). does that mean that those memory were never deleted? and also why cant I Self assign?

I commented earlier that destruction was wrong and I wasn't sure how to comment apart from that. I will try harder now, although I still prefer the "rotate and delete a list" way of doing it. There's no recursion that way and I find that healthy.

The main problem with a tree data structure owning both of its subtrees is that you will wind up not deleting all of the nodes. You will instead get to the extreme left, then delete, and suddenly not be able to go to the next level. When you deleted the left link, you also destroyed the branch to the right child, which might have had more nodes.

I find that to do this properly, nodes need to be able to delete themselves, and that the tree should only own the root node, not the subtrees. The nodes themselves own the subtrees. Now deleting root will start the recursion to delete the whole tree, and the nodes can recursively delete themselves. Each node will send you to the left and the right before exiting the destructor, and since you will definitely reach everything, it works.

Here's an example:

Code:

#include <iostream>
#include <string>

using namespace std;

class Tree
{
public:
    Tree() : root(nullptr)
    {
        cout << "Empty tree." << endl;
    }

    void insert(const string& v)
    {
        TreeNode *curr = root;
        while (curr != nullptr)
        {
            if (curr->value < v)
            {
                if (curr->leftChild == nullptr)
                {
                    curr->leftChild = new TreeNode(v);
                    return;
                }
                else
                {
                    curr = curr->leftChild;
                }
            }
            else if (curr->value > v)
            {
                if (curr->rightChild == nullptr)
                {
                    curr->rightChild = new TreeNode(v);
                    return;
                }
                else
                {
                    curr = curr->rightChild;
                }
            }
            else
            {
                return;
                // Don't insert pre-existing strings.
            }
        }

        // If we get here, new tree!
        root = new TreeNode(v);
        return;
    }

    ~Tree()
    {
        delete root;
    }

private:
    struct TreeNode
    {
        string value;
        TreeNode *leftChild;
        TreeNode *rightChild;

        TreeNode (const string& val) : value(val), leftChild(nullptr), rightChild(nullptr)
        {
            // Nothing
        }

        ~TreeNode()
        {
            delete leftChild;
            delete rightChild;
            cout << value << " deleted." << endl;

        }
    };

    TreeNode *root;
};

int main()
{
    Tree tree;
    tree.insert("aaa");
    tree.insert("ddd");
    tree.insert("bbb");
    tree.insert("ab");
    tree.insert("ccc");
    tree.insert("aba");
}

I'm sorry it's so contrived. nullptr is a C++0x thing, and OP is actually using C++0x, in case that confuses anyone.

Pseudocode for tree deletion that wont cause a stack overflow:

Code:

while head is not null
  if head's left child is not null
    rotate right at the head node
  else
    set temp equal to head's right child
    delete head
    set head equal to temp