You are to complete two features:

tree traversal and

avl balance (right and left) rotations.

Look for Fill the blank block comment as shown below:

// // fill the blank //

Test Run Example

Submit a test run screenshot using the test pattern below:

string input = "h,d,l,b,f,j,n,a,c,e,g,i,k,m,o";

Then test the 3 different traversal.

Submit

source program + validation test run (similar to the sample below).

There are 4 fill in the Blanks in this file. Line 326 BinaryNodeTree class, traversal methods: preorder() and postorder() , Line 577 AVLtree class leftRotate() method. Make sure change line 591 back to return y; Line 707, of theAVLtree class removeNode method(), the four AVL rotation utilities: R-R, R-L, L-R, and L-L rotations. And Line 741.

AVLtree.h

#ifndef AVL_TREE

#define AVL_TREE

#include

#include

#include

//////////////////////

// BinaryNode

//////////////////////

template

class BinaryNode

{

private:

ItemType item; // Data portion

BinaryNode* leftChildPtr; // Pointer to left child

BinaryNode* rightChildPtr; // Pointer to right child

int height; // required by an AVL Tree Node

public:

BinaryNode()

: item(nullptr), leftChildPtr(nullptr), rightChildPtr(nullptr), height(1) {}

BinaryNode(const ItemType& anItem)

:item(anItem), leftChildPtr(nullptr), rightChildPtr(nullptr), height(1) {}

BinaryNode(const ItemType& anItem,

BinaryNode* leftPtr,

BinaryNode* rightPtr)

: item(anItem), leftChildPtr(leftPtr), rightChildPtr(rightPtr), height(1) {}

void setItem(const ItemType& anItem) {item = anItem;}

ItemType getItem() const {return item;}

bool isLeaf() const {

return ((leftChildPtr == nullptr) && (rightChildPtr == nullptr));

}

BinaryNode* getLeftChildPtr() const {return leftChildPtr;}

BinaryNode* getRightChildPtr() const {return rightChildPtr;}

void setLeftChildPtr(BinaryNode* leftPtr) {leftChildPtr = leftPtr;}

void setRightChildPtr(BinaryNode* rightPtr) {rightChildPtr = rightPtr;}

void drawTree(BinaryNode* , std::string , std::string) const;

int getHeight() const {return height;}

void setHeight(int h) {height = h;}

}; // end BinaryNode

////////////////////////////

// BinaryNodeTree Class

////////////////////////////

template

class BinaryNodeTree

{

private:

BinaryNode* rootPtr;

protected:

//------------------------------------------------------------

// Protected Utility Methods Section:

// Recursive helper methods for the public methods.

//------------------------------------------------------------

int getHeightHelper(BinaryNode* subTreePtr) const;

int getNumberOfNodesHelper(BinaryNode* subTreePtr) const ;

// Recursively deletes all nodes from the tree.

void destroyTree(BinaryNode* subTreePtr);

// Recursively adds a new node to the tree in a left/right fashion to

// keep the tree balanced.

BinaryNode* balancedAdd(BinaryNode* subTreePtr,

BinaryNode* newNodePtr);

// Removes the target value from the tree by calling moveValuesUpTree

// to overwrite value with value from child.

BinaryNode* removeValue(BinaryNode* subTreePtr,

const ItemType target,

bool& success);

// Copies values up the tree to overwrite value in current node until

// a leaf is reached; the leaf is then removed, since its value is

// stored in the parent.

BinaryNode* moveValuesUpTree(BinaryNode* subTreePtr);

// Recursively searches for target value in the tree by using a

// preorder traversal.

BinaryNode* findNode(BinaryNode* treePtr,

const ItemType& target,

bool& success) const;

// Copies the tree rooted at treePtr and returns a pointer to

// the copy.

BinaryNode* copyTree(const BinaryNode* treePtr) const;

// Recursive traversal helper methods:

void preorder(void visit(ItemType&), BinaryNode* treePtr) const;

void inorder(void visit(ItemType&), BinaryNode* treePtr) const;

void postorder(void visit(ItemType&), BinaryNode* treePtr) const;

public:

//------------------------------------------------------------

// Constructor and Destructor Section.

//------------------------------------------------------------

BinaryNodeTree() : rootPtr(nullptr) {}

BinaryNodeTree(const ItemType& rootItem) {

rootPtr = new BinaryNode(rootItem, nullptr, nullptr);

}

BinaryNodeTree(const ItemType& rootItem,

const BinaryNodeTree* leftTreePtr,

const BinaryNodeTree* rightTreePtr) {

rootPtr = new BinaryNode(rootItem,

copyTree(leftTreePtr->rootPtr),

copyTree(rightTreePtr->rootPtr));

}

BinaryNodeTree(const BinaryNodeTree& tree) {

rootPtr = copyTree(tree.rootPtr);

}

virtual ~BinaryNodeTree() {destroyTree(rootPtr);}

//------------------------------------------------------------

// Public BinaryTreeInterface Methods Section.

//------------------------------------------------------------

bool isEmpty() const {return rootPtr == nullptr;}

int getHeight() const {return getHeightHelper(rootPtr);}

int getNumberOfNodes() const {

return getNumberOfNodesHelper(rootPtr);

}

ItemType getRootData() const;

void setRootData(const ItemType& newData);

bool add(const ItemType& newData); // Adds a node

bool remove(const ItemType& data); // Removes a node

void clear() {destroyTree(rootPtr);rootPtr = nullptr;}

ItemType getEntry(const ItemType& anEntry) const;

bool contains(const ItemType& anEntry) const;

void drawTree(BinaryNode* treePtr, std::string lpad, std::string rpad) const;

//------------------------------------------------------------

// Public Traversals Section.

//------------------------------------------------------------

void preorderTraverse(void visit(ItemType&)) const {

preorder(visit, rootPtr);

}

void inorderTraverse(void visit(ItemType&)) const {

inorder(visit, rootPtr);

}

void postorderTraverse(void visit(ItemType&)) const {

postorder(visit, rootPtr);

}

//------------------------------------------------------------

// Overloaded Operator Section.

//------------------------------------------------------------

BinaryNodeTree& operator=(const BinaryNodeTree& rightHandSide);

}; // end BinaryNodeTree

//////////////////////////////////////////////////////////////

// Protected Utility Methods Section

//////////////////////////////////////////////////////////////

template

int BinaryNodeTree::getHeightHelper(BinaryNode* subTreePtr) const

{

if (subTreePtr == nullptr)

return 0;

else

return 1 + std::max(getHeightHelper(subTreePtr->getLeftChildPtr()),

getHeightHelper(subTreePtr->getRightChildPtr()));

} // end getHeightHelper

template

int BinaryNodeTree::getNumberOfNodesHelper(BinaryNode* subTreePtr) const

{

if (subTreePtr == nullptr)

return 0;

else

return 1 + getNumberOfNodesHelper(subTreePtr->getLeftChildPtr())

+ getNumberOfNodesHelper(subTreePtr->getRightChildPtr());

} // end getNumberOfNodesHelper

template

BinaryNode* BinaryNodeTree::balancedAdd(BinaryNode* subTreePtr,

BinaryNode* newNodePtr)

{

if (subTreePtr == nullptr)

return newNodePtr;

else

{

BinaryNode* leftPtr = subTreePtr->getLeftChildPtr();

BinaryNode* rightPtr = subTreePtr->getRightChildPtr();

if (getHeightHelper(leftPtr) > getHeightHelper(rightPtr))

{

rightPtr = balancedAdd(rightPtr , newNodePtr);

subTreePtr->setRightChildPtr(rightPtr );

}

else

{

leftPtr = balancedAdd(leftPtr, newNodePtr);

subTreePtr->setLeftChildPtr(leftPtr);

} // end if

return subTreePtr;

} // end if

} // end balancedAdd

template

BinaryNode* BinaryNodeTree::moveValuesUpTree(BinaryNode* subTreePtr)

{

BinaryNode* leftPtr = subTreePtr->getLeftChildPtr();

BinaryNode* rightPtr = subTreePtr->getRightChildPtr();

int leftHeight = getHeightHelper(leftPtr);

int rightHeight = getHeightHelper(rightPtr);

if (leftHeight > rightHeight)

{

subTreePtr->setItem(leftPtr->getItem());

leftPtr = moveValuesUpTree(leftPtr);

subTreePtr->setLeftChildPtr(leftPtr);

return subTreePtr;

}

else

{

if (rightPtr != nullptr)

{

subTreePtr->setItem(rightPtr->getItem());

rightPtr =moveValuesUpTree(rightPtr);

subTreePtr->setRightChildPtr(rightPtr);

return subTreePtr;

}

else

{

//this was a leaf!

// value not important

delete subTreePtr;

return nullptr;

} // end if

} // end if

} // end moveValuesUpTree

/** Depth-first search of tree for item.

@param subTreePtr tree to search.

@param target target item to find.

@param success communicate to client we found it.

@returns A pointer to node containing the item. */

template

BinaryNode* BinaryNodeTree::removeValue(BinaryNode* subTreePtr,

const ItemType target,

bool& success)

{

if(subTreePtr == nullptr) // not found here

return nullptr;

if (subTreePtr->getItem() == target) // found it

{

subTreePtr = moveValuesUpTree(subTreePtr);

success = true;

return subTreePtr;

}

else

{

BinaryNode* targetNodePtr = removeValue(subTreePtr->getLeftChildPtr(), target, success);

subTreePtr->setLeftChildPtr(targetNodePtr);

if (!success) // no need to search right subTree

{

targetNodePtr = removeValue(subTreePtr->getRightChildPtr(), target, success);

subTreePtr->setRightChildPtr(targetNodePtr);

} // end if

return subTreePtr;

} // end if

} // end removeValue

template

BinaryNode* BinaryNodeTree::findNode(BinaryNode* treePtr,

const ItemType& target,

bool& success) const

{

if (treePtr == nullptr) // not found here

return nullptr;

if (treePtr->getItem() == target) // found it

{

success = true;

return treePtr;

}

else

{

BinaryNode* targetNodePtr = findNode(treePtr->getLeftChildPtr(), target, success);

if (!success) // no need to search right subTree

{

targetNodePtr = findNode(treePtr->getRightChildPtr(), target, success);

} // end if

return targetNodePtr;

} // end if

} // end findNode

template

BinaryNode* BinaryNodeTree::copyTree(const BinaryNode* treePtr) const

{

BinaryNode* newTreePtr = nullptr;

// Copy tree nodes during a preorder traversal

if (treePtr != nullptr)

{

// Copy node

newTreePtr = new BinaryNode(treePtr->getItem(), nullptr, nullptr);

newTreePtr->setLeftChildPtr(copyTree(treePtr->getLeftChildPtr()));

newTreePtr->setRightChildPtr(copyTree(treePtr->getRightChildPtr()));

} // end if

return newTreePtr;

} // end copyTree

template

void BinaryNodeTree::destroyTree(BinaryNode* subTreePtr)

{

if (subTreePtr != nullptr)

{

destroyTree(subTreePtr->getLeftChildPtr());

destroyTree(subTreePtr->getRightChildPtr());

delete subTreePtr;

} // end if

} // end destroyTree

//////////////////////////////////////////////////////////////

// Protected Tree Traversal Sub-Section

//////////////////////////////////////////////////////////////

template

void BinaryNodeTree::preorder(void visit(ItemType&), BinaryNode* treePtr) const

{

//

// fill the blank

//

} // end preorder

template

void BinaryNodeTree::inorder(void visit(ItemType&), BinaryNode* treePtr) const

{

if(treePtr) {

inorder( visit, treePtr->getLeftChildPtr());

ItemType thisItem = treePtr->getItem();

visit(thisItem);

inorder( visit, treePtr->getRightChildPtr());

}

} // end inorder

template

void BinaryNodeTree::postorder(void visit(ItemType&), BinaryNode* treePtr) const

{

//

// fill the blank

//

} // end postorder

//////////////////////////////////////////////////////////////

// PUBLIC METHODS BEGIN HERE

//////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////

// Public BinaryTreeInterface Methods Section

//////////////////////////////////////////////////////////////

template

ItemType BinaryNodeTree::getRootData() const

{

if (isEmpty())

std::cout

return rootPtr->getItem();

} // end getRootData

template

void BinaryNodeTree::setRootData(const ItemType& newItem)

{

if (isEmpty())

rootPtr = new BinaryNode(newItem, nullptr, nullptr);

else

rootPtr->setItem(newItem);

} // end setRootData

template

bool BinaryNodeTree::add(const ItemType& newData)

{

BinaryNode* newNodePtr = new BinaryNode(newData);

rootPtr = balancedAdd(rootPtr, newNodePtr);

return true;

} // end add

template

bool BinaryNodeTree::remove(const ItemType& target)

{

bool isSuccessful = false;

rootPtr = removeValue(rootPtr, target, isSuccessful);

return isSuccessful;

} // end remove

template

ItemType BinaryNodeTree::getEntry(const ItemType& anEntry) const

{

bool isSuccessful = false;

BinaryNode* binaryNodePtr = findNode(rootPtr, anEntry, isSuccessful);

if (isSuccessful)

return binaryNodePtr->getItem();

else

std::cout

} // end getEntry

template

bool BinaryNodeTree:: contains(const ItemType& anEntry) const

{

bool isSuccessful = false;

findNode(rootPtr, anEntry, isSuccessful);

return isSuccessful;

} // end contains

//////////////////////////////////////////////////////////////

// Public Traversals Section

//////////////////////////////////////////////////////////////

template

void BinaryNodeTree::drawTree(BinaryNode* treePtr, std::string lpad, std::string rpad) const

{

std::string pad = lpad.substr(0, lpad.size() - 1);

if (treePtr == nullptr) return;

drawTree(treePtr->getRightChildPtr(), rpad + " |", rpad + " ");

std::cout getItem()

drawTree(treePtr->getLeftChildPtr(), lpad + " ", lpad + " |");

} // end drawTree

//////////////////////////////////////////////////////////////

// Overloaded Operator

//////////////////////////////////////////////////////////////

template

BinaryNodeTree& BinaryNodeTree::

operator=(const BinaryNodeTree& rightHandSide)

{

if (!isEmpty())

clear();

this = copyTree(&rightHandSide);

return *this;

} // end operator=

//////////////////////////////

// AVLtree Class

//////////////////////////////

template

class AVLtree : public BinaryNodeTree

{

private:

BinaryNode* rootPtr;

int getHeight(BinaryNode* node);

int getBalance(BinaryNode* node);

protected:

ItemType findSuccessorValue(BinaryNode* subTreePtr);

//------------------------------------------------------------

// Protected Utility Methods Section:

// Recursive helper methods for the public methods.

//------------------------------------------------------------

// Recursively finds where the given node should be placed and

// inserts it in a leaf at that point.

BinaryNode* insertInorder(BinaryNode* subTreePtr,

BinaryNode* newNode);

// Removes the given target value from the tree while maintaining a

// binary search tree.

BinaryNode* removeValue(BinaryNode* subTreePtr,

const ItemType target,

bool& success);

// Removes a given node from a tree while maintaining a

// binary search tree.

BinaryNode* removeNode(BinaryNode* nodePtr);

// Removes the leftmost node in the left subtree of the node

// pointed to by nodePtr.

// Sets inorderSuccessor to the value in this node.

// Returns a pointer to the revised subtree.

BinaryNode* removeLeftmostNode(BinaryNode* subTreePtr,

ItemType& inorderSuccessor);

// Returns a pointer to the node containing the given value,

// or nullptr if not found.

BinaryNode* findNode(BinaryNode* treePtr,

const ItemType& target) const;

public:

//------------------------------------------------------------

// Constructor and Destructor Section.

//------------------------------------------------------------

AVLtree() : rootPtr(nullptr) {}

AVLtree(const ItemType& rootItem) {

rootPtr = new BinaryNode(rootItem, nullptr, nullptr);

}

AVLtree(const AVLtree& tree) {

rootPtr = this->copyTree(tree.rootPtr);

}

virtual ~AVLtree() {

this->destroyTree(rootPtr);

}

//------------------------------------------------------------

// Public Methods Section.

//------------------------------------------------------------

bool isEmpty() const { return rootPtr == nullptr; }

int getHeight() const { return this->getHeightHelper(rootPtr); }

int getNumberOfNodes() const { return this->getNumberOfNodesHelper(rootPtr); }

ItemType getRootData() const;

void setRootData(const ItemType& newData) const {

std::cout

}

bool add(const ItemType& newEntry);

bool remove(const ItemType& anEntry);

void clear() { this->destroyTree(rootPtr); rootPtr = nullptr; }

ItemType getEntry(const ItemType& anEntry) const;

// Override contains to use our improved findNode:

bool contains(const ItemType& anEntry) const {

return findNode(rootPtr, anEntry); // nullptr is same as false

}

//------------------------------------------------------------

// Public Traversals Section.

//------------------------------------------------------------

void preorderTraverse(void visit(ItemType&)) const { // Call inherited method

this->preorder(visit, rootPtr); // Call inherited method

}

void inorderTraverse(void visit(ItemType&)) const {

this->inorder(visit, rootPtr);

}

void postorderTraverse(void visit(ItemType&)) const {

this->postorder(visit, rootPtr);

}

void drawAVLtree() const;

//------------------------------------------------------------

// Overloaded Operator Section.

//------------------------------------------------------------

AVLtree& operator=(const AVLtree& rightHandSide);

}; // end AVLtree

////////////////////////////////////////////////////////////

// non-member public helper

int max(int a, int b) { return (a > b) ? a : b; }

template

int height(BinaryNode* nodePtr) {

if (nodePtr == NULL) return 0;

return nodePtr->getHeight();

}

//////////////////////////////////////////////////////////////

//

// Protected Utility Methods Section

//

//////////////////////////////////////////////////////////////

template

BinaryNode* rightRotate(BinaryNode* y)

{ // std::cout

BinaryNode* x = y->getLeftChildPtr();

BinaryNode* T2 = x->getRightChildPtr();

// Perform rotation

x->setRightChildPtr(y);

y->setLeftChildPtr(T2);

// Update heights

y->setHeight(max(height(y->getLeftChildPtr()), height(y->getRightChildPtr())) + 1);

x->setHeight(max(height(x->getLeftChildPtr()), height(x->getRightChildPtr())) + 1);

// Return new root

return y; // should be x

}

template

BinaryNode* leftRotate(BinaryNode* x)

{

BinaryNode* y = x->getRightChildPtr();

BinaryNode* T2 = y->getLeftChildPtr();

// Perform rotation

// Update heights

//

// fill the blank

//

// Return new root

return x; // should be y

}

template

BinaryNode* AVLtree

::insertInorder(BinaryNode* subTreePtr,

BinaryNode* newNodePtr)

{

if (subTreePtr == nullptr)

return newNodePtr;

else

{ // 1. Perform the normal BST insertion */

if (newNodePtr->getItem() getItem())

subTreePtr->setLeftChildPtr(insertInorder(subTreePtr->getLeftChildPtr(), newNodePtr));

else

subTreePtr->setRightChildPtr(insertInorder(subTreePtr->getRightChildPtr(), newNodePtr));

int leftHeight = getHeight(subTreePtr->getLeftChildPtr());

int rightHeight = getHeight(subTreePtr->getRightChildPtr());

// 2. Update height of this ancestor node

subTreePtr->setHeight(max(leftHeight, rightHeight) + 1);

// 3. Get the balance factor of this ancestor node to check whether this node became unbalanced

int balance = leftHeight - rightHeight;

BinaryNode* leftNode = subTreePtr->getLeftChildPtr();

BinaryNode* rightNode = subTreePtr->getRightChildPtr();

ItemType newKey = newNodePtr->getItem();

// If this node becomes unbalanced, then there are 4 cases

// 3.1 Left Left Case

if( balance > 1 && newKey getItem() ) return rightRotate(subTreePtr);

// 3.2 Right Right Case

if( balance rightNode->getItem() ) return leftRotate(subTreePtr);

// 3.3 Left Right Case

if (balance > 1 && newKey > leftNode->getItem()) {

subTreePtr->setLeftChildPtr(leftRotate(leftNode));

return rightRotate(subTreePtr); }

// 3.4 Right Left Case

if (balance getItem()) {

subTreePtr->setRightChildPtr(rightRotate(rightNode));

return leftRotate(subTreePtr); }

return subTreePtr;

} // end if

} // end AVL insertInorder()

template

int AVLtree::getHeight(BinaryNode* node)

{

if (node == nullptr) return 0;

return node->getHeight();

}

template

BinaryNode* AVLtree

::removeValue(BinaryNode* subTreePtr,

const ItemType target, bool& success) {

BinaryNode* nodePtr = subTreePtr;

// 1. Standard BST Deletion

if (subTreePtr == nullptr) { // Not found here

return nullptr;

}

if (subTreePtr->getItem() == target) {

success = true;

if (nodePtr->isLeaf()) {

delete nodePtr;

return (nodePtr = nullptr); // Assign and return (student maybe should have separate statements)

}

else if (nodePtr->getLeftChildPtr() == nullptr) { // Has rightChild only

BinaryNode* nodeToConnectPtr = nodePtr->getRightChildPtr();

delete nodePtr;

nodePtr = nullptr;

return nodeToConnectPtr;

}

else if (nodePtr->getRightChildPtr() == nullptr) { // Has left child only

BinaryNode* nodeToConnectPtr = nodePtr->getLeftChildPtr();

delete nodePtr;

nodePtr = nullptr;

return nodeToConnectPtr;

}

else { // Has two children

// Traditional way to remove a value in a node with two children

ItemType temp = findSuccessorValue(nodePtr->getRightChildPtr());

nodePtr->setItem(temp);

nodePtr->setRightChildPtr(removeValue(nodePtr->getRightChildPtr(), temp, success));

}

}

else {

if (subTreePtr->getItem() > target)

// Search the left subtree

subTreePtr->setLeftChildPtr(removeValue(subTreePtr->getLeftChildPtr(), target, success));

else

// Search the right subtree

subTreePtr->setRightChildPtr(removeValue(subTreePtr->getRightChildPtr(), target, success));

} // end if

// If only one node, return node

if (nodePtr == nullptr)

{

return nodePtr;

}

// 2. update height of current node and get balance

int leftHeight = getHeight(nodePtr->getLeftChildPtr());

int rightHeight = getHeight(nodePtr->getRightChildPtr());

int balance = leftHeight - rightHeight;

nodePtr->setHeight(max(leftHeight, rightHeight) + 1);

// 2.1 Left Left Case

// 2.2 right Right Case

// 2.3 Left Right Case

// 2.4 Right Left Case

return nodePtr;

} // end removeValue

template

BinaryNode* AVLtree

::removeNode(BinaryNode* nodePtr) {

// Case 1) Node is a leaf - it is deleted

// Case 2) Node has one child - parent adopts child

// Case 3) Node has two children:

// Traditional implementation: Find successor node.

// Alternate implementation: Find successor value and replace node's value;

// alternate does not need pass-by-reference

if (nodePtr->isLeaf()) {

delete nodePtr;

return (nodePtr = nullptr); // Assign and return (student maybe should have separate statements)

}

else if (nodePtr->getLeftChildPtr() == nullptr) { // Has rightChild only

BinaryNode* nodeToConnectPtr = nodePtr->getRightChildPtr();

delete nodePtr;

nodePtr = nullptr;

return nodeToConnectPtr;

}

else if (nodePtr->getRightChildPtr() == nullptr) { // Has left child only

BinaryNode* nodeToConnectPtr = nodePtr->getLeftChildPtr();

delete nodePtr;

nodePtr = nullptr;

return nodeToConnectPtr;

}

else { // Has two children

// Traditional way to remove a value in a node with two children

ItemType newNodeValue;

nodePtr->setRightChildPtr(removeLeftmostNode(nodePtr->getRightChildPtr(), newNodeValue));

nodePtr->setItem(newNodeValue);

return nodePtr;

}

} // end removeNode

template

int AVLtree::getBalance(BinaryNode* node)

{

if (node == nullptr)

{

return 0;

}

return height(node->getLeftChildPtr()) - height(node->getRightChildPtr());

}

template

BinaryNode* AVLtree

::removeLeftmostNode(BinaryNode* nodePtr,

ItemType& inorderSuccessor) {

if (nodePtr->getLeftChildPtr() == nullptr) {

inorderSuccessor = nodePtr->getItem();

return removeNode(nodePtr);

}

else {

nodePtr->setLeftChildPtr(removeLeftmostNode(nodePtr->getLeftChildPtr(), inorderSuccessor));

return nodePtr;

} // end if

} // end removeLeftmostNode

template

ItemType AVLtree::findSuccessorValue(BinaryNode* subTreePtr)

{

BinaryNode* myLeftChildPtr = subTreePtr->getLeftChildPtr();

if (myLeftChildPtr != nullptr)

{

if (myLeftChildPtr->getLeftChildPtr() == nullptr) {

ItemType nodeItemValue = myLeftChildPtr->getItem();

subTreePtr->setLeftChildPtr(removeNode(myLeftChildPtr));

return nodeItemValue;

}

else

{

return findSuccessorValue(subTreePtr->getLeftChildPtr());

} // end if

}

return subTreePtr->getItem();

} // end findSuccessorValue

// Override findNode because now we can use a binary search:

template

BinaryNode* AVLtree

::findNode(BinaryNode* subTreePtr,

const ItemType& target) const {

// Uses a binary search

if (subTreePtr == nullptr)

return nullptr; // Not found

else if (subTreePtr->getItem() == target)

return subTreePtr; // Found

else if (subTreePtr->getItem() > target)

// Search left subtree

return findNode(subTreePtr->getLeftChildPtr(), target);

else

// Search right subtree

return findNode(subTreePtr->getRightChildPtr(), target);

} // end findNode

//////////////////////////////////////////////////////////////

// Public BinaryTreeInterface Methods Section

//////////////////////////////////////////////////////////////

template

ItemType AVLtree::getRootData() const {

if (isEmpty())

std::cout

return rootPtr->getItem();

} // end getRootData

template

bool AVLtree::add(const ItemType& newData) {

BinaryNode* newNodePtr = new BinaryNode(newData);

rootPtr = insertInorder(rootPtr, newNodePtr);

return true;

} // end add

template

bool AVLtree::remove(const ItemType& target) {

bool isSuccessful = false;

rootPtr = removeValue(rootPtr, target, isSuccessful);

return isSuccessful;

} // end remove

// Override getEntry to use our improved findNode:

template

ItemType AVLtree::getEntry(const ItemType& anEntry) const {

BinaryNode* nodeWithEntry = findNode(rootPtr, anEntry);

if (nodeWithEntry == nullptr)

std::cout

else

return nodeWithEntry->getItem();

} // end getEntry

//////////////////////////////////////////////////////////////

// Public Traversals Section

//////////////////////////////////////////////////////////////

template

void AVLtree::drawAVLtree() const {

std::cout

this->drawTree(rootPtr, " ", " ");

std::cout

}

//////////////////////////////////////////////////////////////

// Overloaded Operator

//////////////////////////////////////////////////////////////

template

AVLtree& AVLtree::

operator=(const AVLtree& rightHandSide) {

if (!isEmpty())

clear();

this = copyTree(&rightHandSide); // Call inherited method

return *this;

} // end operator=

#endif

testAVL.cpp

#include

#include "AVLtree.h" // ADT binary tree operations

#include

#include

#include

#include //

using namespace std;

string del = ","; // default delimiter

int trace = 0; // default trace mode, 0 - no trace, 1 - level 1, 2 - level 2.

// Prototypes

void parse(string input, vector &token, string del);

int tokenSize(string input, string del);

void display(string& anItem) { cout

int main() {

// Start up test with hard-wired data sets here:

vector temp; // temp holder for string tokens

string del = ",";

// Initialize the Binary Search Tree (BST) menu app.

// create a default BST instance for testing

AVLtree* treePtr = new AVLtree();

cout

temp.clear();

string input = "h,d,l,b,f,j,n,a,c,e,g,i,k,m,o";

// string input = "g,h,i,j,k,l,m,n,o,p,a,b,c,d,e,f";

parse(input, temp, del);

int tSize = tokenSize(input, del);

cout

for(int i =0; i

treePtr->add(temp[i]);

//cout

treePtr->drawAVLtree();

}

treePtr->drawAVLtree();

auto menu = [&]() {

cout

};

menu();

while(true){

// start the BST menu

string usr_input;

cout YOUR CHOICE-> ";

getline(cin,usr_input);

if(usr_input.length() > 1){

cout

}

else {

char in = tolower(usr_input[0]);

if(in == 'p') treePtr->drawAVLtree();

else if(in == 'e') {

cout isEmpty() ? "EMPTY ": "NOT EMPTY ");

}

else if(in == 'h') {

cout getHeight()

}

else if(in == 'n') {

cout getNumberOfNodes()

}

else if(in == 'i') {

string input;

cout

getline(cin, input);

treePtr->add(input);

tSize++;

cout

}

else if(in == 'r') {

string input;

cout

getline(cin, input);

if(treePtr->remove(input)) tSize--;

else cout

}

else if(in == 'c') {

treePtr->clear();

tSize =0;

}

else if(in == 'b') {

treePtr->clear();

temp.clear();

string input;

cout ";

getline(cin, input);

parse(input, temp, del);

tSize = tokenSize(input,del);

for(int i =0; i

treePtr->add(temp[i]);

if(trace > 1) treePtr->drawAVLtree();

}

}

else if(in == '1') {

cout

treePtr->inorderTraverse(display);

}

else if(in == '2') {

cout

treePtr->preorderTraverse(display);

}

else if(in == '3') {

cout

treePtr->postorderTraverse(display);

}

else if(in == 't') trace = (trace + 1)%3;

else if(in == 'm') menu();

else if(in == 'q') exit(0);

else cout

}//else

} //while

}

void parse(string input, vector &token, string del) {

token.clear();

int countDel =0;

for(int i = 0; i

if(input[i] == del[0])

countDel++;

}

int tokenSize = countDel +1;

for(int i=0; i

int x= input.find(del);

token.push_back(input.substr(0,x));

input = input.substr(x+1);

}

}

// Utilities

int tokenSize(string input, string del)

{

int size;

int countDel =0;

for(int i = 0; i

if(input[i] == del[0])

countDel++;

}

return size = countDel +1;

}

Running /home/ubuntu/workspace/consc?2 10/m88/testAv1.cpp Create a default AVLtree (BST (after completion of this assignment, this should be an AVL Tree): Display the binary search tree as it is being built: t-h tI1 0 rn +a +n +0 t-h 0 ?m ?a BINARY SEARCH TREE MENU Delimiter is(,) t TOGGLE trace: (OFF) LEVEL-0 p PRINT tree e - iSEMPTY h - getHEIGHT n -NUMBER of Nodes b-BUILD tree from a node list i - INSERT r -REMOVE C -CLEAR 1 In Order Traversal 2 -Pre Order Traversal 3 -Post Order Traversal mMENU -this menu q - quit this menu CE_level_0 >YOUR CHOICE-> 1 In-order traversal list: abcdefgh?jk1mnop RACE level 0 >YOUR CHOICE-2 re-order traversal list: jgdbacefh?n1knop RACE level 0 ->YOUR CHOICE-> 3 ost-order traversal list: acbfed?hgkmlpon TRACE level 0YOUR CHOICE- 17 Chern T Form 10. pdf psbjpeg Running /home/ubuntu/workspace/consc?2 10/m88/testAv1.cpp Create a default AVLtree (BST (after completion of this assignment, this should be an AVL Tree): Display the binary search tree as it is being built: t-h tI1 0 rn +a +n +0 t-h 0 ?m ?a BINARY SEARCH TREE MENU Delimiter is(,) t TOGGLE trace: (OFF) LEVEL-0 p PRINT tree e - iSEMPTY h - getHEIGHT n -NUMBER of Nodes b-BUILD tree from a node list i - INSERT r -REMOVE C -CLEAR 1 In Order Traversal 2 -Pre Order Traversal 3 -Post Order Traversal mMENU -this menu q - quit this menu CE_level_0 >YOUR CHOICE-> 1 In-order traversal list: abcdefgh?jk1mnop RACE level 0 >YOUR CHOICE-2 re-order traversal list: jgdbacefh?n1knop RACE level 0 ->YOUR CHOICE-> 3 ost-order traversal list: acbfed?hgkmlpon TRACE level 0YOUR CHOICE- 17 Chern T Form 10. pdf psbjpeg