Binary tree with structs (in C)

2
votes

I have a binary tree of structs. The struct is 

    typedef struct hashtag {
        char *name;
        int acc;
    } *Item;

The nodes are organized by the string. I want to print the node which has the highest acc but is first in alphabetical order. My code so far:

    Item search_max(link h) {
        int max;
        char *word;
        Item hashtag = (Item)malloc(sizeof(struct hashtag));
        Item left = (Item)malloc(sizeof(struct hashtag));
        Item right = (Item)malloc(sizeof(struct hashtag));
        hashtag = h->item;
        max = h->item->acc;
        word = h->item->name;
        if (h == NULL) 
            return 0;
        left = search_max(h->l);
        if (max == left->acc && less(left->name, word))
            word = left->name;
        if (max < left->acc){
            max = left->acc;
            word = left->name;
        }
        right = search_max(h->r);
        if (max == right->acc && less(right->name, word))
            word = right->name;
        if (max < right->acc){
            max = right->acc;
            word = right->name;
        }
        hashtag->acc = max;
        hashtag->name = word;
        return hashtag;
    }

h is the head of the tree and less is 

    #define less(a,b) (strcmp(a,b) < 0)

and link is 

    typedef struct node{
        Item item;
        struct node *l;
        struct node *r;
    } *link;

It gives a segmentation fault(core dumped). Previously I tried the same code without allocating memory for hashtag, left or right (same error).

2
cstructbinary-treebinary-search-tree
Item hashtag = (Item)malloc(sizeof(struct hashtag)); Item left = (Item)malloc(sizeof(struct hashtag)); Item right = (Item)malloc(sizeof(struct hashtag)); hashtag = h->item; You are leaking memory here. and : Item search_max(link h) { what is link ? - joop
@joop I edited my question and now I also have the code of link. How can I fix the problem of memory leaking? Sorry for the question but I'm new at this - Anna_
Note: if your tree is sorted on item->name, the only way to find the element with the max(item->acc) is by inspecting all nodes-->>items. (or: by first re-sorting the tree on item->acc) (which is what you attempt to do, BTW) - joop
but I'm inspecting all nodes. I had a similar function just to find the max of the acc and it worked. It was when I tried to find the name that it stopped working - Anna_
Time to learn how to use a debugger... - Basile Starynkevitch

2 Answers

1
votes

You are allocating memory for the Item pointers and then overwriting the pointers. You have two choices: You could use item values or you could use pointers correctly:

For the first choice you would have to remove the * from the Item typedef and change all usages of Items. For the second choice (which is easier in this case) you should remove all mallocs from search_max. Then use:

Item left = search_max(h->l);
...

Note that you can not locally check the second criteria (lexicographic string order). Instead you again have two choices: collect all entries that have the highest acc-value into another collection, then when you are done with the tree go through that collection to find that single string. Second choice: recursively pass info through all calls to search_max - the info is the current string and its acc-value.

0
votes

The result is either the item in the current node, or an item under its left- or right subtree. Divide and conquer: (I removed the typedeffed pointers for clarity and sanity)

NOTE: there are no malloc()s needed. You are only examining an existing tree, not adding anything to it.

struct item {
        char *name;
        int acc;
        };

struct node {
        struct item *item;
        struct node *left, *right;
        };

int items_cmp( struct item *one, struct item *two)
{
if (one->acc < two->acc) return -1; /* two is better */
if (one->acc > two->acc) return 1;  /* one is better */
return strcmp(one->name, two->name);
}

struct item * find_max( struct node *np)
{
struct item *ret, *sub;

if (!np) return NULL; /* stop the recursion ! */

ret = np->item;
sub = find_max(np->left);
if ( sub && items_cmp(ret, sub) > 0)
        ret = sub;

sub = find_max(np->right);
if ( sub && items_cmp(ret, sub) > 0)
        ret = sub;

return ret;
}