 # 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 »