I have a binary tree which has five nodes. First node has two children.
Path on the left is 0 and on the right is 1. Second node is on the left, and third
is on the right. Node2 has one child on the right, which is Node 4.
Node 4 has one child which is on the left (Node5).
Node 3 has no children.
I need to print a path of a list (0 and 1) after every user input.
I have a code in which user inputs data about one person. When user inputs elements,
the path should be 0->1.
In my code, it won't print any path.
Also, how to print adjacency matrix for a graph for the given binary tree. I know to do it for five nodes (full tree), but what if the user enters three nodes? Then matrix is 3 x 3.
Here is my code,
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct
{
char name[30],surname[30],id[101];
}PERSON;
typedef struct tree_node
{
PERSON person;
struct tree_node *left,*right;
}TREE_NODE;
typedef struct list_node
{
int info;
struct list_node *next,*previous;
}LIST_NODE;
typedef struct list
{
LIST_NODE *head,*tail;
int n;
}LIST;
int returnFirstElementOfList(LIST *list)
{
if(list->head==NULL)
return -1;
LIST_NODE *list_element=list->head;
if(list->head==list->tail)
list->head=list->tail=NULL;
else
{
list->tail->next=list->head->next;
list->head->next->previous=NULL;
list->head=list->head->next;
}
list->n--;
int info=list_element->info;
free(list_element);
return info;
}
void addElementToList(LIST *list,int element)
{
LIST_NODE *list_element=(LIST_NODE *)malloc(sizeof(LIST_NODE));
list_element->info=element;
list_element->previous=list_element->next=NULL;
if(list->head==NULL)
list->head=list->tail=list_element;
else
{
list_element->next=list->head;
list_element->previous=list->tail;
list->tail->next=list_element;
list->tail=list_element;
}
list->n++;
}
void pathToNode(LIST *list,TREE_NODE *tree_node,TREE_NODE *root,int *found)
{
if(root==NULL)
return;
if(root==tree_node)
*found=1;
addElementToList(list,0);
pathToNode(list,tree_node,root->left,found);
if(*found==0)
{
returnFirstElementOfList(list);
addElementToList(list,1);
pathToNode(list,tree_node,root->right,found);
}
if(*found==1)
returnFirstElementOfList(list);
}
TREE_NODE *formTreeNode(PERSON *person)
{
TREE_NODE *tree_node=(TREE_NODE *)malloc(sizeof(TREE_NODE));
tree_node->person=*person;
tree_node->left=NULL;
tree_node->right=NULL;
return tree_node;
}
TREE_NODE *addNodeToTree(TREE_NODE *root,TREE_NODE *person)
{
if(root==NULL)
return person;
if(strcmp(root->person.id,person->person.id)>=0)
root->left=addNodeToTree(root->left,person);
else
root->right=addNodeToTree(root->right,person);
return root;
}
void addNodeToPath(LIST *list,TREE_NODE *tree_node,TREE_NODE *root)
{
if(root==NULL)
return;
if(list->n==1)
{
int path=returnFirstElementOfList(list);
if(path==0)
root->left=tree_node;
else
root->right=tree_node;
}
int path=returnFirstElementOfList(list);
if(path==0)
{
if(root->left==NULL)
root->left=formTreeNode(NULL);
addNodeToPath(list,tree_node,root->left);
}
else
{
if(root->right==NULL)
root->right=formTreeNode(NULL);
addNodeToPath(list,tree_node,root->right);
}
}
void initList(LIST *list)
{
list->head=NULL;
list->tail=NULL;
list->n=0;
}
PERSON *inputPerson()
{
PERSON *person=(PERSON *)malloc(sizeof(PERSON));
printf("name:");
scanf("%s",person->name);
printf("surname:");
scanf("%s",person->surname);
printf("ID:");
scanf("%s",person->id);
return person;
}
void deleteTree(TREE_NODE *root)
{
if(root==NULL)
return;
deleteTree(root->left);
deleteTree(root->right);
free(root);
}
void printList(LIST list)
{
int i=0;
LIST_NODE *head=list.head;
printf("Path:");
while(head != NULL && i<list.n)
{
printf("%d",head->info);
head=head->next;
i++;
}
printf("\n");
}
int main()
{
char option;
PERSON *person=NULL;
int n=0,c=10,found=0,i=0;
TREE_NODE *node=NULL;
TREE_NODE *root=NULL;
TREE_NODE **nperson=(TREE_NODE **)malloc(c * sizeof(TREE_NODE *));
while(1)
{
fflush(stdin);
printf("enter option:");
scanf("%c",&option);
if(option=='A')
{
LIST list;
initList(&list);
person=inputPerson();
if(n+1 > c)
nperson=realloc(nperson,(c=c+10) * sizeof(TREE_NODE *));
node=formTreeNode(person);
nperson[n]=node;
root=addNodeToTree(root,node);
found=0;
pathToNode(&list,node,root,&found);
printList(list);
n++;
}
else if(option=='M')
{
}
else if(option=='E')
{
printf("end of program.");
deleteTree(root);
free(nperson);
break;
}
}
return 0;
}