Bst Tree with Templates
This is implementation of Map (similar to std::map) that contain Bst Node with key and data
|
Code for Node
template <typename T, typename S >
struct MapNode
{
public:
T m_key;
S m_data;
MapNode* m_left;
MapNode* m_right;
MapNode();
~MapNode() { if(DEBUG_FLAG) std::cout << "~MapNode deleted" << std::endl; }
};
|
Example of Implementation Function
we used double pointer to access head as local variable.
|
Complete Program
// Practice C++ Bst and Tempaltes.
#include <iostream>
#include <stack>
const bool DEBUG_FLAG = true;
template
struct MapNode
{
public:
T m_key;
S m_data;
MapNode* m_left;
MapNode* m_right;
MapNode();
~MapNode() { if(DEBUG_FLAG) std::cout << "~MapNode deleted" << std::endl; }
};
template
MapNode::MapNode() : m_left(nullptr ), m_right(nullptr) { }
template
class aMap
{
public:
aMap();
void Insert(T key, S data);
void PrintInOnder();
void Delete(T key);
MapNode* Find(T key);
void CheckBalanced();
MapNode* m_head;
private:
void InsertRec(MapNode** head, T key, S data);
void PrintInOrderRec(MapNode* head);
void DeleteRec(MapNode** head, T key);
MapNode* FindMax(MapNode* head);
void CheckBalancedRec(MapNode* head);
std::stack*> m_balanceTest;
};
template
aMap::aMap() : m_head(nullptr ) { }
template
void aMap::Insert(T key, S value)
{
this->InsertRec(&m_head, key, value);
}
template
void aMap::InsertRec(MapNode** head, T key, S data)
{
if(nullptr == *head)
{
MapNode* newNode = new MapNode();
newNode->m_key = key;
newNode->m_data = data;
*head = newNode;
return;
}
if(key <= (*head)->m_key)
InsertRec(&(*head)->m_left, key, data);
else
InsertRec(&(*head)->m_right, key, data);
}
template
void aMap::PrintInOnder()
{
this->PrintInOrderRec(m_head);
std::cout << "-------------------------------" << std::endl;
}
template
void aMap::PrintInOrderRec(MapNode* head)
{
if(nullptr == head)
return;
PrintInOrderRec(head->m_left);
std::cout << head->m_key << "=" << head->m_data << std::endl;
PrintInOrderRec(head->m_right);
}
template
void aMap::Delete(T key)
{
this->DeleteRec(&m_head, key);
}
template
void aMap::DeleteRec(MapNode** head, T key)
{
if(nullptr == *head)
return;
if(key < (*head)->m_key)
DeleteRec(&(*head)->m_left, key);
else if(key > (*head)->m_key)
DeleteRec(&(*head)->m_right, key);
else
{
if(nullptr == (*head)->m_left && nullptr == (*head)->m_right)
{
if(DEBUG_FLAG) std::cout << "Case 1 - Orphant Node" << std::endl;
delete *head;
*head = nullptr ;
return;
}
if(nullptr != (*head)->m_left && nullptr == (*head)->m_right)
{
if(DEBUG_FLAG) std::cout << "Case 2a - Left child Node" << std::endl;
MapNode* nextLeft = (*head)->m_left;
delete *head;
*head = nextLeft;
return;
}
if(nullptr == (*head)->m_left && nullptr != (*head)->m_right)
{
if(DEBUG_FLAG) std::cout << "Case 2b - Right child Node" << std::endl;
MapNode* nextRight = (*head)->m_right;
delete *head;
*head = nextRight;
return;
}
if(nullptr != (*head)->m_left && nullptr != (*head)->m_right)
{
if(DEBUG_FLAG) std::cout << "Case 3 - Two child nodes" << std::endl;
MapNode* max = FindMax((*head)->m_left);
(*head)->m_data = max->m_data;
(*head)->m_key = max->m_key;
DeleteRec(&(*head)->m_left, max->m_key);
}
}
}
template
MapNode* aMap::FindMax(MapNode* head)
{
while(head->m_right != NULL) // current head empty checked in Case 3 in Delete.
head = head->m_right;
return head;
}
template
void aMap::CheckBalanced()
{
this->CheckBalancedRec(m_head);
MapNode* refNode;
refNode = m_balanceTest.top();
m_balanceTest.pop();
while(!m_balanceTest.empty())
{
std::cout << refNode->m_key << " " << m_balanceTest.top()->m_key << "\n";
if(refNode->m_key < m_balanceTest.top()->m_key)
{
std::cout << "Not Balanced.. " << std::endl;
return;
}
refNode = m_balanceTest.top();
m_balanceTest.pop();
}
}
template
void aMap::CheckBalancedRec(MapNode* head)
{
if(head == nullptr )
return;
CheckBalancedRec(head->m_left);
m_balanceTest.push(head);
CheckBalancedRec(head->m_right);
}
int main()
{
aMap myMap;
MapNode Node;
Node.m_key = 100;
Node.m_data = "lalala";
myMap.Insert(32, "Anton");
myMap.Insert(2, "Baba");
myMap.Insert(35, "Alex");
myMap.Insert(33, "Lili");
myMap.PrintInOnder();
myMap.PrintInOnder();
myMap.CheckBalanced();
std::cout << "----\n";
myMap.m_head->m_key = 658;
myMap.PrintInOnder();
myMap.CheckBalanced();
return 0;
}
|