Write a C++ program to validate computer user-ids and passwords. A list of valid ids and passwords (unsorted) is read from a file and stored in a Binary Search Tree (BST) of UserInfo objects. When user-ids and passwords are entered during execution, this BST is searched to determine whether they are legal. Input (file): UserInfo records for valid users Input (keyboard): Ids and passwords of users logging in Output (screen): Messages indicating whether user-ids and passwords are valid, as well as an alphabetical listing of all valid ids and passwords at the end of the run.

Note: you will need to overload >>, <<, ==, and < operators in the UserInfo class in order to accomplish this task.

BST.h class is on Blackboard. You may ONLY modify the search function.

this is the BST.h file. i need the lab done by editing the this file.

/* BST.h contains the declaration of class template BST.

Basic operations:

Constructor: Constructs an empty BST

empty: Checks if a BST is empty

search: Search a BST for an item

insert: Inserts a value into a BST

remove: Removes a value from a BST

inorder: Inorder traversal of a BST -- output the data values

Private utility helper operations:

search2: Used by delete

inorderAux: Used by inorder

Other operations:

destructor

copy constructor

assignment operator

preorder, postorder, and level-by-level traversals

level finder

Note: Execution terminates if memory isn't available for a new BST node.

---------------------------------------------------------------------------*/

#include

using namespace std;

#ifndef BINARY_SEARCH_TREE

#define BINARY_SEARCH_TREE

template

class BST

{

public:

/***** Function Members *****/

BST();

/*------------------------------------------------------------------------

Construct a BST object.

Precondition: None.

Postcondition: An empty BST has been constructed.

-----------------------------------------------------------------------*/

bool empty() const;

/*------------------------------------------------------------------------

Check if BST is empty.

Precondition: None.

Postcondition: Returns true if BST is empty and false otherwise.

-----------------------------------------------------------------------*/

bool search(const DataType & item) const;

/*------------------------------------------------------------------------

Search the BST for item.

Precondition: None.

Postcondition: Returns true if item found, and false otherwise.

-----------------------------------------------------------------------*/

void insert(const DataType & item);

/*------------------------------------------------------------------------

Insert item into BST.

Precondition: None.

Postcondition: BST has been modified with item inserted at proper

position to maintain BST property.

------------------------------------------------------------------------*/

void remove(const DataType & item);

/*------------------------------------------------------------------------

Remove item from BST.

Precondition: None.

Postcondition: BST has been modified with item removed (if present);

BST property is maintained.

Note: remove uses auxiliary function search2() to locate the node

containing item and its parent.

------------------------------------------------------------------------*/

void inorder(ostream & out) const;

/*------------------------------------------------------------------------

Inorder traversal of BST.

Precondition: ostream out is open.

Postcondition: BST has been inorder traversed and values in nodes

have been output to out.

Note: inorder uses private auxiliary function inorderAux().

------------------------------------------------------------------------*/

private:

/***** Node class *****/

class BinNode

{

public:

DataType data;

BinNode * left;

BinNode * right;

// BinNode constructors

// Default -- data part is default DataType value; both links are null.

BinNode()

{

left = 0;

right = 0;}

// Explicit Value -- data part contains item; both links are null.

BinNode(DataType item)

{

data = item;

left = 0;

right = 0;

}

};// end of class BinNode declaration

typedef BinNode * BinNodePointer;

/***** Private Function Members *****/

void search2(const DataType & item, bool & found,

BinNodePointer & locptr, BinNodePointer & parent) const;

/*------------------------------------------------------------------------

Locate a node containing item and its parent.

Precondition: None.

Postcondition: locptr points to node containing item or is null if

not found, and parent points to its parent.#include

------------------------------------------------------------------------*/

void inorderAux(ostream & out,

BinNodePointer subtreePtr) const;

/*------------------------------------------------------------------------

Inorder traversal auxiliary function.

Precondition: ostream out is open; subtreePtr points to a subtree

of this BST.

Postcondition: Subtree with root pointed to by subtreePtr has been

output to out.

------------------------------------------------------------------------*/

/***** Data Members *****/

BinNodePointer myRoot;

}; // end of class template declaration

//--- Definition of constructor

template

inline BST::BST()

{myRoot = 0;}

//--- Definition of empty()

template

inline bool BST::empty() const

{ return myRoot == 0; }

//--- Definition of search()

template

bool BST::search(const DataType & item) const

{

BinNodePointer locptr = myRoot;

bool found = false;

while (!found && locptr != 0)

{

if (item < locptr->data) // descend left

locptr = locptr->left;

else if (locptr->data < item) // descend right

locptr = locptr->right;

else // item found

found = true;

}

return found;

}

//--- Definition of insert()

template

inline void BST::insert(const DataType & item)

{

BinNodePointer

locptr = myRoot, // search pointer

parent = 0; // pointer to parent of current node

bool found = false; // indicates if item already in BST

while (!found && locptr != 0)

{

parent = locptr;

if (item < locptr->data) // descend left

locptr = locptr->left;

else if (locptr->data < item) // descend right

locptr = locptr->right;

else // item found

found = true;

}

if (!found)

{ // construct node containing item

locptr = new BinNode(item);

if (parent == 0) // empty tree

myRoot = locptr;

else if (item < parent->data ) // insert to left of parent

parent->left = locptr;

else // insert to right of parent

parent->right = locptr;

}

else

cout << "Item already in the tree ";

}

//--- Definition of remove()

template

void BST::remove(const DataType & item)

{

bool found; // signals if item is found

BinNodePointer

x, // points to node to be deleted

parent; // " " parent of x and xSucc

search2(item, found, x, parent);

if (!found)

{

cout << "Item not in the BST ";

return;

}

//else

if (x->left != 0 && x->right != 0)

{ // node has 2 children

// Find x's inorder successor and its parent

BinNodePointer xSucc = x->right;

parent = x;

while (xSucc->left != 0) // descend left

{

parent = xSucc;

xSucc = xSucc->left;

}

// Move contents of xSucc to x and change x

// to point to successor, which will be removed.

x->data = xSucc->data;

x = xSucc;

} // end if node has 2 children

// Now proceed with case where node has 0 or 2 child

BinNodePointer

subtree = x->left; // pointer to a subtree of x

if (subtree == 0)

subtree = x->right;

if (parent == 0) // root being removed

myRoot = subtree;

else if (parent->left == x) // left child of parent

parent->left = subtree;

else // right child of parent

parent->right = subtree;

delete x;

}

//--- Definition of inorder()

template

inline void BST::inorder(ostream & out) const

{

inorderAux(out, myRoot);

}

//--- Definition of search2()

template

void BST::search2(const DataType & item, bool & found,

BinNodePointer & locptr,

BinNodePointer & parent) const

{

locptr = myRoot;

parent = 0;

found = false;

while (!found && locptr != 0)

{

if (item < locptr->data) // descend left

{

parent = locptr;

locptr = locptr->left;

}

else if (locptr->data < item) // descend right

{

parent = locptr;

locptr = locptr->right;

}

else // item found

found = true;

}

}

//--- Definition of inorderAux()

template

void BST::inorderAux(ostream & out,

BinNodePointer subtreeRoot) const

{

if (subtreeRoot != 0)

{

inorderAux(out, subtreeRoot->left); // L operation

out << subtreeRoot->data << " "; // V operation

inorderAux(out, subtreeRoot->right); // R operation

}

}

#endif

and this is an extra file called recrusive BST search i think we can use it as well.

//--- Definition of search2() template void BST::search2(const DataType & item, bool & found) const { searchAUX(item, found, root); //begin searching at root } template void BST::searchAUX(const DataType & item, bool & found, BinNodePointer & locptr) const { if ( locptr == null ) // Failed to find found = false; // Base case 1 else if ( item < locptr->data ) // Down left searchAUX(item, found, locptr -> left); else if ( item > locptr->data ) // Down right searchAUX(item, found, locptr -> right); else // We FOUND it! found = true; // Base case 2 } 

we use c++. 

you can use any list of userid and passwords. they didnt provide any other lists beside all i posted.