Binary tree – An introduction

0 / 1672
Binary search tree

 

Binary Trees:

Today, in this blog we will discuss about binary trees. Binary tree is a data structure in which each node has two successors called the left and right child.

Below is a small image showing what a typical binary tree is like.

Binary tree

Binary tree

 

The above diagram just shows a binary tree which is different than a binary search tree. Difference between the two is the former is un-ordered and hence not fit for fast lookup of nodes however, binary search tree satisfies the criteria that if the child node is greater than the root, then it will be inserted to the right else to the left of the root node as shown in below diagram

Binary search tree

Binary search tree

 

 

Below is a small program that demonstrates creation of binary search tree and traversal , viz. inorder, preorder and postorder

 

C program for binary search tree

#include 
#include 

struct btree
{
int data;
struct btree *leftchild;
struct btree *rightchild;
};


void insert(struct btree **node, int data);
void inorder(struct btree *node);
void preorder(struct btree *node);
void postorder(struct btree *node);


int main()
{
int arr [] = {2,8,4,5,7,6,3};
int index = 0;

struct btree *root = NULL, *newNode = NULL;
int length = sizeof(arr)/sizeof(int);

for(index = 0; index < length; index++)
{
insert(&root, arr[index]);
}

printf("This is the output of inorder traversal :- \n");
inorder(root);
printf("\n");

printf("This is the output of inorder traversal :- \n");
preorder(root);
printf("\n");

printf("This is the output of inorder traversal :- \n");
postorder(root);
printf("\n");

return 0;
}

void insert(struct btree **node, int data)
{
if(*node == NULL)
{
*node = (struct btree *)malloc(sizeof(struct btree));
(*node)->data = data;
(*node)->leftchild = NULL;
(*node)->rightchild = NULL;
}
else
{
if(data > ((*node)->data))
insert(&(((*node)->rightchild)), data);
else
insert(&(((*node)->leftchild)), data);
}
}



void inorder(struct btree *node)
{
if(node != NULL)
{
inorder(node->leftchild);
printf("%d ", node->data);
inorder(node->rightchild);	
}
}



void preorder(struct btree *node)
{
if(node != NULL)
{
printf("%d ", node->data);
inorder(node->leftchild);
inorder(node->rightchild);	
}
}


void postorder(struct btree *node)
{
if(node != NULL)
{
inorder(node->leftchild);
inorder(node->rightchild);
printf("%d ", node->data);	
}
}

The above program simply uses the recursive approach in creating and traversing through the binary search tree.

insert() inserts the node data passed as argument to the right if its greater than the root node else to the left by calling itself recursively. It first allocates memory for the root node, if the tree is empty.

inorder(), preorder() and postorder() all use recursion whereas, the traversing is done by visiting left, root and right in case of inorder,

root, left and right in case of preorder & left, right and root in case of post order.

 

Here is the output of the code: – Btree – Output

 

We will now move a bit ahead and write code for searching and deleting a particular node from a binary search tree. The below program , traverses through the tree, until node is found, frees the node so that there are no memory leaks and returns.

// code to search and delete a node from B search tree
/* CH8PR4.C: Program to insert and delete a node
			 from the binary search tree. */

#include 
#include 
#include 

#define TRUE 1
#define FALSE 0

struct btreenode
{
	struct btreenode *leftchild ;
	int data ;
	struct btreenode *rightchild ;
} ;


void delete ( struct btreenode **, int ) ;
void search ( struct btreenode **, int, struct btreenode **,
				struct btreenode **, int * ) ;


/* deletes a node from the binary search tree */
void delete ( struct btreenode **root, int num )
{
	int found ;
	struct btreenode *parent, *x, *xsucc ;

	/* if tree is empty */
	if ( *root == NULL )
	{
		printf ( "\nTree is empty" ) ;
		return ;
	}

	parent = x = NULL ;

	/* call to search function to find the node to be deleted */
	search ( root, num, &parent, &x, &found ) ;

	/* if the node to deleted is not found */
	if ( found == FALSE )
	{
		printf ( "\nData to be deleted, not found" ) ;
		return ;
	}

	/* if the node to be deleted has two children */
	if ( x -> leftchild != NULL && x -> rightchild != NULL )
	{
		parent = x ;
		xsucc = x -> rightchild ;

		while ( xsucc -> leftchild != NULL )
		{
			parent = xsucc ;
			xsucc = xsucc -> leftchild ;
		}

		x -> data = xsucc -> data ;
		x = xsucc ;
	}

	/* if the node to be deleted has no child */
	if ( x -> leftchild == NULL && x -> rightchild == NULL )
	{
		if ( parent -> rightchild == x )
			parent -> rightchild = NULL ;
		else
			parent -> leftchild = NULL ;

		free ( x ) ;
		return ;
	}

	/* if the node to be deleted has only rightchild */
	if ( x -> leftchild == NULL && x -> rightchild != NULL )
	{
		if ( parent -> leftchild == x )
			parent -> leftchild = x -> rightchild ;
		else
			parent -> rightchild = x -> rightchild ;

		free ( x ) ;
		return ;
	}

	/* if the node to be deleted has only left child */
	if ( x -> leftchild != NULL && x -> rightchild == NULL )
	{
		if ( parent -> leftchild == x )
			parent -> leftchild = x -> leftchild ;
		else
			parent -> rightchild = x -> leftchild ;

		free ( x ) ;
		return ;
	}
}

/*returns the address of the node to be deleted, address of its parent and
   whether the node is found or not */
void search ( struct btreenode **root, int num, struct btreenode **par, struct
		btreenode **x, int *found )
{
	struct btreenode *q ;

	q = *root ;
	*found = FALSE ;
	*par = NULL ;

	while ( q != NULL )
	{
		/* if the node to be deleted is found */
		if ( q -> data == num )
		{
			*found = TRUE ;
			*x = q ;
			return ;
		}

		*par = q ;

		if ( q -> data > num )
			q = q -> leftchild ;
		else
			q = q -> rightchild ;
	}
}

 

Stay tuned for more interesting programming stuff.

 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.
loading...

Related Posts