Implementing a Binary Tree


Creating a binary tree is simple once you understand the concept of a tree. The programming is similar to the way we created a linked list using a class and a structure. Since the program will be large we’ll break it down into smaller parts and discuss them separately.


The node:

First of all we need to define our node. The node of a tree is similar to a linked list node except that we will have two pointers in every node of the tree (for the linked list every node had just one pointer). So let’s create a structure to represent our node:

struct node
{
string data;
node *right;
node *left;
};

The basic outline of the tree class:

class tree
{ private: struct node
{
string data;
node *right;
node *left;
};
node *root;
void destroy_tree(node*);

public:

tree( )
{
    root=NULL;
}

~tree( )
{
    destroy_tree(root);
}
};

node *root; This is the pointer which will point to the first node of our tree. It defines the starting memory location of our binary tree.

void destroy_tree(node*); We’ll need to destroy the tree (using the delete function) and this function will serve the purpose. We will call this function from the destructor of the tree class. The reason we make this private is because we don’t want to allow a user to access this function. This will be explained later.

The constructor: When a tree is created we don’t have any nodes in the tree. So the root pointer should point to NULL (otherwise it would be pointing to some unknown memory location).


Member Functions

Next we’ll need some member functions. The basic functions are:

First let’s write the code for adding a new node to our tree:

Before starting with the code let’s write a pseudo algorithm (it is always a good practice to write algorithms before you jump into coding- it’ll save a lot of time).

  1. Create a new node and assign the value to be stored to ‘data’.
  2. Set the new node’s right and left pointers to NULL. Next we need to decide where to insert this node.
  3. Check if root is NULL. If so then make the root point to this node (i.e. this will now become the first node of the tree).
  4. Else compare the value of the node with the root node (the first node). If the value is less than the root node value then we’ll have to insert this node into the left side. Else it’ll have to go into the right side.
  5. Let’s assume that our value is greater than the root node. So, we’ll have to insert it to the right of the root node. Check if the right pointer of the root node is NULL. If so then we can simply make the right pointer point to our new node. If it is not NULL it means that some node is already present to the right of the root node. So compare the value with the existing node value and repeat the above steps (steps 3, 4 and 5) till you find a vacant place to insert the node.

You must have guessed by now that we’ll need an iterative loop to insert the new node.

void tree::addnode(string str)
{
	node *newnode,*ptr;	//Creating a new node
	newnode=new node;
	newnode->data=str;
	newnode->left=NULL;
	newnode->right=NULL;

	if (root==NULL)		//Determining the position to insert the new node
	{
		root=newnode;
	}
	else
	{
		ptr=root;
		while (ptr!=NULL)
		{
			if (newnode->data < ptr->data)
			{
				if (ptr->left==NULL)
				{
					ptr->left=newnode;
					ptr=NULL;
				}
				else
				{
					ptr=ptr->left;
				}
			}
			else
			{
				if (ptr->right==NULL)
				{

					ptr->right=newnode;
					ptr=NULL;
				}
				else
				{
					ptr=ptr->right;
				}
			}
		}
	}
}

The code might seem complicated but it’s actually easy if you’ve understood the algorithm for inserting a new node.

Remember: Inserting a new node means that all we need to do is make the pointers point to the correct addresses.


The destructor

In our destructor we pass the root pointer as argument to the destroy_tree( ) function (because we want to destroy all the nodes from the root onwards). The algorithm to destroy a tree is as follows:

The algorithm may seem a little complex to implement at first sight. But if you analyze the procedure carefully then you’ll find a recurring pattern. Recursion would help us to solve this problem easily. The code will be:

void tree::destroy_tree(node *delnode)
{
    if (delnode->left!=NULL)
    {
                destroy_tree(delnode->left);
    }

    if (delnode->right!=NULL)
    {
                destroy_tree(delnode->right);
    }
cout<<endl<<"Deleting the node: "<<delnode->data;
delete delnode;
}

We just keep on recursively calling the same destroy function. Take an example and think like the compiler to understand the logic.

The main( ) function:

int main( )
{
tree names;
names.addnode("michael");
names.addnode("srinath");
return 0;
}

The output will be:

Deleting the node: srinath

Deleting the node: michael

As expected, the child node (srinath) is deleted first before the root node is deleted.

Remember: The tree structure is decided based on the way we store values in the tree. In the above example, if srinath were inserted first into the tree then michael would have been inserted to the left of srinath.


Go back to the Contents Page 2


Copyright © 2004 Sethu Subramanian All rights reserved.