C++: Binary Tree 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

https://youtu.be/FXVKguFdPyg

Comment