+1 678 648 4277 

Adding Items to a Binary Tree

#include #include #include #include using namespace std; class Node { public: Node * left; Node *right; int data; Node () { left = NULL; right = NULL; } }; class BTree { public: /** * A function to create list from 1 to i-1 * @param i the max element of the array * @return the array */ vector < int >createList (int i) { vector < int >x; for (int j = 1; j < i; j++) { x.push_back (j); } return x; } Node *root; BTree () { root = NULL; } /** * add data to a tree. This function is a regular function thar can be found * in a standard BST add node * @param data */ void addData (int data) { Node *parent = root; while (parent != NULL) { if (data - (parent->data) > 0) { if (parent->right == NULL) { parent->right = new Node (); } parent = parent->right; } else { if (parent->left == NULL) { parent->left = new Node (); } parent = parent->left; } } if (parent == NULL) { parent = new Node (); } parent->data = data; } /** * Function to create a complete binary search tree out of a list of list numbers * @param treeList the input list to make the tree of its element */ void ConstructCompleteBSTfromList (vector < int >treeList) { sort (treeList.begin (), treeList.end ()); queue < vector < int >>listsQueue; // holds right and left parts in each iteeration listsQueue.push (treeList); while (listsQueue.size () > 0) { queue < vector < int >>tSplitLists; for (int i = 0; i < listsQueue.size (); i++) { vector < int >tIntList = listsQueue.front (); listsQueue.pop (); int length = tIntList.size (); // compute starting point int mid = calcMid (length); // length/2 ; //+ calcOffset(length); addData (tIntList[mid]); if (mid - 0 > 0) { tSplitLists.push (vector < int >(tIntList.begin (), tIntList.begin () + mid)); } if (length - (mid + 1) > 0) { tSplitLists.push (vector < int >(tIntList.begin () + mid + 1, tIntList.end ())); } } listsQueue = tSplitLists; } } /** * This function calculates the element to be the root * For the BST to be complete the root index has to be offset so that nodes * that would normally appear on the right side of the root instead appear * on the left side of the root. As long as the computation works for any * length list then each split sublist is built properly. * @param listLength the working on list size to get root for * @return the index of the root element for this list */ int calcMid (int listLength) { if (listLength <= 4) { return listLength / 2; } int levelNodesCount = 1; int totalNodes = 1; while (totalNodes < listLength) { levelNodesCount *= 2; totalNodes += levelNodesCount; } int excess = listLength - (totalNodes - levelNodesCount); int minMid = (totalNodes - levelNodesCount + 1) / 2; if (excess <= levelNodesCount / 2) { return minMid + (excess - 1); } else { int midExcess = levelNodesCount / 2; return minMid + (midExcess - 1); } } }; int main () { for (int i = 2; i < 65; ++i) { BTree btree; btree.ConstructCompleteBSTfromList (btree.createList (i)); } } Source.cpp #include #include #include #include #include using namespace std; class Node { public: Node * left; Node *right; int data; Node() { left = NULL; right = NULL; } }; class BTree { public: /** * A function to create list from 1 to i-1 * @param i the max element of the array * @return the array */ vector < int >createList(int i) { vector < int >x; for (int j = 1; j < i; j++) { x.push_back(j); } return x; } Node *root; BTree() { root = NULL; } /** * add data to a tree. This function is a regular function thar can be found * in a standard BST add node * @param data */ void addData(int data) { if (root == NULL) { root = new Node(); root->data = data; return; } Node *parent = root; while (parent != NULL) { if (data - (parent->data) > 0) { if (parent->right == NULL) { parent->right = new Node(); parent = parent->right; break; } parent = parent->right; } else { if (parent->left == NULL) { parent->left = new Node(); parent = parent->left; break; } parent = parent->left; } } if (parent == NULL) { parent = new Node(); } parent->data = data; } /** * Function to create a complete binary search tree out of a list of list numbers * @param treeList the input list to make the tree of its element */ void ConstructCompleteBSTfromList(vector < int >treeList) { sort(treeList.begin(), treeList.end()); vector < vector < int >>listsQueue; // holds right and left parts in each iteeration listsQueue.push_back(treeList); while (listsQueue.size() > 0) { vector < vector < int >>tSplitLists; for (int i = 0; i < listsQueue.size(); i++) { vector < int >tIntList = listsQueue[i]; int length = tIntList.size(); // compute starting point int mid = calcMid(length); // length/2 ; //+ calcOffset(length); addData(tIntList[mid]); if (mid - 0 > 0) { tSplitLists.push_back(vector < int >(tIntList.begin(), tIntList.begin() + mid)); } if (length - (mid + 1) > 0) { tSplitLists.push_back(vector < int >(tIntList.begin() + mid + 1, tIntList.end())); } } listsQueue = tSplitLists; } } /** * This function calculates the element to be the root * For the BST to be complete the root index has to be offset so that nodes * that would normally appear on the right side of the root instead appear * on the left side of the root. As long as the computation works for any * length list then each split sublist is built properly. * @param listLength the working on list size to get root for * @return the index of the root element for this list */ int calcMid(int listLength) { if (listLength <= 4) { return listLength / 2; } int levelNodesCount = 1; int totalNodes = 1; while (totalNodes < listLength) { levelNodesCount *= 2; totalNodes += levelNodesCount; } int excess = listLength - (totalNodes - levelNodesCount); int minMid = (totalNodes - levelNodesCount + 1) / 2; if (excess <= levelNodesCount / 2) { return minMid + (excess - 1); } else { int midExcess = levelNodesCount / 2; return minMid + (midExcess - 1); } } }; int main() { // read array vectordata; int temp; ifstream input("input.txt"); while (input >> temp) { data.push_back(temp); } BTree btree; btree.ConstructCompleteBSTfromList(data); }