445,918 Members | 2,294 Online
Need help? Post your question and get tips & solutions from a community of 445,918 IT Pros & Developers. It's quick & easy.

clone a tree

 P: n/a hi all i have a binary tree and want to clone this, is there a standard way to do this,i think i can do it by traversing the tree like in the preorder tecnique and add all the nodes to another root is there a common way to do this? Dec 21 '05 #1
6 Replies

 P: n/a standard knows nothing about binary trees and therefore there's no standard way to do this, it all depends on your particular implementation of binary tree Dec 21 '05 #2

 P: n/a jw wrote: hi all i have a binary tree and want to clone this, is there a standard way to do this,i think i can do it by traversing the tree like in the preorder tecnique and add all the nodes to another root is there a common way to do this? that would likely be it. Dec 21 '05 #3

 P: n/a jw wrote: hi all i have a binary tree and want to clone this, is there a standard way to do this,i think i can do it by traversing the tree like in the preorder tecnique and add all the nodes to another root is there a common way to do this? I haven't tested this, but I think it would do the trick: struct Node { Node *left; Node *right; Node *clone(); }; Node *Node::clone() { Node *node = new Node; if(left) node->left = left->clone(); if(right) node->right = right->clone(); return node; } Given the root node, the entire tree will be cloned by: Node *rootClone = root->clone(); DW Dec 21 '05 #4

 P: n/a David White wrote: I haven't tested this, but I think it would do the trick: struct Node { Oops, you need this as well: Node() : left(0), right(0) {} Node *left; Node *right; Node *clone(); }; Node *Node::clone() { Node *node = new Node; if(left) node->left = left->clone(); if(right) node->right = right->clone(); return node; } DW Dec 21 '05 #5

 P: n/a jw wrote: hi all i have a binary tree and want to clone this, is there a standard way to do this,i think i can do it by traversing the tree like in the preorder tecnique and add all the nodes to another root is there a common way to do this? Tree newTree = oldTree; Seriously, it's hard to offer much help if we have no idea what your data structure looks like (not to mention that this is OT without any reference to C++). Knowing nothing else, I would suggest a recursive approach: clone the left and right children and attach them to the cloned root. Dec 21 '05 #6

 P: n/a jw wrote: hi all i have a binary tree and want to clone this, is there a standard way to do this,i think i can do it by traversing the tree like in the preorder tecnique and add all the nodes to another root is there a common way to do this? Why not use the C++ STL library containers std::set or std::map which can easily be clone via copy constructor? Many binary tree requirements can be accomplished via std::set or std::map containers. Dec 21 '05 #7