Plant a Node, make a Binary Tree Forest in C++!

Once in awhile I really like to push the crazy and bizarre in the way of programming theory. Twist something mother nature made into a computer mutation that only a mad computer scientist would love. I fell upon the idea of creating a binary forest. What is that you ask? Well it is what I am calling a vector made up of binary trees. Each tree would have its own special attributes and together they would be pushed together to make… well… a forest of binary trees! One tree could contain even numbers. Another could be odd (like some of us here on DIC) and one could even be prime. Lets explore the crazy idea on this entry of the Programmer’s Underground!

So how do we build a binary tree forrest? Well first of all we need a way to build the trees, then we need a way to group the trees up into a forest. So what we need to do is create an automated way of actually generating some random value nodes which we will then put together into a binary tree.

If you are unfamiliar with a binary tree, it is simply a hierarchy of nodes where each point (called a node) can have zero, one or at max two branches below it. The two branches are often referred to as left and right. The left branch has values less than that of the node that the branch belongs to. The right branch has values higher than the node.

You can see my blog entry on nodes and binary trees (including a great little graphic to show you the organization of a tree). It is a bit too much to explain all over again here on this entry. You can see it here.

Once we have a mechanism for building trees, we must generate some values, create some nodes with those values, evaluate the values and then pass them to the appropriate tree to be added.

After we build our trees, we have to group them together. To do this grouping I decided to create a vector of node pointers. A vector is like a collection in more modern languages. Think of it as a group of similar items that exist as a “collective”. We can have a vector of integers, custom structures, even pointers to other objects. So I decided to create a vector of pointers to nodes. Our vector will point to the root node that starts each tree.

Below is a simple graphic showing the structure of this monster. At the top you will see that our vector has three slots. These will be created using the push_back method of a vector. On each push_back call, we give it one of our prebuilt binary trees. One will be even, one will be odd and one will consist of prime numbers. This is infinitely scalable and you can have trees with cousin primes, numbers in lotto, or even trees of other objects.

So how about we get to the coding in C++ and show the steps of how this is going to be built. Be sure to read through the in code comments and take your time to see what is going on.

#include <iostream>
#include <vector>
#include <time.h>
using namespace std;

// Structure of our node
struct node {
	int value;
	node *left;
	node *right;
};

// Prototypes
bool isPrime(int);
void addToTree(node*&, node*);
void printTree(node*);

int main() {
	// First create our forrest vector to hold our trees
	vector<node*> myforrestvector;

	// Two variables, i is for our loop and r is for our random number
	int i = 0;
	int r = 0;

	// Create three pointers to nodes
	// We set them to NULL so they are not pointing at anything... yet!
	node *eventree = NULL;
	node *oddtree = NULL;
	node *primetree = NULL;

	// Seed our random number generator
	srand((int)time(NULL));

	while (i < 100) {
		// Get a random number
		r = rand() % 100 + 1;

		// Put it in even or odd trees
		if ((r % 2) == 0) { 
			// Even
			node *anEvenItem = new node();
			anEvenItem->value = r;
			addToTree(eventree,anEvenItem); 
		}
		else { 
			// Odd
			node *anOddItem = new node();
			anOddItem->value = r;
			addToTree(oddtree, anOddItem); 
		}

		// Place it in the prime tree
		if (isPrime(r)) { 
			node *aPrimeItem = new node();
			aPrimeItem->value = r;
			addToTree(primetree,aPrimeItem); 
		}
		
		i++;
	}

	// Build our forrest by pushing the tree roots onto our vector
	myforrestvector.push_back(eventree);
	myforrestvector.push_back(oddtree);
	myforrestvector.push_back(primetree);

	// Create an iterator of type node*
	vector<node*>::iterator iterate;

	// We start a loop using begin to refer to the beginning of the vector and
	// we continue until we hit the end of the vector. Each item in our forrest
	// is a special binary tree.
	for (iterate = myforrestvector.begin(); iterate != myforrestvector.end(); iterate++) {
		cout << "Printing tree..." << endl;
		// Dereference the root and give the pointer to a tree root to printTree
		printTree((*iterate));
		cout << "End of tree" << endl << endl;
	}

	return 0;
}

// Simple function to determine if the number is prime
// That is, only divisible by 1 and itself.
bool isPrime(int number) {
	if (number > 1) { 
		for (int i = 2; i < number; i++) {
			if ((number % i) == 0) { return false; }
		}
		return true;
	}
	else { return false; }
}

// In charage of adding a node item to our specific trees.
void addToTree(node *&tree, node *item) {
	if (tree == NULL) {
		// If no root in the tree, make it the first.
		tree = item;
	}
	else {
		// Setup a pointer to our root which we can then keep track
		// of current node as we traverse the tree.
		node *temp = tree;
		bool flag = false;

		while (!flag) {
			// If node value is less than current node, we check the left branch
			// If it is null, we place the new node there. Otherwise we set the
			// current node to the left branch and go back through the loop.
			if (item->value < temp->value) {
				if (temp->left == NULL) { temp->left = item; flag = true; }
				else { temp = temp->left; }
			}
			else if (item->value > temp->value) {
				if (temp->right == NULL) { temp->right = item; flag = true; }
				else { temp = temp->right; }
			}
			else { 
				// The node value was the same as an current node, so dump it.
				flag = true;
			}
		}
	}
}

// Print out a given tree using recursion
void printTree(node *aNode) {
	
	// Recurse down left node till we hit bottom leaf
	if (aNode->left != NULL) {
		printTree(aNode->left);
	}

	// Print the value of the node we are at and every time we move
	// back up

	cout << aNode->value << endl;

	// Traverse down the right branch now recursively
	if (aNode->right != NULL) {
		printTree(aNode->right);
	}
}

The results of this program is three lists being generated. The printTree function I created here simply traverses the individual trees and returns the results in a sorted order. You will notice the first tree has even values, the second has odd values, and the last has prime values. Also note that while we may generate repeating numbers, we remove the duplicates when we go to add the values to the individual trees. By having a value similar to one that already exists, we simply go to our else clause and end the loop without having added it to the tree.

So you might be saying “What in the hell Martyr, what is with this behemoth!? What could it possibly be good for?” Well binary trees are awesome for searching. They take advantage of the fact that you can cut the branches down rather quick by simply knowing if the search value is higher or lower than the current node value. This gives excellent timing and works great for massive, as well as small, trees.

By putting them together like this you could essentially leverage the idea of binary searching and array/vector iterating together. Iterate to the proper tree of values, then conduct your search. The trees don’t need to be the same type either. One could be a collection of baseball card items and another could be a collection of integers. Simply zip to the right element in the vector and conduct the search.

This could also form the basis of a index system and one similar to what Google uses with regards to their index servers splitting up search results to the appropriate machines. If each tree was a portion of a larger index, you could skip to slot “s-t” of the vector, then conduct a binary search on the subset of results that are between “s” and “t”.

But mainly I put this together for fun and to help those out there that might be interested in using vectors, trees, nodes and how they might link together in new and wonderful ways.

I hope you enjoyed the little guy and feel free to use him at your leisure. Just be sure to feed him once in awhile. I had one of these little nasty things try to chew my leg off the other day. I had to put it down. 🙁

Thanks for reading.