Question
implement Pre-order, Post-order and Breadth-First traversals. (No In-order here) Moreover, when balanced-factor and rotations have been appled into a BSTree class, a self-balanced BSTree (AVL
implement Pre-order, Post-order and Breadth-First traversals. (No In-order here) Moreover, when balanced-factor and rotations have been appled into a BSTree class, a self-balanced BSTree (AVL Tree) can be created. Therefore, the 2nd part of this assignment is to add this new feature self-balance into the existing BSTree class to make it behaves like an AVL Tree.
write C++ methods to implement traversals of a Binary Search Tree (BSTree) and to write (or re-write) C++ methods to make it as an (AVL Tree).
re-write the method insert and remove in BSTree.h to make sure they work properly in the self-balanced BSTree (AVL Tree).
Add these under the public access specifier in the BSTree.h class declaration
void preOrder() const;
void postOrder() const;
void breadthFirstOrder() const;
//=== AVLTree Methods===
//calculate balanceFactor (with sign)
int balanceFactor() const;
// balance() called by void insert ( const DataType& newDataItem ) and bool remove ( const KeyType& deleteKey ) void balance(); void LLRotation(); //called by balance() void LRRotation(); //called by balance() void RRRotation(); //called by balance() void RLRotation(); //called by balance()
Height and Count also do not work and need to be adjusted to work
BSTree.h
#ifndef BSTREE_H #define BSTREE_H
#include #include #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
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 ); // cutRightmost 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 copyTree ( const BSTree &otherTree ); void copyTreeHelper ( BSTreeNode *&p, const BSTreeNode *otherPtr );
// Data member BSTreeNode *root; // Pointer to the root node };
//-------------------------------------------------------------------- // // Laboratory BSTree.cpp // // ** Linked implementation of the Binary Search Tree ADT ** // //--------------------------------------------------------------------
//--------------------------------------------------------------------
template < typename DataType, typename KeyType > BSTree:: BSTreeNode :: BSTreeNode ( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr )
// Creates a binary search tree node containing data item elem, left // child pointer leftPtr, and right child pointer rightPtr.
: dataItem(nodeDataItem), left(leftPtr), right(rightPtr)
{}
//--------------------------------------------------------------------
template < typename DataType, typename KeyType > BSTree:: BSTree ()
// Creates an empty tree.
: root(0)
{}
//--------------------------------------------------------------------
template < typename DataType, typename KeyType > BSTree:: BSTree ( const BSTree &source )
// Creates an empty tree.
: root(0)
{ copyTree(source); }
//--------------------------------------------------------------------
template < typename DataType, typename KeyType > BSTree& BSTree:: operator= ( const BSTree &sourceTree )
// Sets a tree to be equivalent to the tree "source".
{ // Avoid accidentally trying to set object to itself. // Calling clear() on an object, then copying the deleted data doesn't work. // Although this may seems like overkill and an unlikely scenario, it can happen, if( this != &sourceTree ) { clear(); copyTree(sourceTree); return *this; } else { return *this; } }
//--------------------------------------------------------------------
template < typename DataType, typename KeyType > void BSTree:: copyTree ( const BSTree &sourceTree )
// Sets a tree to be equivalent to the tree "source".
{ copyTreeHelper( root, sourceTree.root ); }
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType > void BSTree:: copyTreeHelper ( BSTreeNode *&p, const BSTreeNode *sourcePtr )
// Recursive helper function that helps set a tree to be equivalent to another tree.
{ if( p != 0 ) { p = new BSTreeNode( sourcePtr->DataItem, 0, 0 ); copyTreeHelper( p->left, sourcePtr->left ); copyTreeHelper( p->right, sourcePtr->right ); } }
//-------------------------------------------------------------------- template < typename DataType, typename KeyType > BSTree:: ~BSTree ()
// Frees the memory used by a tree.
{ clear(); }
//--------------------------------------------------------------------
template < typename DataType, typename KeyType > void BSTree:: insert ( const DataType &newDataItem )
// Inserts newDataItem into a tree. If an data item with the same key // as newDataItem already exists in the tree, then updates that // data item's data with newDataItem's data.
{ insertHelper(root, newDataItem); }
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType > void BSTree:: insertHelper ( BSTreeNode *&p, const DataType &newDataItem )
// Recursive helper function for insert. Inserts newDataItem in // the subtree pointed to by p.
{ if ( p == 0 ) // Insert p = new BSTreeNode(newDataItem,0,0); else if ( newDataItem.getKey() < p->dataItem.getKey() ) insertHelper(p->left, newDataItem); // Search left else if ( newDataItem.getKey() > p->dataItem.getKey() ) insertHelper(p->right, newDataItem); // Search right else p->dataItem = newDataItem; // Update }
//--------------------------------------------------------------------
template < typename DataType, typename KeyType > bool BSTree:: retrieve ( const KeyType& searchKey, DataType &searchDataItem ) const
// Searches a tree for the data item with key searchKey. If the data item // is found, then copies the data item to searchDataItem and returns true. // Otherwise, returns false with searchDataItem undefined.
{ return retrieveHelper(root,searchKey,searchDataItem); }
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType > bool BSTree:: retrieveHelper ( BSTreeNode *p, const KeyType& searchKey, DataType &searchDataItem ) const
// Recursive helper function for retrieve. Searches the subtree // pointed to by p.
{ bool result; // Result returned
if ( p == 0 ) { // Fell off the tree while searching. Item is not in tree. result = false; } else if ( searchKey < p->dataItem.getKey() ) { // Key is smaller than current node. Search to left. result = retrieveHelper(p->left,searchKey,searchDataItem); } else if ( searchKey > p->dataItem.getKey() ) { // Key is larger than current node. Search to right. result = retrieveHelper(p->right,searchKey,searchDataItem); } else { // Found the desired item searchDataItem = p->dataItem; result = true; }
return result; }
//--------------------------------------------------------------------
template < typename DataType, typename KeyType > bool BSTree:: remove ( const KeyType& deleteKey )
// Removes the data item with key deleteKey from a tree. If the // data item is found, then deletes it from the tree and returns true. // Otherwise, returns false.
{ return removeHelper(root,deleteKey); }
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType > bool BSTree:: removeHelper ( BSTreeNode *&p, const KeyType& deleteKey )
// Recursive helper function for remove. Searches the subtree // pointed to by p for the node with key deleteKey. If this node is // found, then does one of the following: // // - If the node is missing one or more children, then links // around it and deletes it. // // - Otherwise, uses cutRightmost to replace the data in the // node with the data in the rightmost descendant of the node's // left child and deletes that node.
{ BSTreeNode *delPtr; // Pointer to node to delete bool result; // Result returned
if ( p == 0 ) result = false; // Search failed else if ( deleteKey < p->dataItem.getKey() ) result = removeHelper(p->left,deleteKey); // Search left else if ( deleteKey > p->dataItem.getKey() ) result = removeHelper(p->right,deleteKey); // Search right else { // Found delPtr = p; if ( p->left == 0 ) { p = p->right; // No left child delete delPtr; } else if ( p->right == 0 ) { p = p->left; // No right child delete delPtr; } else // Node has both children: removing is more complex. {
// ** Start implemtation option #1 // Find node with largest key smaller than p's key. BSTreeNode* temp = p->left; while( temp->right ) { temp = temp->right; } // Copy node data to p p->dataItem = temp->dataItem; // And remove the node whose data was copied to p. removeHelper( p->left, temp->dataItem.getKey());
/* // ** Start implemtation option #2. Looks simpler here, // but there is all of cutRightmost to deal with. cutRightmost(p->left,delPtr); delete delPtr; */ } result = true; }
return result; }
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType > void BSTree:: cutRightmost ( BSTreeNode *&r, BSTreeNode *&delPtr )
// Recursive helper function for removeHelper in implementation // option #2. Traces down a sequence of right children. Copies the // data from the last node in the sequence into the node pointed // to delPtr, sets delPtr to point to the last node in the sequence, // and links around this node.
{ if ( r->right != 0 ) cutRightmost(r->right,delPtr); // Continue down to the right else { delPtr->dataItem = r->dataItem; delPtr = r; r = r->left; } }
//--------------------------------------------------------------------
template < typename DataType, typename KeyType > void BSTree:: writeKeys () const
// Outputs the keys in a tree in ascending order.
{ writeKeysHelper(root); cout << endl; }
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType > void BSTree:: writeKeysHelper ( BSTreeNode *p ) const
// Recursive helper for writeKeys. // Outputs the keys in the subtree pointed to by p.
{ if ( p != 0 ) { writeKeysHelper(p->left); cout << p->dataItem.getKey() << " "; writeKeysHelper(p->right); } }
//--------------------------------------------------------------------
template < typename DataType, typename KeyType > void BSTree:: clear ()
// Removes all the nodes from a tree.
{ clearHelper(root); root = 0; }
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType > void BSTree:: clearHelper ( BSTreeNode *p )
// Recursive helper for clear. Clears the subtree pointed to by p.
{ if ( p != 0 ) { // Use post-order traversal. Otherwise get into trouble by // referencing p->left and/or p->right after p had been deallocated. clearHelper(p->left); clearHelper(p->right); delete p; } }
//--------------------------------------------------------------------
template < typename DataType, typename KeyType > bool BSTree:: isEmpty () const
// Returns true if a tree is empty. Otherwise returns false.
{ return root == 0; }
//--------------------------------------------------------------------
template < typename DataType, typename KeyType > void BSTree:: showStructure () const
// Outputs the keys in a binary search tree. The tree is output // rotated counterclockwise 90 degrees from its conventional // orientation using a "reverse" inorder traversal. This operation is // intended for testing and debugging purposes only.
{ if ( root == 0 ) cout << "Empty tree" << endl; else { cout << endl; showHelper(root,1); cout << endl; } }
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType > void BSTree:: showHelper ( BSTreeNode *p, int level ) const
// Recursive helper for showStructure. // Outputs the subtree whose root node is pointed to by p. // Parameter level is the level of this node within the tree.
{ int j; // Loop counter
if ( p != 0 ) { showHelper(p->right,level+1); // Output right subtree for ( j = 0 ; j < level ; j++ ) // Tab over to level cout << "\t"; cout << " " << p->dataItem.getKey(); // Output key if ( ( p->left != 0 ) && // Output "connector" ( p->right != 0 ) ) cout << "<"; else if ( p->right != 0 ) cout << "/"; else if ( p->left != 0 ) cout << "\\"; cout << endl; showHelper(p->left,level+1); // Output left subtree } }
//-------------------------------------------------------------------- // In lab Programming Exercise //--------------------------------------------------------------------
template < typename DataType, typename KeyType > int BSTree:: getHeight () const
// Returns the height of a tree.
{ return getHeightHelper(root); }
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType > int BSTree:: getHeightHelper ( BSTreeNode *p ) const
// Recursive helper for height. Returns the height of // the subtree pointed to by p -- that is, the length of the longest // path from the node pointed to by p to any leaf node.
{ int l, // Length of the longest path through the left child r, // Length of the longest path through the right child result; // Result returned
if ( p == 0 ) { result = -1; // Empty tree }
// add code here to get height of left subtree // add code here to get height of right subtree // the height is of this node is the larger of the two // plus extra height for this node
//return the result }
template < typename DataType, typename KeyType > int BSTree:: getCount () const
// Returns the number of nodes in the tree
{ return getCountHelper(root); }
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType > int BSTree:: getCountHelper ( BSTreeNode *p ) const
// Recursive partner of the getCount() function. // Add code to Returns the count of // the subtree pointed to by p -- that is, the number of nodes in the // left child + number of nodes in the right child + 1
{
}
#endif // #ifdef BSTREE_H
test.cpp
#include using namespace std; #include "BSTree.h"
void print_help();
//-------------------------------------------------------------------- // Declaration for the binary search tree data item class //--------------------------------------------------------------------
class TestData { public:
void setKey ( int newKey ) { keyField = newKey; } // Set the key
int getKey () const { return keyField; } // Returns the key
private:
int keyField; // Key for the data item };
int main() { BSTree testTree; // Test binary search tree TestData testData; // Binary search tree data item int inputKey; // User input key char cmd; // Input command
print_help();
do { testTree.showStructure(); // Output tree
cout << endl << "Command: "; // Read command cin >> cmd; if ( cmd == '+' || cmd == '?' || cmd == '-' || cmd == '<' ) cin >> inputKey;
switch ( cmd ) { case 'P' : case 'p' : print_help(); break;
case '+' : // insert testData.setKey(inputKey); cout << "Insert : key = " << testData.getKey() << endl; testTree.insert(testData); break;
case '?' : // retrieve if ( testTree.retrieve(inputKey,testData) ) cout << "Retrieved : getKey = " << testData.getKey() << endl; else cout << "Not found" << endl; break;
case '-' : // remove if ( testTree.remove(inputKey) ) cout << "Removed data item" << endl; else cout << "Not found" << endl; break;
case 'K' : case 'k' : // writeKeys cout << "Keys:" << endl; testTree.writeKeys(); break;
case 'C' : case 'c' : // clear cout << "Clear the tree" << endl; testTree.clear(); break;
case 'E' : case 'e' : // empty if ( testTree.isEmpty() ) cout << "Tree is empty" << endl; else cout << "Tree is NOT empty" << endl; break;
case 'G' : case 'g' : // Programming Exercise cout << "Tree nodes count = " << testTree.getCount() << endl; break;
case 'H' : case 'h' : // Programming Exercise cout << "Tree height = " << testTree.getHeight() << endl; break;
case 'Q' : case 'q' : // Quit test program break;
default : // Invalid command cout << "Inactive or invalid command. 'P' prints help." << endl; } } while ( cin && ( cmd != 'Q' ) && ( cmd != 'q' ) ); if ( !cin ) { cerr << "Error in console input. Exiting." << endl; }
return 0; }
//--------------------------------------------------------------------
void print_help() { cout << endl << "Commands:" << endl; cout << " P : [P]rint Help (displays this message)" << endl; cout << " +key : Insert (or update) data item (use integers)" << endl; cout << " ?key : Retrieve data item" << endl; cout << " -key : Remove data item" << endl; cout << " K : Write keys in ascending order" << endl; cout << " C : Clear the tree" << endl; cout << " E : Empty tree?" << endl; cout << " G : Get count of nodes " << "Active : " << endl;
cout << " H : Height " << "Active : "<< endl;
cout << " Q : Quit the test program" << endl; cout << endl; }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started