Binary Tree Search

Need to create function binaryTreeSearch, which attemps to locate a specified value in a binary search tree object. The function should take as arguments a pointer to the root node of the binary tree and a search key to be located. If the node containing the search key is found, the function should return a pointer to that node; otherwise , the function should return a null pointer.



// Definition of class TreeNode
#ifndef SATCHERD_TREENODE_H
#define SATCHERD_TREENODE_H

template< class NODETYPE > class Tree; // forward declaration

template< class NODETYPE >
class TreeNode {
friend class Tree< NODETYPE >;
public:
TreeNode( const NODETYPE &d )
: leftPtr( 0 ), data( d ), rightPtr( 0 ) { }
NODETYPE getData() const { return data; }
private:
TreeNode< NODETYPE > *leftPtr; // pointer to left subtree
NODETYPE data;
TreeNode< NODETYPE > *rightPtr; // pointer to right subtree
};

#endif




// Definition of template class Tree
#ifndef SATCHERD_TREE_H
#define SATCHERD_TREE_H

#include <iostream>
#include <cassert>
#include "satcherd_Treenode.h"

using std::endl;

template< class NODETYPE >
class Tree {
public:
Tree();
void insertNode( const NODETYPE & );
void preOrderTraversal() const;
void inOrderTraversal() const;
void postOrderTraversal() const;

void binaryTreeSearch(NODETYPE);

private:
TreeNode< NODETYPE > *rootPtr;

// utility functions
void insertNodeHelper(
TreeNode< NODETYPE > **, const NODETYPE & );
void preOrderHelper( TreeNode< NODETYPE > * ) const;
void inOrderHelper( TreeNode< NODETYPE > * ) const;
void postOrderHelper( TreeNode< NODETYPE > * ) const;

void binaryTreeSearchHelper( NODETYPE , TreeNode<NODETYPE>*);

};

template< class NODETYPE >
Tree< NODETYPE >::Tree() { rootPtr = 0; }

template< class NODETYPE >
void Tree< NODETYPE >::insertNode( const NODETYPE &value )
{ insertNodeHelper( &rootPtr, value ); }

// This function receives a pointer to a pointer so the
// pointer can be modified.
template< class NODETYPE >
void Tree< NODETYPE >::insertNodeHelper(
TreeNode< NODETYPE > **ptr, const NODETYPE &value )
{
if ( *ptr == 0 ) { // tree is empty
*ptr = new TreeNode< NODETYPE >( value );
assert( *ptr != 0 );
}
else // tree is not empty
if ( value < ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->leftPtr ), value );
else
if ( value > ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->rightPtr ), value );
else
cout << value << " dup" << endl;
}

template< class NODETYPE >
void Tree< NODETYPE >::preOrderTraversal() const
{ preOrderHelper( rootPtr ); }

template< class NODETYPE >
void Tree< NODETYPE >::preOrderHelper(
TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != 0 ) {
cout << ptr->data << ' ';
preOrderHelper( ptr->leftPtr );
preOrderHelper( ptr->rightPtr );
}
}

template< class NODETYPE >
void Tree< NODETYPE >::inOrderTraversal() const
{ inOrderHelper( rootPtr ); }

template< class NODETYPE >
void Tree< NODETYPE >::inOrderHelper(
TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != 0 ) {
inOrderHelper( ptr->leftPtr );
cout << ptr->data << ' ';
inOrderHelper( ptr->rightPtr );
}
}

template< class NODETYPE >
void Tree< NODETYPE >::postOrderTraversal() const
{ postOrderHelper( rootPtr ); }

template< class NODETYPE >
void Tree< NODETYPE >::postOrderHelper(
TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != 0 ) {
postOrderHelper( ptr->leftPtr );
postOrderHelper( ptr->rightPtr );
cout << ptr->data << ' ';
}
}



template< class NODETYPE >
void Tree< NODETYPE >::binaryTreeSearch(NODETYPE key )
{binaryTreeSearchHelper(key,rootPtr);}


template< class NODETYPE >
void Tree< NODETYPE >::binaryTreeSearchHelper( NODETYPE &key, TreeNode<NODETYPE>*ptr)
{
if(ptr!=NULL)
{
if(key==ptr->data)
return ptr;
if(key<ptr->data)
return binaryTreeSearchHelper(key,ptr->leftPtr);
else
return binaryTreeSearchHelper(key,ptr->rightPtr);
}
else return NULL;

}

#endif


// Driver to test class Tree
#include <iostream>
#include <iomanip>
#include "satcherd_tree.h"

using std::cout;
using std::cin;
using std::setiosflags;
using std::ios;
using std::setprecision;

int main()
{
Tree< int > intTree ;
int intVal, i;

cout << "Enter 10 integer values:\n";
for( i = 0; i < 10; i++ ) {
cin >> intVal;
intTree.insertNode( intVal );
}

cout << "\nPreorder traversal\n";
intTree.preOrderTraversal();

Tree< int > intTree ;
cout << "\nBinary Search of Tree.\n";
intTree.binaryTreeSearch(3);


return 0;
}

And your question is? How do you use code tags?

If functions need to return a value they shouldn't be declared as returning void.

Do you have to use recursion to search your tree? There's a very simple iterative method.

There's a very simple iterative method.
There's an even simpler recursive method.

Recursion is good for certain things... IMHO it's easier to use a recursive solution here... but hey, we're all entitled to our opinion :D.

U.

Thanks,
But I need help, if you can see where I made the mistakes point them out and I will learn.
If you know a method to help me solve this, an example would be nice. I know that my search function is messed up but I need to know what to do to make it work. I'm not looking for someone to do the work, I'm at a point where I don't know what to so next.

Besides the fact that binaryTreeSearch and binaryTreeSearchHelper should be returning the result of the find, I don't see anything wrong with the logic of the search.

Instead of doing binaryTreeSearchHelper which is really too long of a function name, you can overload binaryTreeSearch so that you have two binaryTreeSearch functions tacking different types of arguments one public and one private.

>There's an even simpler recursive method.

I don't think it's any simpler. How complicated is

Code:

---

                node* it = root;
                while(it!=0)
                {
                        if(key==it->key)
                                return it;
                        if(key<it->key)
                                it=it->left;
                        if(key>it->key)
                                it=it->right;
                }

---

?

>Recursion is good for certain things

I agree.

>IMHO it's easier to use a recursive solution here...

I don't agree. It's doesn't make anything simpler, and it's inefficient in comparison with the iterative one.

>but hey, we're all entitled to our opinion

True.

hi c++ newbie,

do u have binary search tree program for the scenario what u have explained?


memebr function to locate a specified value in a binary search tree object. the function should take as arguments a pointer to the root node of the binary tree and search key to be located. If the node containing the search key is found, the function should return a pointer to that node, otherwise, the function should return a null pointer.

pls help me out. i need program for this one.

Nine years almost to the day? Holy thread bump batman!