Thread: 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 >:reOrderTraversal() const
{ preOrderHelper( rootPtr ); }

template< class NODETYPE >
void Tree< NODETYPE >:reOrderHelper(
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 >:ostOrderTraversal() const
{ postOrderHelper( rootPtr ); }

template< class NODETYPE >
void Tree< NODETYPE >:ostOrderHelper(
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;
}