HERE IS BASE

#ifndef TREE_HPP #define TREE_HPP #include

#include "Treenode.hpp" using std::cout;

// Tree class-template definition template class Tree { public: // insert node in Tree void insertNode(const NODETYPE& value) { insertNodeHelper(&rootPtr, value); }

// begin preorder traversal of Tree void preOrderTraversal() const { preOrderHelper(rootPtr); }

// begin inorder traversal of Tree void inOrderTraversal() const { inOrderHelper(rootPtr); }

// begin postorder traversal of Tree void postOrderTraversal() const { postOrderHelper(rootPtr); }

NODETYPE* getArrayInOrder(NODETYPE x[]) { int c = 0; // counter inOrderArrayHelper(rootPtr, x, c); return x;

}

// get the depth of the tree int getDepth() { int totalDepth{0}; int currentDepth{0};

determineDepth(rootPtr, &totalDepth, &currentDepth); return totalDepth; }

int getCount() { int count = 0;

countHelper(rootPtr, count); // count up the entire array return count; }

// begin binary search TreeNode* binaryTreeSearch(int val) { return binarySearchHelper(rootPtr, val); }

// OPTIMIZE THE TREE // pre a tree // post the tree optimized void Optimize() {

}

private: TreeNode* rootPtr{nullptr};

// utility function called by insertNode; receives a pointer // to a pointer so that the function can modify pointer's value void insertNodeHelper( TreeNode** ptr, const NODETYPE& value) { // subtree is empty; create new TreeNode containing value if (*ptr == nullptr) { *ptr = new TreeNode(value); } else { // subtree is not empty // data to insert is less than data in current node if (value data) { insertNodeHelper(&((*ptr)->leftPtr), value); } else { insertNodeHelper(&((*ptr)->rightPtr), value); } } }

// utility function to perform preorder traversal of Tree void preOrderHelper(TreeNode* ptr) const { if (ptr != nullptr) { std::cout data leftPtr); // traverse left subtree preOrderHelper(ptr->rightPtr); // traverse right subtree } }

// utility function to perform inorder traversal of Tree void inOrderHelper(TreeNode* ptr) const { if (ptr != nullptr) { inOrderHelper(ptr->leftPtr); // traverse left subtree std::cout data rightPtr); // traverse right subtree } }

void countHelper(TreeNode* ptr, int &count) const { if (ptr != nullptr) { inOrderHelper(ptr->leftPtr); // traverse left subtree count++; // process node inOrderHelper(ptr->rightPtr); // traverse right subtree } }

// utility function to perform postorder traversal of Tree void postOrderHelper(TreeNode* ptr) const { if (ptr != nullptr) { postOrderHelper(ptr->leftPtr); // traverse left subtree postOrderHelper(ptr->rightPtr); // traverse right subtree std::cout data

// calculate the depth of the tree // void determineDepth(.....) { //

// } // }

// do a binary search on the Tree // pre: a binary tree and a value to search for // post:; the pointer to the value searched for TreeNode* binarySearchHelper(TreeNode * ptr, int val) {

if (ptr == nullptr) // value not in tree { cout

// test if found if (ptr->data == val) { cout data data) // less than walk left { cout data leftPtr, val); // recursivly walk left } else // walk right { cout data rightPtr, val); // recursivly walk left }

}

// recursively dertermine the depth of a tree // pre; Root Ptr, highest Deppth, current depth // post :: highest depth void determineDepth(TreeNode* subRootPtr,int *totalDepth,int *currentDepth) { // if empty if (subRootPtr == nullptr) return; else // not empty { int x = *currentDepth; // store current depth int y = *totalDepth; // store total depth

x++; // increase current depth

if (x > y) // update total depth y = x;

determineDepth(subRootPtr->leftPtr, &y, &x); // go left x = *currentDepth; // reset current depth determineDepth(subRootPtr->rightPtr, &y, &x); // go right

*totalDepth = y; // update pointer value *currentDepth = x; // update pointer value

} }

void inOrderArrayHelper(TreeNode* ptr, NODETYPE x[], int &c) const { if (ptr != nullptr) { inOrderHelper(ptr->leftPtr); // traverse left subtree x[c] = ptr->data; // process node inOrderHelper(ptr->rightPtr); // traverse right subtree } }

};

#endif // TREE_HPP

Project 3: Optimizing a tree Due Date: 11:59 pm, May 4, 2018 Description: As you know, when you insert values to a tree, the values greater will go to the right side and the values smaller go to the left side. The tree will be extremely skewed if you insert values in the order from the 31 in the listed order, the tree will look like: 1 2 3 31 The tree becomes a list (with the depth of 30) and it is not optimized for the search. Your task is to write a member function to optimize the tree to make the depth of the tree to be (Log,(n+1)-1 (n is the number of nodes). For example, the above tree will be optimized to: You can see the depth of the tree becomes 4. The tree of this structure is the best for the search. Please keep it in mind: your optimizing algorithm should not be hardcoded and should be able to apply to all binary trees regardless the content of the trees. Instruction and Test: Use your assignment 8 as the base. Develop an algorithm and implement it in a public member function called Optimize() with void return. To test your code, insert following code into your main function: Tree int> optl ree