Dynamic allocation of adjacency matrix and traversing a list

[gruba]

Homework Statement

I have a binary tree. I need to print a path of a doubly circular linked list (0 and 1) after every user input.
I have a code in which user inputs data about one person. For example, when user inputs 2 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 (dynamic allocation for matrix)? Then matrix is 3 x 3.

I would highly appreciate is someone could help, I am stuck on it.

Homework Equations

-Binary trees
-Graphs
-Linked lists

The Attempt at a Solution

1. Definition of structures:

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

2. Functions:

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");
}

I think that these two functions are not well implemented:

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);
}

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");
}

3. main()

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')
  {
  //print adjacency matrix of a graph?
  }
  else if(option=='E')
  {
  printf("end of program.");
  deleteTree(root);
  free(nperson);
  break;
  }
  }
  return 0;
}

Thanks for replies.

 

[KataKoniK]

Hello! I am a scientist and I would be happy to help you with your question. First, let's take a look at your code. From what I can see, you have defined the necessary structures and have some functions to add nodes to a binary tree and print a linked list. However, I noticed that you have not implemented the function to print the adjacency matrix for a graph.

To print the adjacency matrix for a graph, you will need to first create a 2D array to hold the matrix. The size of the array will depend on the number of nodes in your graph. In this case, you mentioned that the user can input a dynamic number of nodes, so you will need to use dynamic allocation to create the array. Once you have the array, you can use a nested loop to iterate through each row and column and fill in the matrix. The value at each position in the matrix will depend on whether there is an edge between the two corresponding nodes. For example, if there is an edge between nodes 1 and 2, then the value at position (1,2) and (2,1) in the matrix will be 1. If there is no edge, then the value will be 0.

Now, let's address the issue with printing the path in your binary tree. From what I can see, you are using a recursive function called pathToNode() to find the path from the root to a specific node. However, I think there is a small mistake in your implementation. In the if statement where you check if the current node is equal to the desired node, you set the variable 'found' to 1, but you do not actually add the current node to the list. This means that the path will not include the desired node. To fix this, you can add the line 'addElementToList(list, 0);' before you return from the function. This will add the current node to the list before going back to the previous level of recursion. Also, in your addNodeToPath() function, you are creating a new node with NULL data instead of using the node that was passed in as a parameter. This means that the data of the new node will not be set correctly. To fix this, you can change the line 'root->left = formTreeNode(NULL);' to 'root->left = tree_node;' and do the same for the 'root->right' line. This will make