PROWAREtech
C++: Binary Tree Data Structure
An O(log(n)) at best and O(n) at worst data structure.
The binary search tree is very important. New data can be sorted instantly. Trees are used to sort tokens in programming languages and to index data in databases.
Searches and adding items are very fast, O(log(n)) (best case) O(n) (worse case) using Big O notation.
This is a link-based binary search tree, for an array based one see this page.
This basic example of a binary search tree is written mostly in C. It uses the benefits of a C++ class constructor and destructor to make the code more readable.
(Skip to the C++ example that uses template classes.) Note that the data that this tree sorts are passed as command line arguments so the
executable's command line would look like:executable.exe John Mary Paul Aaron David Xavier Susan. The program output would look like this in
the console window:
Aaron David John Mary Paul Susan Xavier Press any key to continue . . .
#include <iostream>
using namespace std;
class Node
{
private:
char *szName;
public:
Node *left, *right;
Node(char *szNodeName);
~Node();
char *GetNodeName();
};
Node::Node(char *szNodeName)
{
left = right = 0;
szName = szNodeName;
}
Node::~Node()
{
if(left)
delete left;
if(right)
delete right;
}
char *Node::GetNodeName()
{
return szName;
}
void AddNode(Node **next, char *szNodeName)
{
if((*next) == 0)
*next = new Node(szNodeName);
else
{
if(strcmp(szNodeName, (*next)->GetNodeName()) < 0)
AddNode(&(*next)->left, szNodeName);
else
AddNode(&(*next)->right, szNodeName);
}
}
void PrintNodes(Node *node)
{
if(node)
{
PrintNodes(node->left);
cout << node->GetNodeName() << endl;
PrintNodes(node->right);
}
}
int main(int argc, char *argv[])
{
Node *root = 0;
if(argc > 1)
for(int i = 1; i < argc; AddNode(&root, argv[i++]));
PrintNodes(root);
if(root)
delete root;
return 0;
}Now a binary search tree written in C++ using templates.
#include <iostream>
#include <string>
#include <stdlib.h>
#include <ctime>
using namespace std;
template <class TData> class Node
{
private:
Node() {}
public:
TData data;
Node<TData> *pleft, *pright;
Node(const TData &dataToSort);
~Node();
bool IsLeaf();
};
template <class TData> class BinarySearchTreeDataMembers
{
public:
Node<TData> *ptree;
unsigned int height, count;
BinarySearchTreeDataMembers();
};
template <class TData> class BinarySearchTree
{
private:
BinarySearchTreeDataMembers<TData> *dm;
void CopyTree(const Node<TData> *tree); // this is used by the assignment operator
void AddNode(Node<TData> *pnode); // this is used by the Balance() operation
void AddArray(Node<TData> **parray, const unsigned int length);
public:
BinarySearchTree();
BinarySearchTree(const BinarySearchTree<TData> &obj); // copy constructor
~BinarySearchTree();
const BinarySearchTree<TData> &operator=(const BinarySearchTree<TData> &obj); // assignment operator
void Add(const TData &data);
bool Search(const TData &data) const;
void Forward(void ClientFunc(const TData &)) const;
void Backward(void ClientFunc(const TData &)) const;
const TData *MaxValue() const; // return nullptr when tree is empty; this function could be useful to overload <, >, and == operators
const TData *MinValue() const;
unsigned int Height() const; // tree height; returns 0 if empty
unsigned int Count() const; // node count; returns 0 if empty
void Balance();
void Clear();
};
template <class TData> Node<TData>::Node(const TData &dataToSort)
{
pleft = nullptr;
pright = nullptr;
data = dataToSort;
}
template <class TData> Node<TData>::~Node()
{
if (pleft)
{
delete pleft;
pleft = nullptr;
}
if (pright)
{
delete pright;
pright = nullptr;
}
}
template <class TData> bool Node<TData>::IsLeaf() { return (pleft == nullptr && pright == nullptr); }
template <typename TData> void forward(void client_func(const TData &), const Node<TData> *tree)
{
if (tree)
{
forward(client_func, tree->pleft);
client_func(tree->data);
forward(client_func, tree->pright);
}
}
template <typename TData> void backward(void client_func(const TData &), const Node<TData> *tree)
{
if (tree)
{
backward(client_func, tree->pright);
client_func(tree->data);
backward(client_func, tree->pleft);
}
}
template <typename TData> void FillArray(Node<TData> *tree, Node<TData> **parray, unsigned int &index)
{
if (tree)
{
FillArray(tree->pleft, parray, index);
parray[index++] = tree;
FillArray(tree->pright, parray, index);
}
}
template <class TData> BinarySearchTreeDataMembers<TData>::BinarySearchTreeDataMembers()
{
ptree = nullptr;
height = 0;
count = 0;
}
template <class TData> BinarySearchTree<TData>::BinarySearchTree(const BinarySearchTree<TData> &obj)
{
dm = new BinarySearchTreeDataMembers<TData>();
this->operator=(obj);
}
template <class TData> BinarySearchTree<TData>::BinarySearchTree()
{
dm = new BinarySearchTreeDataMembers<TData>();
}
template <class TData> BinarySearchTree<TData>::~BinarySearchTree()
{
Clear();
delete dm;
}
template <class TData> const BinarySearchTree<TData> &BinarySearchTree<TData>::operator=(const BinarySearchTree<TData> &obj)
{
if (this != &obj)
{
Clear();
CopyTree(obj.dm->ptree);
}
return (*this);
}
template <class TData> void BinarySearchTree<TData>::CopyTree(const Node<TData> *tree)
{
if (tree)
{
Add(tree->data);
CopyTree(tree->pleft);
CopyTree(tree->pright);
}
}
template <class TData> void BinarySearchTree<TData>::Add(const TData &data)
{
Node<TData> **root = &dm->ptree;
unsigned int height = 0;
while (*root)
{
height++;
if ((*root)->data == data)
{
if (height > dm->height)
dm->height = height;
return;
}
if ((*root)->data > data)
root = &(*root)->pleft;
else
root = &(*root)->pright;
}
(*root) = new Node<TData>(data);
dm->count++;
height++;
if (height > dm->height)
dm->height = height;
}
template <class TData> unsigned int BinarySearchTree<TData>::Height() const
{
return dm->height;
}
template <class TData> unsigned int BinarySearchTree<TData>::Count() const
{
return dm->count;
}
template <class TData> void BinarySearchTree<TData>::AddNode(Node<TData> *pnode)
{
Node<TData> **root = &dm->ptree;
unsigned int height = 0;
while (*root)
{
height++;
if (pnode->data < (*root)->data)
root = &(*root)->pleft;
else
root = &(*root)->pright;
}
(*root) = pnode;
height++;
if (height > dm->height)
dm->height = height;
}
template <class TData> void BinarySearchTree<TData>::AddArray(Node<TData> **parray, const unsigned int length)
{
if (length)
{
const unsigned int middle = length / 2;
AddNode(parray[middle]);
if (middle + 1 < length)
AddArray(parray + middle + 1, length - middle - 1);
if (middle)
AddArray(parray, length - middle - (length & 1));
}
}
template <class TData> void BinarySearchTree<TData>::Balance()
{
dm->height = 0;
const unsigned int count = dm->count;
Node<TData> **parray = new Node<TData>*[count];
unsigned int index = 0;
FillArray(dm->ptree, parray, index);
for (index = 0; index < count; index++)
parray[index]->pleft = parray[index]->pright = nullptr;
dm->ptree = nullptr;
AddArray(parray, count);
delete[]parray;
}
template <class TData> bool BinarySearchTree<TData>::Search(const TData &data) const
{
Node<TData> *root = dm->ptree;
while (root)
{
if (root->data == data)
return true;
if (data < root->data)
root = root->pleft;
else
root = root->pright;
}
return false;
}
template <class TData> void BinarySearchTree<TData>::Forward(void ClientFunc(const TData &)) const
{
forward(ClientFunc, dm->ptree);
}
template <class TData> void BinarySearchTree<TData>::Backward(void ClientFunc(const TData &)) const
{
backward(ClientFunc, dm->ptree);
}
template <class TData> const TData *BinarySearchTree<TData>::MinValue() const
{
Node<TData> *pnode = dm->ptree;
while (pnode && pnode->pleft)
pnode = pnode->pleft;
if (pnode)
return &pnode->data;
return nullptr;
}
template <class TData> const TData *BinarySearchTree<TData>::MaxValue() const
{
Node<TData> *pnode = dm->ptree;
while (pnode && pnode->pright)
pnode = pnode->pright;
if (pnode)
return &pnode->data;
return nullptr;
}
template <class TData> void BinarySearchTree<TData>::Clear()
{
if (dm->ptree)
{
delete dm->ptree;
dm->ptree = nullptr;
dm->count = dm->height = 0;
}
}
// ######## TEST DRIVER CODE (THE CLIENT) ########
template <typename TData> void DataHit(const TData &data)
{
cout << data << endl;
}
class Person
{
private:
string firstname, lastname;
public:
Person() {};
Person(const char *first, const char *last)
{
firstname = first;
lastname = last;
}
string FirstName() const { return firstname; }
string LastName() const { return lastname; }
// overload these operators to make it compatible with the algorithms used
bool operator<(const Person &obj) const
{
if (this->lastname == obj.lastname)
return this->firstname < obj.firstname;
return this->lastname < obj.lastname;
}
bool operator>(const Person &obj) const
{
if (this->lastname == obj.lastname)
return this->firstname > obj.firstname;
return this->lastname > obj.lastname;
}
bool operator==(const Person &obj) const
{
return (this->lastname == obj.lastname && this->firstname == obj.firstname);
}
const Person &operator=(const Person &obj)
{
if (this != &obj)
{
this->firstname = obj.firstname;
this->lastname = obj.lastname;
}
return (*this);
}
};
void DataHit(const Person &data)
{
cout << data.LastName() << ", " << data.FirstName() << endl;
}
int main()
{
{
BinarySearchTree<int> bt;
int n;
time_t t = time(0);
srand(t);
for (int i = 0; i < 25; i++)
{
n = rand();
cout << n << endl;
bt.Add(n);
}
BinarySearchTree<int> bt2 = bt;
bt = bt2;
cout << "ENTER A NUMBER TO SEARCH: ";
cin >> n;
bool found = bt.Search(n);
if (found)
cout << "FOUND: " << n << endl;
else
cout << "NOT FOUND: " << n << endl;
bt.Forward(DataHit);
cout << endl;
bt.Backward(DataHit);
const int *p = bt.MaxValue();
if (p)
{
cout << "MAX: " << *p << endl;
cout << "MIN: " << *bt.MinValue() << endl;
}
cout << "COUNT: " << bt.Count() << endl;
cout << "HEIGHT: " << bt.Height() << endl;
cout << "BALANCING..." << endl;
bt.Balance();
cout << "COUNT: " << bt.Count() << endl;
cout << "HEIGHT: " << bt.Height() << endl;
}
cout << endl;
{
BinarySearchTree<string> bt;
string s;
for (int i = 0; i < 20; i++)
{
char c[4] = { 0,0,0,0 };
c[0] = c[1] = c[2] = ((rand() % 26) + 97);
s = c;
cout << s << endl;
bt.Add(s);
}
cout << "ENTER A STRING TO SEARCH: ";
cin >> s;
bool found = bt.Search(s);
if (found)
cout << "FOUND: " << s << endl;
else
cout << "NOT FOUND: " << s << endl;
bt.Forward(DataHit);
cout << endl;
bt.Backward(DataHit);
const string *p = bt.MaxValue();
if (p)
{
cout << "MAX: " << *p << endl;
cout << "MIN: " << *bt.MinValue() << endl;
}
}
{
BinarySearchTree<Person> people;
Person *temp[] = {
new Person("Vince", "Young"),
new Person("Xavier", "Taylor"),
new Person("John", "Williams"),
new Person("Angela", "Taylor"),
new Person("Sam", "Smith"),
new Person("Julie", "Simms"),
new Person("Susie", "Williams"),
new Person("John", "Brown"),
new Person("Will", "White"),
new Person("John", "White"),
new Person("Jill", "Flowers")
};
for (int i = 0; i < sizeof(temp) / sizeof(Person *); i++)
{
people.Add(*temp[i]);
delete temp[i];
temp[i] = nullptr;
}
cout << endl;
people.Forward(DataHit);
cout << endl;
people.Backward(DataHit);
cout << endl;
}
return 0;
}
Coding Video
Comment
