Please complete each function that has "TODO" in the comments, don't make any new program just complete the said functions please. I only need the "ToDo implementations" worked on, all the info should be there just complete the algorithms for each of those functions with given information please.

-------------------------------------------------------------------------------------------------------------------

#ifndef AVL_TREE_H

#define AVL_TREE_H

#include "dsexceptions.h"

#include // For NULL

#include // For level order printout

#include

#include // For max() function

using namespace std;

// AvlTree class

//

// CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds

//

// ******************PUBLIC OPERATIONS*********************

// int size( ) --> Quantity of elements in tree

// int height( ) --> Height of the tree (null == -1)

// void insert( x ) --> Insert x

// void insert( vector ) --> Insert whole vector of values

// void remove( x ) --> Remove x (unimplemented)

// bool contains( x ) --> Return true if x is present

// Comparable findMin( ) --> Return smallest item

// Comparable findMax( ) --> Return largest item

// boolean isEmpty( ) --> Return true if empty; else false

// void makeEmpty( ) --> Remove all items

// void printTree( ) --> Print tree in sorted (in) order

// void printPreOrder( ) --> Print tree in pre order

// void printPostOrder( ) --> Print tree in post order

// void printInOrder( ) --> Print tree in *in* order

// ******************ERRORS********************************

// Throws UnderflowException as warranted

template

class AvlTree

{

public:

AvlTree( ) : root( NULL )

{ }

AvlTree( const AvlTree & rhs ) : root( NULL )

{

*this = rhs;

}

~AvlTree( )

{

cout << " [!] Destructor called." << endl;

makeEmpty( );

}

/**

* Find the smallest item in the tree.

* Throw UnderflowException if empty.

*/

const Comparable & findMin( ) const

{

if( isEmpty( ) )

throw UnderflowException( );

return findMin( root )->element;

}

/**

* Find the largest item in the tree.

* Throw UnderflowException if empty.

*/

const Comparable & findMax( ) const

{

if( isEmpty( ) )

throw UnderflowException( );

return findMax( root )->element;

}

/**

* Returns true if x is found in the tree.

*/

bool contains( const Comparable & x ) const

{

return contains( x, root );

}

/**

* Test if the tree is logically empty.

* Return true if empty, false otherwise.

* TODO: Implement

*/

bool isEmpty( ) const

{

return false; // so not correct

}

/**

* Return number of elements in tree.

*/

int size( )

{

return size( root );

}

/**

* Return height of tree.

* Null nodes are height -1

*/

int height( )

{

return height( root );

}

/**

* Print the tree contents in sorted order.

*/

void printTree( ) const

{

if( isEmpty( ) )

cout << "Empty tree" << endl;

else

printInOrder( root );

}

/**

* Print the tree contents in sorted order.

*/

void printInOrder( ) const

{

if( isEmpty( ) )

cout << "Empty tree" << endl;

else

printInOrder( root );

}

/**

* Print the tree contents in pre order.

*/

void printPreOrder( ) const

{

if( isEmpty( ) )

cout << "Empty tree" << endl;

else

printPreOrder( root );

}

/**

* Print the tree contents in post order.

*/

void printPostOrder( ) const

{

if( isEmpty( ) )

cout << "Empty tree" << endl;

else

printPostOrder( root );

}

/**

* Make the tree logically empty.

*/

void makeEmpty( )

{

makeEmpty( root );

}

/**

* Insert x into the tree; duplicates are ignored.

*/

void insert( const Comparable & x )

{

insert( x, root );

}

/**

* Insert vector of x's into the tree; duplicates are ignored.

*/

void insert( vector vals)

{

for( auto x : vals ) {

insert( x, root );

}

}

/**

* Remove x from the tree. Nothing is done if x is not found.

* TODO: Implement

*/

void remove( const Comparable & x )

{

//cout << "[!] Sorry, remove unimplemented; " << x << " still present" << endl;

}

/**

* Deep copy. - or copy assignment operator

* Will be in part II

*/

const AvlTree & operator=( const AvlTree & rhs )

{

cout << " [!] Copy *assignment* operator called." << endl;

return *this;

}

/*****************************************************************************/

private:

struct AvlNode

{

Comparable element;

AvlNode *left;

AvlNode *right;

int height;

AvlNode( const Comparable & theElement, AvlNode *lt,

AvlNode *rt, int h = 0 )

: element( theElement ), left( lt ), right( rt ), height( h ) { }

};

AvlNode *root;

/**

* Internal method to count nodes in tree

* TODO: Implement

*/

int size( AvlNode * & t )

{

return(-1);

}

/**

* Internal method to insert into a subtree.

* x is the item to insert.

* t is the node that roots the subtree.

* Set the new root of the subtree.

* TODO: Implement

*/

void insert( const Comparable & x, AvlNode * & t )

{

// Definitely to do

}

/**

* Internal method to find the smallest item in a subtree t.

* Return node containing the smallest item.

* You'll need this for deletes

* TODO: Implement

*/

AvlNode * findMin( AvlNode *t ) const

{

return t; // placeholder

}

/**

* Internal method to find the largest item in a subtree t.

* Return node containing the largest item.

* TODO: Implement

*/

AvlNode * findMax( AvlNode *t ) const

{

return t; // placeholder

}

/**

* Internal method to test if an item is in a subtree.

* x is item to search for.

* t is the node that roots the tree.

* TODO: Implement

*/

bool contains( const Comparable & x, AvlNode *t ) const

{

return false; // Lolz

}

/******************************************************/

/**

* Internal method to make subtree empty.

* TODO: implement for destructor

*

*/

void makeEmpty( AvlNode * & t )

{

cout << " [!] makeEmpty not implemented " << endl;

}

/**

* Internal method to print a subtree rooted at t in sorted order.

* TODO: Implement

*/

void printInOrder( AvlNode *t ) const

{

cout << " [!] Printing In Order";

}

/**

* Internal method to print a subtree rooted at t in pre order.

* TODO: Implement

*/

void printPreOrder( AvlNode *t ) const

{

cout << " [!] Printing Pre order";

}

/**

* Internal method to print a subtree rooted at t in post order.

* TODO: Implement

*/

void printPostOrder( AvlNode *t ) const

{

cout << " [!] Printing post order";

}

/**

* Internal method to clone subtree.

*/

AvlNode * clone( AvlNode *t ) const

{

if( t == NULL )

return NULL;

else

return new AvlNode( t->element, clone( t->left ), clone( t->right ), t->height );

}

// Avl manipulations

/**

* Return the height of node t or -1 if NULL.

* TODO: Implement

*/

int height( AvlNode *t ) const

{

return(-2); // DEFINITELY not true

}

int max( int lhs, int rhs ) const

{

return lhs > rhs ? lhs : rhs;

}

/**

* Rotate binary tree node with left child.

* For AVL trees, this is a single rotation for case 1.

* Update heights, then set new root.

* TODO: Implement

*/

void rotateWithLeftChild( AvlNode * & k2 )

{

}

/**

* Rotate binary tree node with right child.

* For AVL trees, this is a single rotation for case 4.

* Update heights, then set new root.

* TODO: Implement

*/

void rotateWithRightChild( AvlNode * & k1 )

{

}

/**

* Double rotate binary tree node: first left child.

* with its right child; then node k3 with new left child.

* For AVL trees, this is a double rotation for case 2.

* Update heights, then set new root.

* TODO: Implement

*/

void doubleWithLeftChild( AvlNode * & k3 )

{

}

/**

* Double rotate binary tree node: first right child.

* with its left child; then node k1 with new right child.

* For AVL trees, this is a double rotation for case 3.

* Update heights, then set new root.

* TODO: Implement

*/

void doubleWithRightChild( AvlNode * & k1 )

{

}

};

#endif