CODEWITHSUNDEEP
cbinary-treestructure
starkk92
starkk92

Reputation: 5924

Unable to print all the elements in the binary tree

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>

struct node *create_node(int );
struct node *add_node(struct node *,int );
void asce_order(struct node *);
void desc_order(struct node *);


struct node
{
    int data;
    int count;
    struct node *next,*previous;
};

struct node *create_node(int value)
{
    struct node *pnode=(struct node *)malloc(sizeof(node));
    pnode->data=value;
    pnode->count=1;
    pnode->next=pnode->previous=NULL;
return pnode;
}

struct node *add_node(struct node *pnode,int value)
{
    if(pnode==NULL)
    {
        pnode=create_node(value);
        return pnode;
    }

    else if(pnode->data == value)
    {
        (pnode->count)++;
        return pnode;
    }
    else
    {
        if(pnode->data>value)
        {
            return add_node(pnode->previous,value);
        }
        else 
        {
            return add_node(pnode->next,value);
        }
    }


}

void asce_order(struct node *pnode)
{
    int i;
    if(pnode->previous!=NULL)
    asce_order(pnode->previous);

    for(i=0;i<pnode->count;i++)
    printf("%d\n",pnode->data);

    if(pnode->next!=NULL)
    asce_order(pnode->next);
}

void desc_order(struct node *pnode)
{

    int i;
    if(pnode->next!=NULL)
    desc_order(pnode->next);

    for(i=0;i<pnode->count;i++)
    printf("%d\n",pnode->data);

    if(pnode->previous!=NULL)
    desc_order(pnode->previous);
}

void free_variables(struct node *pnode)
{
    if(pnode==NULL)
    return;
    if(pnode->next!=NULL)
    free_variables(pnode->next);
    if(pnode->previous!=NULL)
    free_variables(pnode->previous);

    free(pnode);
}

int main()
{
    int data;
    struct node *head=NULL;
    char option='y';
    int choice;

    while(tolower(option) == 'y')
    {
        printf("enter the data:");
        scanf("%d",&data);
        if(head==NULL)
        head=create_node(data);
        else
        add_node(head,data);
        fflush(stdin);
        printf("enter the option:");
        scanf("%c",&option);    
    }

    printf("enter the choice:\n1.ascending order\n2.Descending order");
    scanf("%d",&choice);
    switch(choice)
    {
        case 1:
        printf("the ascending order:\n");
        asce_order(head);
        break;

        case 2:
        printf("the descending order:\n");
        desc_order(head);
        break;

        default :
        printf("you have entered the wrong choice");
        break;
    }

    free_variables(head);

return 0;
}

**this is the code I have written for sorting numbers using binary trees.It is printing only the head node of the tree.I know the problem is with the add_node function.When I replace the content in add_node with 

    if(value==pnode->data)
{
    (pnode->count)++;
    return pnode;
}
if(value<pnode->data)
{
    if(pnode->previous==NULL)
    {
        pnode->previous=create_node(value);
        return pnode->previous;
    }
    else
    {
        return add_node(pnode->previous,value);
    }
}
else
{
    if(pnode->next==NULL)
    {
        pnode->next=create_node(value);
        return pnode->next;
    }
    else
    return add_node(pnode->next,value);
}

What seems to be the problem in the first code.someone please help me out.thanks**

Upvotes: 0

Views: 268

Answers (2)

Alexey Frunze
Alexey Frunze

Reputation: 62058

The problem is, add_node() does recurse the tree, but doesn't modify it. There isn't a single place in the function where it would change some node's previous or next pointer. How can that modify the tree? It can't.

It should be something like this instead:

struct node *add_node(struct node *pnode, int value)
{
    if (pnode == NULL)
    {
        pnode = create_node(value);
        return pnode;
    }
    else if (pnode->data == value)
    {
        pnode->count++;
        return pnode;
    }

    if (pnode->data > value)
    {
        if (pnode->previous == NULL)
        {
            return pnode->previous = create_node(value);
        }
        return add_node(pnode->previous, value);
    }
    else 
    {
        if (pnode->next == NULL)
        {
            return pnode->next = create_node(value);
        }
        return add_node(pnode->next, value);
    }
}

The entire program with minor fixes, changes and improved formatting:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node *create_node(int);
struct node *add_node(struct node *, int);
void asce_order(struct node *);
void desc_order(struct node *);

struct node
{
    int data;
    int count;
    struct node *next, *previous;
};

struct node *create_node(int value)
{
    struct node *pnode = malloc(sizeof(struct node));
    pnode->data = value;
    pnode->count = 1;
    pnode->next = pnode->previous = NULL;
    return pnode;
}

struct node *add_node(struct node *pnode, int value)
{
    if (pnode == NULL)
    {
        pnode = create_node(value);
        return pnode;
    }
    else if (pnode->data == value)
    {
        pnode->count++;
        return pnode;
    }

    if (pnode->data > value)
    {
        if (pnode->previous == NULL)
        {
            return pnode->previous = create_node(value);
        }
        return add_node(pnode->previous, value);
    }
    else 
    {
        if (pnode->next == NULL)
        {
            return pnode->next = create_node(value);
        }
        return add_node(pnode->next, value);
    }
}

void asce_order(struct node *pnode)
{
    int i;

    if (pnode->previous != NULL)
    {
        asce_order(pnode->previous);
    }

    for(i = 0; i < pnode->count; i++)
    {
        printf("%d\n", pnode->data);
    }

    if(pnode->next != NULL)
    {
        asce_order(pnode->next);
    }
}

void desc_order(struct node *pnode)
{
    int i;

    if (pnode->next != NULL)
    {
        desc_order(pnode->next);
    }

    for (i = 0; i < pnode->count; i++)
    {
        printf("%d\n", pnode->data);
    }

    if (pnode->previous != NULL)
    {
        desc_order(pnode->previous);
    }
}

void free_variables(struct node *pnode)
{
    if (pnode == NULL)
    {
        return;
    }

    if (pnode->next != NULL)
    {
        free_variables(pnode->next);
    }

    if (pnode->previous != NULL)
    {
        free_variables(pnode->previous);
    }

    free(pnode);
}

int main(void)
{
    struct node *head=NULL;

    head = add_node(head, 2);
    add_node(head, 0);
    add_node(head, 6);
    add_node(head, 7);
    add_node(head, 4);
    add_node(head, 2);
    add_node(head, 8);
    add_node(head, 3);
    add_node(head, 7);
    add_node(head, 5);
    add_node(head, 0);
    add_node(head, 1);
    add_node(head, 6);
    add_node(head, 9);

    printf("ascending order:\n");
    asce_order(head);

    printf("descending order:\n");
    desc_order(head);

    return 0;
}

Output (ideone):

ascending order:
0
0
1
2
2
3
4
5
6
6
7
7
8
9
descending order:
9
8
7
7
6
6
5
4
3
2
2
1
0
0

Upvotes: 1

timrau
timrau

Reputation: 23058

The problem is here in add_node():

else
{
    if(pnode->data>value)
    {
        return add_node(pnode->previous,value);
    }
    else 
    {
        return add_node(pnode->next,value);
    }
}

If pnode->previous or pnode->next is NULL, then the node created by add_node() is not linked to pnode at all. You could modify it as follows:

else
{
    if(pnode->data>value)
    {
        pnode->previous = add_node(pnode->previous,value);
    }
    else 
    {
        pnode->next = add_node(pnode->next,value);
    }
    return pnode;
}

Upvotes: 1

Related Questions