Monday, November 15, 2010

Implementing Binary Trees in C

This is a program that I had in my mind for almost 3 years before I actually implemented it.
This program uses RECURSION to implement most of the algorithms here.
The DrawTree function is the one that draws the tree. It's based on the simple concept that at the Root Level we have just one node, two at the next, 4 at the next, in general 2 to the power h at level h.
// *******************************Trees.c***********************************


#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<graphics.h>
#include<math.h>
typedef struct mynode
{
int value;
struct mynode* left;
struct mynode* right;
}TreeNode;
void AddNode(TreeNode** root,int n);
void InOrder(TreeNode* root);
void PreOrder(TreeNode* root);
void PostOrder(TreeNode* root);
int Max(int a,int b);
int height(TreeNode* root);
void DrawTree(TreeNode* root,int yPosition,int xPosition,int dy,int dx,int level);
void main()
{
int gdriver = DETECT, gmode, errorcode;
TreeNode *root=NULL;
char ch=`1`;
int n;
clrscr();
while(ch!=27)
{
switch(ch)
{
case `A`:
case `a`:printf("\nEnter value to Add = ");
    scanf("%d",&n);
    AddNode(&root,n);
    break;
case `I`:
case `i`:printf("\n Inorder = ");
    InOrder(root);
    printf("\n");
    break;
case `P`:
case `p`:printf("\n PreOrder=");
     PreOrder(root);
     printf("\n");
     break;
case `T`:
case `t`:printf("\n PostOrder=");
     PostOrder(root);
     printf("\n");
     break;
case `d`:
case `D`:initgraph(&gdriver, &gmode, "");
    DrawTree(root,10,getmaxx()/2,getmaxy()/height(root),getmaxx()/2,1);
    getch();
    closegraph();
}
ch=getch();
}
}
void AddNode(TreeNode** root,int n)
{
if(*root==NULL)
{
*root=malloc(sizeof(TreeNode));
(*root)->value=n;
(*root)->left=NULL;
(*root)->right=NULL;
return;
}
if(n<(*root)->value)
AddNode(&(*root)->left,n);
else
AddNode(&(*root)->right,n);
}
void InOrder(TreeNode* root)
{
if(root==NULL)
return;
InOrder(root->left);
printf("%d,",root->value);
InOrder(root->right);
}
void PreOrder(TreeNode* root)
{
  if(root==NULL)
  return;
 printf("%d,",root->value);
 PreOrder(root->left);
 PreOrder(root->right);
}
void PostOrder(TreeNode* root)
{
   if(root==NULL)
   return;
  PostOrder(root->left);
 PostOrder(root->right);
printf("%d,",root->value);
}
void DrawTree(TreeNode* root,int yPosition,int xPosition,int dy,int dx,int level)
{
char s[80];
int radius=10,cx,cy,adjust=5;
if(root==NULL)
return;
if(level==1)
{
circle(xPosition,yPosition,radius);
itoa(root->value,s,10);
outtextxy(xPosition-adjust,yPosition-adjust,s);
DrawTree(root->left,yPosition,xPosition,dy,-dx/2,level+1);
DrawTree(root->right,yPosition,xPosition,dy,dx/2,level+1);
}
else
{
cx=xPosition + dx;
cy=yPosition + dy;
circle(cx,cy,radius);
itoa(root->value,s,10);
outtextxy(cx-adjust,cy-adjust,s);
line(xPosition,yPosition,cx,cy);
DrawTree(root->left,cy,cx,dy,-abs(dx)/2,level+1);
DrawTree(root->right,cy,cx,dy,abs(dx)/2,level+1);
}
}
int Max(int a,int b)
{
if(a>b)
return(a);
else
return(b);
}
int height(TreeNode* root)
{
if(root==NULL)
return(0);
return(1 + Max(height(root->left),height(root->right)));
}



// *******************************Trees.c***********************************
There is a supplementary post

Breadth First traversal in Binary Trees.

No comments:

Post a Comment