Click here to Skip to main content
14,666,459 members
Rate this:
Please Sign up or sign in to vote.
See more:
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')
    {
        //print adjacency matrix of a graph
    }
    else if(option=='E')
    {
        printf("end of program.");
        deleteTree(root);
        free(nperson);
        break;
    }
    }
    return 0;
}
Posted

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100