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
No comments:
Post a Comment