deep copy of binary search tree?

[NancyH]

could someone please help me, I need to write a deep copy constructor for BST. I have already written a method insert and checkEmpty. Can anyone help? thanks

 

[lowbk]

deep copy as in clone? you mean you want to duplicate a BST in a construtor?
do u mean something like

public class bstnode
{
int bstnodevalue;
bstnode next;
.....
}

public class bst
{
bstnode left;
bstnode right;

public bst(bst tree) //constructor
{
...//every node of this input tree is copied over
}

}


i think in the constructor, this.left = tree.left and this.right = tree.right will assign new memory reference to the nodes. but if you don't want memory reassignment but value reassignment, then i think you need some recursion to do the insertion but i'm stuck at it..very sorry

 

[stillflame]

[tt]
public void copy (bst source, bst dest)
{
dest.root().setVal( source.root().value() );
if(source.left() != null)
{
dest.addLeft( source.left().value() );
copy( source.left(), dest.left() );
}
if(source.right() != null)
{
dest.addRight( source.right().value() );
copy( source.right(), dest.right() );
}

}
[/tt]
this has some redundant copying in it to compensate for the root node of the tree, but it should illustrate how this is to be done. you'll probly have to add extra methods 'addLeft(Object)' and 'addRight(Object)' for this to work.

good luck. "If you think you're too small to make a difference, try spending a night in a closed tent with a mosquito."