Structure copy

Write a method that takes a pointer to a Node structure as a parameter and returns a complete copy of the passed in data structure. The Node data structure contains two pointers to other Nodes.

The algorithm will maintain a mapping from a node address in the original structure to the corresponding node in the new structure. This mapping will allow us to discover previously copied nodes during a traditional depth first traversal of the structure. Traversals often mark visited nodes–the mark can take many forms and does not necessarily need to be stored in the node.

01 typedef map<Node*, Node*> NodeMap;
02 Node* copy_recursive(Node* cur, NodeMap& nodeMap){
03   if(cur==NULL){
04     return NULL;
05   }
07   NodeMap::iterator i=nodeMap.find(cur);
08   if(i!=nodeMap.end()){
09     //we have been here before, return the copy
10     return  i->second;
11   }
12   Node* node=new node;
13   nodeMap[cur]=node; //map current before traversing links
14   node->ptr1=copy_recursive(cur->ptr1,nodeMap);
15   node->ptr2=copy_recursive(cur->ptr2,nodeMap)
16   return node;
17 }
19 Node* copy_structure(Node* root){
20   NodeMap nodeMap; //we will need an empty map
21   return copy_recursive(root, nodeMap);
22 }
This entry was posted in C++. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s