bintree.c

#include <stdio.h>
#include <stdlib.h>
#include "bintree.h"
#include "queue.h"




int main(void)
{
    bintree_t *bt = newBT(10);
    insert(bt, 5);
    insert(bt, 12);
    insert(bt, 2);
    insert(bt, 7);
    insert(bt, 6);
    insert(bt, 13);
    displayBT(bt);
    return 0;
}


bintree_t *newBT(int i)
{
    bintree_t *t =  (bintree_t *)malloc(sizeof(bintree_t));
    t->left = t->right = NULL;
    t->node = i;
    return t;
}


int search(bintree_t *t, int i)
{
    if (t->node==i) {
        return 1;
    }else if (t->node>i) {
        /* left */
        if (t->left==NULL) {
            return 0;
        }else {
            return search(t->left, i);
        }
    }else {
        /* right */
        if (t->right==NULL) {
            return 0;
        }else {
            return search(t->right, i);
        }
    }
}


void insert(bintree_t *t, int i)
{
    if (t->node>i) {
        if (t->left==NULL)
            t->left = newBT(i);
        else
            insert(t->left, i);
    }else if (t->node<i) {
        if (t->right==NULL)
            t->right = newBT(i);
        else
            insert(t->right, i);
    }
}


void delete(bintree_t *t)
{
    if (t!=NULL) {
        bintree_t *right = t->right;
        bintree_t *left = t->left;
        free(t);
        delete(left);
        delete(right);
    }
}


/* breadth first using queue*/
void displayBT(bintree_t *t)
{
    bintree_t *bt = t;
    bintree_t *dummy = newBT(-1); /* for checking tree depth */
    queue_t *nodes = newQ();
    int has_deeper_elem = 0;
    enqueue(nodes, bt);
    enqueue(nodes, dummy);
    printf("[ ");
    while (nodes->head!=nodes->tail) {
        bintree_t *top = dequeue(nodes);
        if (top==NULL) {
            printf("* ");
            enqueue(nodes, NULL);
            enqueue(nodes, NULL);
            continue;
        }

        if (top->node==-1) {    /* dummy */
            if (!has_deeper_elem) {
                break;
            }
            has_deeper_elem = 0; /* go down one level, so reset the value */
            printf("]\n[ ");
            enqueue(nodes, dummy);
            continue;
        }
        printf("%d ", top->node);
        if (top->left==NULL&&top->right==NULL) {
            enqueue(nodes, NULL);
            enqueue(nodes, NULL);
        }else {
            has_deeper_elem = 1;
            enqueue(nodes, top->left);
            enqueue(nodes, top->right);
        }
    }
    printf("]\n");
}

bintree.h

#ifndef __BINTREE_H__
#define __BINTREE_H__

/* left>right unbalanced tree */
typedef struct bintree_t {
    struct bintree_t *left;
    struct bintree_t *right;
    int               node;
} bintree_t;


bintree_t *newBT(int i);
int search(bintree_t *t, int i);
void insert(bintree_t *t, int i);
void delete(bintree_t *t);
void displayBT(bintree_t *t);


#endif  /* __BINTREE_H__ */

Makefile

# Makefile
bintree: bintree.c queue.c
	gcc bintree.c queue.c

queue.c

#include <stdio.h>
#include <stdlib.h>
#include "bintree.h"
#include "queue.h"




atom_t *newAtom(bintree_t *t)
{
    atom_t *a = (atom_t *)malloc(sizeof(atom_t));
    a->tree = t;
    return a;
}


void deleteAtom(atom_t *a)
{
    free(a);
}


queue_t *newQ(void)
{
    queue_t *q = (queue_t *)malloc(sizeof(queue_t));
    q->head = q->tail = NULL;
    return q;
}

void deleteQ(queue_t *q)
{
    atom_t *a = q->head;
    atom_t *n = q->head;

    while (a != NULL) {
        n = a->next;
        free(a);
        a = n;
    }
    free(q);
}


void enqueue(queue_t *q, bintree_t *t)
{
    atom_t *a = newAtom(t);
    a->next = NULL;

    if (q->tail == NULL) {
        q->head = q->tail = a;
    } else {
        q->tail->next = a;
        q->tail = a;
    }
}


bintree_t *dequeue(queue_t *q)
{
    bintree_t *tree;
    atom_t* a = q->head;

    if (a != NULL) {
        tree = a->tree;
        q->head = a->next;
        deleteAtom(a);
    } else {
        tree = NULL;
    }
    return tree;
}

queue.h

#ifndef __QUEUE_H__
#define __QUEUE_H__

#include "bintree.h"
/* structure inside queue like atoms of a list */
typedef struct atom_t{
    bintree_t *tree;
    struct atom_t *next;
} atom_t;

/* queue structure */
typedef struct {
    struct atom_t *head;
    struct atom_t *tail;
} queue_t;


atom_t *newAtom(bintree_t *t);
void deleteAtom(atom_t *a);
queue_t *newQ(void);
void deleteQ(queue_t *q);
void enqueue(queue_t *q, bintree_t *t);
bintree_t *dequeue(queue_t *q);

#endif  /* __QUEUE_H__ */