#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    17
    Rep Power
    0

    How to copy a tree


    I want to copy a part of a tree. And I have found the node as the beginning(like root). How can I copy the tree from this node as a whole?
    Thanks in advance!
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,413
    Rep Power
    1871
    C or C++?

    What sort of "tree" utility functions do you have, say
    - create node
    - insert node
    - copy node
    - traverse tree
    and so on.

    In essence, it's just traversal + node copy + insert
    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
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    17
    Rep Power
    0
    Originally Posted by salem
    C or C++?

    What sort of "tree" utility functions do you have, say
    - create node
    - insert node
    - copy node
    - traverse tree
    and so on.

    In essence, it's just traversal + node copy + insert
    in C
    copy node. copy the children nodes from one node(including this parent node). I think the structure variable can be assigned value directly, so I can write codes like: new_node = node; new_node->children[0] = node->children[0]; recursively.
    Thanks!
  6. #4
  7. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,242
    Rep Power
    2222
    Since it's not clear which you're describing, we should discuss the concept of deep copy vs shallow copy when pointers are involved. Basically, with a shallow copy you have the copy pointing to the exact same data location as the original did, but with a deep copy you also create copies of what the original pointed to so that both the original and the copy has their very own and separate data. With the result of a shallow copy, if either the original or the copy changes the data, both the original and the copy will be affected, but with the result of a deep copy a change in the data of one will not affect the other.

    A simple example would be copying a C-style string:
    Code:
        char *dest;
        char *src = "A string.";
    
        // shallow copy
        dest = src;  // now both pointers point to the same string
    
        // deep copy
        dest = malloc(strlen(src)+1);
        strcpy(dest, src);
    So to deep-copy the subtree it would be:
    malloc root node of the new tree, copy the node's data fields to the new node.
    malloc a child node and assign the pointer to the new root node's children field, then copy the child's data to the new child.
    Repeat.

IMN logo majestic logo threadwatch logo seochat tools logo