Write down the code for binary search tree in c++?, C/C++ Programming

A: BinarySearchTree.h

----------------------

#ifndef BINARY_SEARCH_TREE_H_

#define BINARY_SEARCH_TREE_H_

#include "dsexceptions.h"

#include // For NULL

// Binary node & forward declaration since g++ does

// not understand nested classes. template

class BinarySearchTree;

template

class BinaryNode

{

Corresponding element; BinaryNode *left; BinaryNode *right;

BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )

: element( theElement ), left( lt ), right( rt ) { }

friend class BinarySearchTree;

};

// BinarySearchTree class

//

// CONSTRUCTION: along with ITEM_NOT_FOUND object utilized to signal failed finds

//

// ********PUBLIC OPERATIONS**********

// void insert( x ) --> Insert x

// void remove( x ) --> Remove x

// Comparable find( x ) --> Return item that matches x

// Comparable findMin( ) --> Return smallest item

// Comparable findMax( ) --> Return largest item

// boolean isEmpty( ) --> if empty , Return true; else false

// void makeEmpty( ) --> Remove every items

// void printTree( ) --> Print tree into the sorted order

template

class BinarySearchTree

{

public:

explicit BinarySearchTree( const Comparable & notFound );

BinarySearchTree( const BinarySearchTree & rhs );

~BinarySearchTree( );

const Comparable & findMin( ) const;

const Comparable & findMax( ) const;

const Comparable & find( const Comparable & x ) const;

bool isEmpty( ) const;

void printTree( ) const;

void makeEmpty( );

void insert( const Comparable & x );

void remove( const Comparable & x );

const BinarySearchTree & operator=( const BinarySearchTree & rhs );

private: BinaryNode *root;

const Comparable ITEM_NOT_FOUND;

const Comparable & elementAt( BinaryNode *t ) const;

void insert( const Comparable & x, BinaryNode * & t ) const;

void remove( const Comparable & x, BinaryNode * & t ) const;

BinaryNode * findMin( BinaryNode *t ) const;

BinaryNode * findMax( BinaryNode *t ) const;

BinaryNode * find( const Comparable & x, BinaryNode *t ) const;

void makeEmpty( BinaryNode * & t ) const;

void printTree( BinaryNode *t ) const; BinaryNode * clone( BinaryNode *t ) const;

};

#endif

BinarySearchTree

--------------------

#include "BinarySearchTree.h"

#include

/**

* developed unbalanced binary search tree.

* Note down that all "matching" is depend on the < method.

*/

/**

* develop the tree.

*/

template

BinarySearchTree::BinarySearchTree( const Comparable & notFound ) :

root( NULL ), ITEM_NOT_FOUND( notFound )

{

}

/**

* Copy constructor.

*/ template BinarySearchTree::

BinarySearchTree( const BinarySearchTree & rhs ) :

root( NULL ), ITEM_NOT_FOUND( rhs.ITEM_NOT_FOUND )

{

*this = rhs;

}

/**

* Destructor for the tree.

*/ template BinarySearchTree::~BinarySearchTree( )

{

makeEmpty( );

}

/**

* Insert the value of x in the tree; duplicates are avoided.

*/

template

void BinarySearchTree::insert( const Comparable & x )

{

insert( x, root );

}

/**

* Remove x from the tree. If x is not found nothing is done

*/

template

void BinarySearchTree::remove( const Comparable & x )

{

remove( x, root );

}

/**

* In the tree determine the smallest item.

* Return smallest item or ITEM_NOT_FOUND if empty.

*/

template

const Comparable & BinarySearchTree::findMin( ) const

{

return elementAt( findMin( root ) );

}

/**

* Determine the largest item in the tree.

* if empty , then Return the largest item of ITEM_NOT_FOUND

*/

template

const Comparable & BinarySearchTree::findMax( ) const

{

return elementAt( findMax( root ) );

}

/**

* Find item x in the tree.

* Return the matching item or ITEM_NOT_FOUND if not found.

*/

template

const Comparable & BinarySearchTree::

find( const Comparable & x ) const

{

return element At( find( x, root ) );

}

/**

* Make tree logically empty.

*/

template

void BinarySearchTree::makeEmpty( )

{

makeEmpty( root );

}

/**

* Test if the tree is logically empty.

* Return true if empty, or else false.

*/

template

bool BinarySearchTree::isEmpty( ) const

{

return root == NULL;

}

/**

* Write tree contents in sorted order.

*/

template

void BinarySearchTree::printTree( ) const

{

if( isEmpty( ) )

cout << "Empty tree" << endl;

else

printTree( root );

}

/**

* Deep copy.

*/

template

const BinarySearchTree & BinarySearchTree::

operator=( const BinarySearchTree & rhs )

{

if( this != &rhs )

{

makeEmpty( );

root = clone( rhs.root );

}

return *this;

}

/**

* Internal method to obtain element field in node t.

* Return element field or ITEM_NOT_FOUND if t is NULL.

*/

template

const Comparable & BinarySearchTree::

elementAt( BinaryNode *t ) const

{

if( t == NULL )

return ITEM_NOT_FOUND;

else

return t->element;

}

/**

* Internal method to insert in subtree.

* x is the item to insert.

* t is the node that roots the tree.

* Set the new root.

*/

template

void BinarySearchTree::

insert( const Comparable & x, BinaryNode * & t ) const

{

if( t == NULL )

t = new BinaryNode( x, NULL, NULL );

else if( x < t->element )

insert( x, t->left );

else if( t->element < x )

insert( x, t->right );

else

; // Duplicate; do nothing

}

/**

* Internal method to eliminate from a subtree.

* x is the item to eliminate.

* t is the node that roots the tree.

* Set the new root.

*/

template

void BinarySearchTree::

remove( const Comparable & x, BinaryNode * & t ) const

{

if( t == NULL )

return; // Item not found; if( x < t->element ) , do nothing

remove( x, t->left );

else if( t->element < x )

remove( x, t->right );

else if( t->left != NULL && t->right != NULL ) // Two children

{

t->element = findMin( t->right )->element;

remove( t->element, t->right );

}

else

{

BinaryNode *oldNode = t;

t = ( t->left != NULL ) ? t->left : t->right;

delete oldNode;

}

}

/**

* Internal method to determine the smallest item in a subtree t.

* Return node containing the smallest item.

*/ template BinaryNode *

BinarySearchTree::findMin( BinaryNode *t ) const

{

if( t == NULL )

return NULL;

if( t->left == NULL )

return t;

return findMin( t->left );

}

 

/**

* Internal method to determine the largest item in a subtree t.

* Return node having the largest item.

*/ template BinaryNode *

BinarySearchTree::findMax( BinaryNode *t ) const

{

if( t != NULL )

while( t->right != NULL )

t = t->right;

return t;

}

/**

* Internal method to determine an item in a subtree.

* x is item to look for.

* t is the node which roots the tree.

* Return node having the matched item.

*/ template BinaryNode * BinarySearchTree::

find( const Comparable & x, BinaryNode *t ) const

{

if( t == NULL )

return NULL;

else if( x < t->element ) return find( x, t->left );

else if( t->element < x ) return find( x, t->right );

 else

return t; // Match

}

/****** NONRECURSIVE VERSION*****************

template BinaryNode * BinarySearchTree::

find( const Comparable & x, BinaryNode *t ) const

{

while( t != NULL ) if( x < t->element ) t = t->left;

else if( t->element < x )

t = t->right;

else

return t; // Match

 

return NULL; // No match

}

*****************/

/**

* to make subtree empty , internal method.

*/

template

void BinarySearchTree::

makeEmpty( BinaryNode * & t ) const

{

if( t != NULL )

{

makeEmpty( t->left ); makeEmpty( t->right ); delete t;

}

t = NULL;

}

 

/**

* Internal method to write a sub tree rooted at t in sorted order.

*/

template

void BinarySearchTree::printTree( BinaryNode *t ) const

{

if( t != NULL )

{

printTree( t->left );

cout << t->element << endl;

printTree( t->right );

}

}

 

/**

* Internal method to duplicate subtree.

*/ template BinaryNode *

BinarySearchTree::clone( BinaryNode * t ) const

{

if( t == NULL ) return NULL;

else

return new BinaryNode( t->element, clone( t->left ), clone( t->right ) );

}

Test Binary Search Tree

------------------------

#include

#include "BinarySearchTree.h"

// Test program int main( )

{

const int ITEM_NOT_FOUND = -9999; BinarySearchTree t( ITEM_NOT_FOUND );

int NUMS = 4000;

const int GAP = 37;

int i;

cout << "Checking... (no more output means success)" << endl;

for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )

t.insert( i );

for( i = 1; i < NUMS; i+= 2 )

t.remove( i );

if( NUMS < 40 )

t.printTree( );

if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )

cout << "FindMin or FindMax error!" << endl;

for( i = 2; i < NUMS; i+=2 )

if( t.find( i ) != i )

cout << "Find error1!" << endl;

for( i = 1; i < NUMS; i+=2 )

{

if( t.find( i ) != ITEM_NOT_FOUND )

cout << "Find error2!" << endl;

}

BinarySearchTree t2( ITEM_NOT_FOUND );

t2 = t;

for( i = 2; i < NUMS; i+=2 )

if( t2.find( i ) != i )

cout << "Find error1!" << endl;

for( i = 1; i < NUMS; i+=2 )

{

if( t2.find( i ) != ITEM_NOT_FOUND )

cout << "Find error2!" << endl;

}

return 0;

}

#      

 

Posted Date: 3/20/2013 4:00:15 AM | Location : United States







Related Discussions:- Write down the code for binary search tree in c++?, Assignment Help, Ask Question on Write down the code for binary search tree in c++?, Get Answer, Expert's Help, Write down the code for binary search tree in c++? Discussions

Write discussion on Write down the code for binary search tree in c++?
Your posts are moderated
Related Questions
direction[] = {L,R,R,L,L,R,R,R,R,L,Z} length[]= {2,2,1,1,1,2,5,2,2,3,1}

Greatest Common Divisor (GCD) - The greatest common divisor (GCD) of two integers is the largest integer that will evenly divide both integers. The GCD algorithm involves intege

write a program that counts the number of occurrences of the string in the n-th padovan string p(n)   program 1 : package test.padovanstring; public class PadovanString {

The Malt Shop restaurant charges $2.99 for burgers, $1.29 for fries, and $1.25 for sodas.  Write a program that allows a restaurant employee to enter an order (the number of bur

The new and delete operators The C language has explained library functions- malloc() and free() for dynamic allocation and de-allocation of memory. C++ gives yet another appro

The heart of the modern electronic system is the microprocessor e.g. the video, sound, game consoles, portable phones and domestic appliances. Let us consider the heart of a home c

Templates permit to create generic functions that admit any data type as parameters and return value without having to overload the function with all the possible data types. Until

program for lexicographically precedes the given input permutation


claculate 5% tax >10000 sal