How to copy a tree

Dev Shed Forums Sponsor:

January 8th, 2013, 11:47 AM

asdk77

Registered User

Join Date: Nov 2012

Posts: 17

Time spent in forums: 5 h 19 m 31 sec
Reputation 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!

January 8th, 2013, 01:04 PM

salem

Contributed User

Join Date: Jun 2005

Posts: 3,838

Folding Points: 153 Folding Title: Novice Folder

Time spent in forums: 2 Months 3 Weeks 2 Days 17 h 58 m 15 sec
Reputation Power: 1774

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

January 9th, 2013, 12:05 PM

asdk77

Registered User

Join Date: Nov 2012

Posts: 17

Time spent in forums: 5 h 19 m 31 sec
Reputation Power: 0

Quote:

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

dwise1_aol

Contributing User

Dev Shed God 2nd Plane (6000 - 6499 posts)

Join Date: Jan 2003

Location: USA

Posts: 6,130

Time spent in forums: 2 Months 2 Weeks 3 Days 19 h 43 m 21 sec
Reputation Power: 1949

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.

How to copy a tree

Developer Shed Advertisers and Affiliates