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