In this blog we are going to learn how to build and access Binary search tree using tsearch function.  The tsearch() function requires search.h header file.

#include <search.h>
void *tsearch(const void *key, void **rootp,
                       int (*compar)(const void *, const void *));
  1. The key argument is a pointer to an element.
  2. If the key is present in the node of the tree , then it returns pointer of the found node.
  3. If key is not in the tree then a new node is created with the value of key, and a pointer to this node is returned.
  4. The rootp argument points to a variable that points to the root node of the tree.
  5. The third argument takes a function pointer. This comparator function compares two integers and return an integer less than, equal to or greater than 0. It depends upon whether the first argument is to be considered less than, equal to or greater than the second argument.

Build and Access Binary search tree using tsearch function Example

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

// node of the tree 
struct data {
    int id;
    char *str;
};

static int
compare (const void *a, const void *b) {
    const struct data *data_a = a, *data_b = b;

    if (data_a->id < data_b->id) {
        return -1;
    } else if (data_a->id > data_b->id) {
        return 1; 
    } else {
        return 0;
    }
}

int main (int argc, char **argv) {
    void *tree = NULL;
    struct data *d1, *d2;

    d1 = malloc(sizeof(struct data));
    d1->id = 1;
    d1->str = "Hello";
    tsearch(d1, &tree, compare);
    
    d2 = malloc(sizeof(struct data));
    d2->id = 2;
    d2->str = "World";
    tsearch(d2, &tree, compare);

    return 0;
}
                                                                                                                                

More about tsearch() library function

  1.  tdelete() frees the memory required for the node in the tree.
  2. tfind() returns a pointer to the item, or NULL if no match is found.
  3. We can use twalk() function to print binary search tree. Let us see sample example.
#include <stdio.h>
#include <search.h>
#include <stdlib.h>

// node of the tree 
struct data {
    int id;
    char *str;
};

static int
compare (const void *a, const void *b) {
    const struct data *data_a = a, *data_b = b;

    if (data_a->id < data_b->id) {
        return -1;
    } else if (data_a->id > data_b->id) {
        return 1;
    } else {
        return 0;
    }
}

void static print(const void *root, const VISIT which, const int depth);

int main (int argc, char **argv) {
    void *tree = NULL;
    struct data *d1, *d2;

    d1 = malloc(sizeof(struct data));
    d1->id = 1;
    d1->str = "Hello";
    tsearch(d1, &tree, compare);

    d2 = malloc(sizeof(struct data));
    d2->id = 2;
    d2->str = "World";
    tsearch(d2, &tree, compare);

    twalk(tree,print);
    // free tree
    tdestroy(tree, free);
    return 0;
}

void static print(const void *root, const VISIT which, const int depth)
{
    struct data *e = *((struct data **) root);

    switch (which) {
    case leaf:
    case postorder:
        printf("Depth: %d. data:\n", depth);
        printf("\t%d, %s\n", e->id, e->str);
        break;
    default:
        break;
    }
}

Ref:

Learn c from our blogs

https://www.ibm.com/support/knowledgecenter/en/SSLTBW_2.3.0/com.ibm.zos.v2r3.bpxbd00/rtsear.htm



Related Contents to follow