January 8th, 2013, 11:47 AM
-
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!
January 8th, 2013, 01:04 PM
-
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
January 9th, 2013, 12:05 PM
-
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!
January 9th, 2013, 01:45 PM
-
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.