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
I Want a answer for solving the big M method in the topic of simplex method...

Define some features of static storage class in c program? The features of a variable defined to contain a static storage class are as follows. Storage - memory Default

Explain the terms- Substitutability and Extensibility Substitutability - The objects of a properly derived class can be safely and easily substituted for an object of its

Input Format: First line starts with T, which is the number of test cases. Each test case contains a string (S). Output Format: For each test case print the minimum number of ch

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

Each function has its own stack frame between %fp and %sp. Let Caller calls Callee. Then Caller's %sp becomes callee's %fp, and callee's %sp set to be a new value (a smaller one be


Program to find a Greatest String: C - Program: Write a program find largest string by c program. int main( int argc, char *argv[] ) {     if( argc         {

Define Generic Bitwise Operations? Bitwise operators only work on an incomplete number of types int and char. It turns out there's above one kind of int. In particular there's

An employee’s total weekly pay equals the hourly wage multiplied by the total number of regular hours plus any overtime pay. Overtime pay equals the total overtime hours multiplied