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
Custom Scans and Alerts Think or Swim Project Description: I am seeking somebody to make me several Custom Scans and Alerts on Thinkorswim TOS Skills required are C++ Prog

what is a string?


Q: What are some ways try / catch / throw can develop software quality? A: By removing one of the reasons for if statements. The commonly utilized alternative to try / catch

Polymorphism C++ supports this idea - that different objects do "the right thing "- by function polymorphism and class polymorphism. Poly means many, while morph means form.

A palindrome is a string that reads the same from both the ends. Given a string S convert it to a palindrome by doing character replacement. Your task is to convert S to palindrome

what is an array?

Addition of array elements: #define rows 3 #define cols 3 void main() {                 int i=0,j=0,sum=0;                 int arr[rows][cols];

Explain high-order and low-order bytes. - Numbers are written from left to right in decreasing order of significance. In the same way, bits in a byte of computer memory can be

Hi, I want to get rtsp source for windows