C Binary Tree

« Previous Tutorial Next Tutorial »

Binary trees are the special trees because, when sorted, they lend themselves to rapid searches, insertions, and deletions. Since each item in a tree consists of information along with a link to the left member and a link to the right member. Here this figure shows a small tree.

The root is the first item in the tree. Each item is called a node of tree, and any piece of tree is called a subtree. A node that has no subtrees attached to it is called a terminal node or leaf. The height of the tree is equal to the number of layers deep that its roots grow.

Note - A tree is only a way to logically organize the data in the memory, and the memory is linear.

The binary tree is a special form of linked list. Items can be inserted, deleted, and accessed in any order.

Most functions that uses the trees are recursive, because the tree itself a recursive data structure. That is, each subtree is itself a tree.

How a tree is ordered depends on how it is going to be accessed. The process of accessing each node in a tree is called a tree traversal. See the following tree.

There are the following three ways to traverse a tree:

inorder - using inorder, you visit the left subtree, the root, and then the right subtree
preorder - using preorder, you visit the root, the subtree and then the right subtree
postorder - using postorder, you visit the left subtree, the right subtree, and then the root

Using each method, the order of access for the tree is show here :

inorder		a b c d e f g
preorder	d b a c f e g
postorder	a c b e g f d

Even though, a tree need not be sorted, most uses require this. Of course, what constitutes a sorted tree depends on how you will be traversing the tree.

The following function, stree(), builds a sorted binary tree:

struct tree
{
	char info;
	struct tree *left;
	struct tree *right;
};

struct tree *stree(struct tree *root,struct tree *r,char info)
{
	if(!r)
	{
		r = (struct tree *)
		malloc(sizeof(struct tree));
		if(!r)
		{
			printf("Out of Memory..!!\n");
			exit(1);
		}
		r->left = NULL;
		r->right = NULL;
		r->info = info;
		if(!root)
			return r;    /* first entry */
		if(info < root->info)
			root->left = r;
		else
			root->right = r;
		return r;
	}
	if(info < r->info)
		stree(r, r->left, info);
	else
		stree(r, r->right, info);
	return root;
}

C Binary Tree Example

Here is the complete example demonstrating binary tree in C. This program construct a binary tree in C language.

/* C Binary Tree - Binary Tree Program Example
 * This program demonstrates the concept of
 * binary tree in C programming
 */

#include<stdio.h>
#include<conio.h>
#include<assert.h>
#include<stdlib.h>

#define ARRAY_SIZE 10

typedef char DATA;

struct node
{
	DATA d;
	struct node *left;
	struct node *right;
};

typedef struct node NODE;
typedef NODE *BINARY_TREE;

BINARY_TREE newnode(void);
BINARY_TREE init_node(DATA d, BINARY_TREE p1, BINARY_TREE p2);
BINARY_TREE create_tree(DATA a[], int i, int size);
void preorder (BINARY_TREE root);
void inorder (BINARY_TREE root);
void postorder (BINARY_TREE root);

BINARY_TREE new_node()
{
	return((BINARY_TREE)malloc(sizeof(NODE)));
}

BINARY_TREE init_node(DATA d1, BINARY_TREE p1, BINARY_TREE p2)
{
	BINARY_TREE temp;

	temp = new_node();
	temp->d = d1;
	temp->left = p1;
	temp->right = p2;
	return temp;
}

BINARY_TREE create_tree(DATA a[], int i, int size)
{
	if(i >= size)
	{
		return NULL;
	}
	else
	{
		return(init_node(a[i], create_tree(a, 2*i+1, size), create_tree(a, 2*i+2, size)));
	}
}

void preorder(BINARY_TREE root)
{
	if(root != NULL)
	{
		printf("%c ", root->d);
		preorder(root->left);
		preorder(root->right);
	}
}

void inorder(BINARY_TREE root)
{
	if(root != NULL)
	{
		inorder(root->left);
		printf("%c ", root->d);
		inorder(root->right);
	}
}

void postorder(BINARY_TREE root)
{
	if(root != NULL)
	{
		postorder(root->left);
		postorder(root->right);
		printf("%c ", root->d);
	}
}

void main()
{
	char arr[ARRAY_SIZE];
	BINARY_TREE root;
	int lop;
	clrscr();

	printf("Enter %d characters: ", ARRAY_SIZE);
	for(lop=0; lop<ARRAY_SIZE; lop++)
	{
		scanf("%c", &arr[lop]);
		fflush(stdin);
	}
	root = create_tree(arr, 0, ARRAY_SIZE);
	assert(root != NULL);
	printf("\n");
	printf("Inorder:\t");
	inorder(root);
	printf("\n");
	printf("Preorder:\t");
	preorder(root);
	printf("\n");
	printf("Postorder:\t");
	postorder(root);
	printf("\n");

	getch();
}

Here is the sample run of the above C program:

C Online Test

« Previous Tutorial Next Tutorial »