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
Available, and the right kind of programs. My son wants to stop using ice. He has organised detox a number of times, and is always successful. It is the next stage, rehab, where

Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b. The area under a curve between two points can b

Write a program that predicts users’ age (0-128 years old) with at most 7 questions. The game starts with asking the user whether he/she is younger or older than G (an initial gues

Consider text comprised of sentences and sentences comprised of words. Words in a sentence will be space delimited. Given a text and K strings, task is to find out the number valid

Ask question #Minimum 100 words acceptedEducational Objectives: After completing this assignment, the student should be able to accomplish the following: Apply generic algorithms i

Help for tomorrow...?

Byteland county is very famous for luminous jewels. Luminous jewels are used in making beautiful necklaces. A necklace consists of various luminous jewels of particular colour. Nec

Aim: To implement a program for following string operations: Length of String. String Concatenation. Substring (provide start index and length) Find character a

Define a class? A: It is an expanded concept of a data structure: rather than holding only data, it can hold data and functions both.

Project Description: I will need a tutor that would help me out in Data Structure and learning Algorithm more at the mathematical/algorithmic level. The book is written by "by T