Click here to Skip to main content
15,116,516 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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,

C++
#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, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900