Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Sep 11, 2024

C++ program Using the linked approach implement the BST ADT, implement only the following functions in the BSTree.cpp: - constructor, copy constructor, assignment operator, destructor

C++ program

Using the linked approach implement the BST ADT, implement only the following functions in the BSTree.cpp:

- constructor, copy constructor, assignment operator, destructor

- insert, retrieve, remove, writeKeys

- clear, isEmpty

Note: Use recursive functions to traverse the tree.

Config.h

* Activate test 'N' by defining the corresponding LAB9_TESTN to have the value 1.

* Deactive test 'N' by setting the value to 0.

#define LAB9_TEST1 0 // Programming Exercise 2: getCount

#define LAB9_TEST2 0 // Programming Exercise 2: getHeight

#define LAB9_TEST3 0 // Programming Exercise 3: writeLessThan

BSTree.h

#ifndef BSTREE_H

#define BSTREE_H

#include

using namespace std;

template < typename DataType, class KeyType > // DataType : tree data item

class BSTree // KeyType : key field

{

public:

// Constructor

BSTree (); // Default constructor

BSTree ( const BSTree& other ); // Copy constructor

BSTree& operator= ( const BSTree& other );

// Overloaded assignment operator

// Destructor

~BSTree ();

// Binary search tree manipulation operations

void insert ( const DataType& newDataItem ); // Insert data item

bool retrieve ( const KeyType& searchKey, DataType& searchDataItem ) const;

// Retrieve data item

bool remove ( const KeyType& deleteKey ); // Remove data item

void writeKeys () const; // Output keys

void clear (); // Clear tree

// Binary search tree status operations

bool isEmpty () const; // Tree is empty

// !! isFull() has been retired. Not very useful in a linked structure.

// Output the tree structure -- used in testing/debugging

void showStructure () const;

// In-lab operations

int getHeight () const; // Height of tree

int getCount () const; // Number of nodes in tree

void writeLessThan ( const KeyType& searchKey ) const; // Output keys < searchKey

protected:

class BSTreeNode // Inner class: facilitator for the BSTree class

{

public:

// Constructor

BSTreeNode ( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr );

// Data members

DataType dataItem; // Binary search tree data item

BSTreeNode *left, // Pointer to the left child

*right; // Pointer to the right child

};

// Recursive helpers for the public member functions -- insert

// prototypes of these functions here.

void insertHelper ( BSTreeNode *&p, const DataType &newDataItem );

bool retrieveHelper ( BSTreeNode *p, const KeyType& searchKey, DataType &searchDataItem ) const;

bool removeHelper ( BSTreeNode *&p, const KeyType& deleteKey );

// cutRightmose used in one implementation of remove.

void cutRightmost ( BSTreeNode *&r, BSTreeNode *&delPtr );

void writeKeysHelper ( BSTreeNode *p ) const;

void clearHelper ( BSTreeNode *p );

void showHelper ( BSTreeNode *p, int level ) const;

int getHeightHelper ( BSTreeNode *p ) const;

int getCountHelper ( BSTreeNode *p ) const;

void writeLTHelper ( BSTreeNode *p, const KeyType& searchKey ) const;

void copyTree ( const BSTree &otherTree );

void copyTreeHelper ( BSTreeNode *&p, const BSTreeNode *otherPtr );

// Data member

BSTreeNode *root; // Pointer to the root node

};

#endif // define BSTREE_H

BSTree.cpp

#include "BSTree.h"

template

BSTree::BSTreeNode::BSTreeNode ( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr )

{

}