Order Now  +1 678 648 4277 

Inserting numbers into a binary tree in C++ assignment help

The guarantees on binary trees in terms of the O(n) of operations assume the tree is balanced. Our C++ assignment helpers insert the values into the binary tree so that the tree is complete. You don’t need to worry about balancing the tree as long as the insertion is done in the correct order. If you insert the items in sorted order for example you end up with a linked list rather than a binary tree.

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); }