Need a little help with a BST

[TD]

What would be the best way to implement a parent node in a BST? Here's my
code for the insertNode function:

template< class NODETYPE >
void Tree< NODETYPE >::insertNodeHelper( TreeNode< NODETYPE > **ptr, const
NODETYPE &value )
{
if( *ptr == 0 ) // if tree is empty
*ptr = new TreeNode< NODETYPE >( value );

else if( value < (*ptr)->data )
insertNodeHelper( &( (*ptr)->leftPtr ), value );

else if( value > (*ptr)->data )
insertNodeHelper( &( (*ptr)->rightPtr ), value );

else
cout << value << " dup" << endl;

(*ptr)->height = max( height( (*ptr)->leftPtr ), height( (*ptr)->rightPtr
) ) + 1;
}


Hope the formatting doesn't get screwed up. Anyhow, I just need to figure
out how to have each node set a pointer to its parent node on creation. Anyone
have any hints?

Thanks!

TD

[Scott]

I think this would work:
if( *ptr == 0 ) // if tree is empty
*ptr = new TreeNode< NODETYPE >( value, this );

then:
Tree<NODETYPE>::Tree<NODETYPE>(NODETYPE& value, Tree<NODETYPE>* parent)
: Value(value), Parent(parent) {}

with member variable:
Tree<NODETYPE>* Parent;


"TD" <boonewaser@yahoo.com> wrote:
>
>What would be the best way to implement a parent node in a BST? Here's
my
>code for the insertNode function:
>
>template< class NODETYPE >
>void Tree< NODETYPE >::insertNodeHelper( TreeNode< NODETYPE > **ptr, const
>NODETYPE &value )
>{
> if( *ptr == 0 ) // if tree is empty
> *ptr = new TreeNode< NODETYPE >( value );
>
> else if( value < (*ptr)->data )
> insertNodeHelper( &( (*ptr)->leftPtr ), value );
>
> else if( value > (*ptr)->data )
> insertNodeHelper( &( (*ptr)->rightPtr ), value );
>
> else
> cout << value << " dup" << endl;
>
> (*ptr)->height = max( height( (*ptr)->leftPtr ), height( (*ptr)->rightPtr
>) ) + 1;
>}
>
>
>Hope the formatting doesn't get screwed up. Anyhow, I just need to figure
>out how to have each node set a pointer to its parent node on creation.
Anyone
>have any hints?
>
>Thanks!
>
>TD

[Pat]

I'm not sure I understood the solution posted by the other guy, but this problem
is pretty easy. Inside your insert function, you're going to have to call
your search function on the value you're trying to insert to see if it already
exists in the tree. Your search funct. will need two pointers for this: curr
and prev. Curr runs through the tree testing values as it goes.

Assuming value is your parameter and node.value is the node's value (crazily
enough):

int Tree::search (ptr* prev, ptr* curr, val& value) {
if (curr) {
if (value < curr->value){
search (curr, curr->left, value);
}
else if (value > curr->value) {
search (curr, curr->right, value);
}
else {
cout << "Value exists in tree.\n";
return 1;
}
}
else {
cout << "Value does not exist in tree.\n";
return 0;
}
}

now, after this search you have a nice little situation. If the value exists
in the tree you'll know and if it doesn't, this is the great part, you'll
already have a pointer to it's parent (prev). Now all add has left to do
is create a new node with the value, do a quick test to see if it should
be the left or right child of prev and set the appropriate pointer (assuming
prev exists. if not, then you're creating the root node of the tree so you'll
need to set your root pointer also), and then set the node's parent pointer
to prev.

Done.

This may or may not be obvious the way I've explained it but, trust me, the
logic is correct and this works.

"TD" <boonewaser@yahoo.com> wrote:
>
>What would be the best way to implement a parent node in a BST? Here's
my
>code for the insertNode function:
>
>template< class NODETYPE >
>void Tree< NODETYPE >::insertNodeHelper( TreeNode< NODETYPE > **ptr, const
>NODETYPE &value )
>{
> if( *ptr == 0 ) // if tree is empty
> *ptr = new TreeNode< NODETYPE >( value );
>
> else if( value < (*ptr)->data )
> insertNodeHelper( &( (*ptr)->leftPtr ), value );
>
> else if( value > (*ptr)->data )
> insertNodeHelper( &( (*ptr)->rightPtr ), value );
>
> else
> cout << value << " dup" << endl;
>
> (*ptr)->height = max( height( (*ptr)->leftPtr ), height( (*ptr)->rightPtr
>) ) + 1;
>}
>
>
>Hope the formatting doesn't get screwed up. Anyhow, I just need to figure
>out how to have each node set a pointer to its parent node on creation.
Anyone
>have any hints?
>
>Thanks!
>
>TD