CodeProject
Sample Output is shown above. This program will run in windows only. For Linux you must write your own gotoxy function.
Sample Output is shown above. This program will run in windows only. For Linux you must write your own gotoxy function.
#include<stdio.h>
#include<stdlib.h>
#define MAX_PRINT_LEVEL 5
#include <windows.h>
void gotoxy(int col, int row) //starting from 0
{
COORD
coord;
coord.X =
col;
coord.Y =
row;
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);
}
struct tree_node
{
struct tree_node *left,*right;
int data;
};
typedef struct tree_node
TNODE;
TNODE* create_tree(int
*input,int num);
void add_num(TNODE *node,int
*input,int num);
void print_tree(TNODE *root,int
num,int col,int
row);
int print_subsets(TNODE *root,int
sum,int *input,int
*subsets,int index,int
num);
int pow(int a, int b);
//array to store all possible sums,
remove if not neeeded
/*int *sums,sum_count=0;*/
int main()
{
int sum;
int *input,num;
int *subsets;
TNODE
*root=NULL;
int i;
printf("\nHOW MANY NUMBERS: ");
scanf("%d",&num);
if(num<0)
{
printf("\nERROR: Invalid num value...\n\n");
exit(1);
}
if( (input = (int*)malloc(num*sizeof(int))) ==
NULL)
{
printf("\n\nERROR: MEMORY NOT ALLOCATED\n\n");
exit(1);
}
if( (subsets = (int*)malloc(num*sizeof(int))) ==
NULL)
{
printf("\n\nERROR: MEMORY NOT ALLOCATED\n\n");
exit(1);
}
printf("\nEnter numbers: \n");
for(i=0;i<num;i++)
{
printf("NUM[%d] : ",i);
scanf("%d",&input[i]);
}
//array to store all possible sums, remove if not neeeded
/*if( (sums = (int*)malloc(pow(2,num)*sizeof(int))) ==
NULL)
{
printf("\n\nERROR:
MEMORY NOT ALLOCATED\n\n");
exit(1);
}*/
root =
create_tree(input,num);
system("cls");
print_tree(root,num,0,0);
printf("\n\nINPUT ARRAY :");
for(i=num-1;i>=0;i--)
printf(" %d",input[i]);
printf("\n\n");
//print all sums possible
/*for(i=sum_count-1;i>=0;i--)
{
if(print_subsets(root,sums[i],input,subsets,num,num))
printf("\n**********
SUBSETS WITH SUM = %d **********",sums[i]);
}*/
//print a particular
sum
printf("\n\nENTER SUM: ");
scanf("%d",&sum);
printf("\n********** SUBSETS WITH SUM = %d **********",sum);
if(!print_subsets(root,sum,input,subsets,num,num))
printf("\n\nOOPS : NO SUBSET CAN BE FOUND");
printf("\n\n\n");
return 0;
}
int print_subsets(TNODE *node,int
sum,int *input,int
*subsets,int index,int
num)
{
int i,found=0,a,b;
if(node->left==NULL && node->right ==
NULL)
{
if(node->data == sum)
{
printf("\n{ ");
for(i=0;i<num;i++)
if(subsets[i] == 1)
{
found
= 1;
printf("%d,",input[i]);
}
if(found)
printf("\b } ");
else
printf("NULL SET }");
return 1;
}
else
return 0;
}
if(node->left)
{
subsets[index-1]
= 1;
a=print_subsets(node->left,sum,input,subsets,index-1,num);
}
if(node->right)
{
subsets[index-1]
= 0;
b=print_subsets(node->right,sum,input,subsets,index-1,num);
}
return (a||b);
}
void print_tree(TNODE *root,int
level,int col,int
row)
{
int gap,pos,slash;
int i;
int bcol,brow;
if(level>MAX_PRINT_LEVEL)
{
printf("\nTree cant be displayed for level > %d...",MAX_PRINT_LEVEL);
return;
}
gap =
pow(2,level) - 1;
bcol =
col;
brow =
row;
col=col+gap;
gotoxy(col,row);
printf("%d",root->data);
if(root->left)
{
slash
= pow(2,level-1);
for(i=0;i<slash;i++)
{
gotoxy(--col,++row);
printf("/");
}
print_tree(root->left,level-1,bcol,row+1);
}
if(root->right)
{
col
= bcol+gap;
row
= brow;
slash
= pow(2,level-1);
for(i=0;i<slash;i++)
{
gotoxy(++col,++row);
printf("\\");
}
if(level>1)
print_tree(root->right,level-1,bcol+gap+1,row+1);
else
print_tree(root->right,level-1,bcol+gap+1,row+2);
}
}
int pow(int a, int b)
{
int ans=1;
if(b==0)
return 1;
while(b>0)
{
ans
= ans * a;
b--;
}
return ans;
}
TNODE* create_tree(int
*input,int num)
{
TNODE
*temp;
int i;
temp =
(TNODE*)malloc(1*sizeof(TNODE));
temp->data=0;
temp->left=NULL;
temp->right=NULL;
add_num(temp,input,num);
return temp;
}
void add_num(TNODE *node,int
*input,int num)
{
if(num == 0)
{
//array to store all possible sums, remove if not neeeded
/*sums[sum_count++] = node->data;*/
return;
}
node->left=(TNODE*)malloc(1*sizeof(TNODE));
node->right=(TNODE*)malloc(1*sizeof(TNODE));
node->left->data
= node->data + input[num-1];
node->left->left
= NULL;
node->left->right
= NULL;
node->right->data
= node->data + 0;
node->right->left
= NULL;
node->right->right
= NULL;
add_num(node->left,input,num-1);
add_num(node->right,input,num-1);
}
