Thread: Binary Tree Search

  1. #1
    Registered User
    Join Date
    Nov 2001
    Posts
    10

    Unhappy Binary Tree Search PLEASE HELP!!!!!!!!!!!

    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;
    }
    Last edited by C++Newbie; 03-21-2002 at 04:39 PM.

  2. #2
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    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.

  3. #3
    Registered User
    Join Date
    Dec 2001
    Posts
    421
    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 .

    U.
    Quidquid latine dictum sit, altum sonatur.
    Whatever is said in Latin sounds profound.

  4. #4
    Registered User
    Join Date
    Nov 2001
    Posts
    10

    Angry binary Tree search

    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.

  5. #5
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

  6. #6
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    >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.

  7. #7
    Registered User
    Join Date
    Apr 2011
    Posts
    1

    Post need help in binary search tree

    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.

  8. #8
    www.entropysink.com
    Join Date
    Feb 2002
    Posts
    603
    Nine years almost to the day? Holy thread bump batman!
    Visit entropysink.com - It's what your PC is made for!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 09:11 AM
  3. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  4. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 10:18 AM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM