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.

C++:
01 typedef map<Node*, Node*> NodeMap;
02 Node* copy_recursive(Node* cur, NodeMap& nodeMap){
03   if(cur==NULL){
04     return NULL;
05   }
06 
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 }
18 
19 Node* copy_structure(Node* root){
20   NodeMap nodeMap; //we will need an empty map
21   return copy_recursive(root, nodeMap);
22 }
Advertisements
This entry was posted in C++. Bookmark the permalink.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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