Like Tree3Likes
  • 1 Post By whiteflags
  • 1 Post By whiteflags
  • 1 Post By iMalc

Copy control of Binary Tree

This is a discussion on Copy control of Binary Tree within the C++ Programming forums, part of the General Programming Boards category; Hi, I have implemented a copy control version of binary tree.. As I am a Beginner. I think i have ...

  1. #1
    Registered User
    Join Date
    Jan 2013
    Posts
    114

    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.?
    Last edited by Tamim Ad Dari; 05-17-2013 at 10:19 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,822
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,759
    You don't destroy the whole tree properly. That's just not how you do it. You have to rotate the tree into a linked list type structure, where all the nodes are on one side of the tree and destroy all of those.

  4. #4
    Registered User
    Join Date
    Mar 2010
    Posts
    535
    It looks pretty much ok.

    Code:
    TreeNode(const TreeNode& rhs):value(rhs.value),count(count),left(rhs.left),right(rhs.right){++*count; }
    Here you're not initialising count to anything, so the attempt to increment it will segfault or otherwise fail.

    You're missing a "return *this" from your operator=. You're not handling the case where the lhs and rhs are the same.

    Other than that it looks ok to me from what you've posted. I'm not sure what "count" is -- it looks like a reference count to see if a node can be deleted. If that's the case then shouldn't you be incrementing it on everything below the rhs too? I think if you assign overlapping subtrees to each other a few times it'll go wrong. Not completely sure though.

    Quote Originally Posted by whiteflags View Post
    You don't destroy the whole tree properly. That's just not how you do it. You have to rotate the tree into a linked list type structure, where all the nodes are on one side of the tree and destroy all of those.
    Do you? Could you explain what's wrong with the OPs code, as I can't see what's wrong and am curious! It looks like a sensible post order traversal via recursive dtor calls to me. I think (my C++ is pretty shabby).

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    I'm still trying to figure out what "a copy control version of binary tree" means.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Jan 2013
    Posts
    114
    looks like I wasnt able to made every one clear about my intention.. Thing is I have just learnt copying and assigning and destroying a class. and in the book from where I am studying gave me this exercise.There is no way I could know my code is right,, so I posted it here.
    BTW... now I have revised my class.. And I get segmentation fault.. why I am getting segmentation fault
    Code:
    #include <iostream>
    #include <string>
    struct TreeNode{
        TreeNode()=default;
    TreeNode(const std::string &val):value(val),count(new int(1)){}
    TreeNode(const TreeNode& rhs):value(rhs.value),count(rhs.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;
    return *this;
    
    }
    ~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()
    {
        TreeNode root("root");
        TreeNode root2(root);
        TreeNode root3;
        root3=root2;
    
    
    }

  7. #7
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,759
    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.
    Last edited by whiteflags; 05-18-2013 at 11:34 PM.
    Salem likes this.

  8. #8
    Registered User
    Join Date
    Jan 2013
    Posts
    114
    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?
    Last edited by Tamim Ad Dari; 05-19-2013 at 01:02 AM.

  9. #9
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,759
    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.
    Last edited by whiteflags; 05-19-2013 at 03:15 AM.
    smokeyangel likes this.

  10. #10
    Registered User
    Join Date
    Jan 2013
    Posts
    114
    What is the "rotate and delete a list" way? will you please explain?

  11. #11
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,759
    Well the rotate and delete a list way has to do with changing the structure of the tree to make it easier to delete in a loop. Normally, rotation is used to balance trees, but if you keep rotating in one direction, you make a list of nodes. If every node in the tree is on one side, it is easier to loop over that list of nodes and delete each one.

    One way goes like this: First, you need to decide which link to use and it doesn't really matter which. Say we decide to rotate to the right: The main thing is when the left child of the current node exists, you have to do one rotation to put the child in line and keep going. When there is only one child on the right, you have to save the link to the right child then delete the current node. The rotations will keep any subtrees alive that you haven't gotten to yet.

    Further reading on rotation:

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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
    whiteflags likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Converting From Binary Tree to Threaded Binary Trees
    By elton_fan in forum C Programming
    Replies: 15
    Last Post: 11-08-2007, 11:41 PM
  2. Replies: 2
    Last Post: 08-01-2007, 02:08 PM
  3. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  4. Still battling with Copy Control
    By Mario F. in forum C++ Programming
    Replies: 9
    Last Post: 06-23-2006, 09:04 AM
  5. display tree data in binary tree format
    By xddxogm3 in forum C++ Programming
    Replies: 4
    Last Post: 12-11-2003, 12:47 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21