Makefile

random-tree: random-tree.c queue.c stack.c
	gcc random-tree.c queue.c stack.c

queue.c

#include <stdio.h>
#include <stdlib.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 (empty(q)) {
        q->head = q->tail = a;
    }else {
        q->tail->next = a;
        q->tail = a;
    }
}


bintree_t *dequeue(queue_t *q)
{
    bintree_t *tree;
    if (empty(q)) {
        return NULL;
    }else if (q->head==q->tail){ /* q has only one atom */
        tree = q->head->tree;
        q->head=q->tail=NULL;
    }else {
        tree = q->head->tree;
        q->head = q->head->next;
     }
    return tree;
}


int empty(queue_t *t)
{
    return t->head==NULL&&t->head==t->tail;
}

queue.h

#ifndef __QUEUE_H__
#define __QUEUE_H__

#include "random-tree.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);
int empty(queue_t *t);

#endif  /* __QUEUE_H__ */

random-tree.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "random-tree.h"
#include "queue.h"
#include "stack.h"




int main(void)
{
    srand(time(NULL));
    bintree_t *tree = newBT(10);
    displayBT(tree);
    insert(tree, 2);
    insert(tree, 3);
    insert(tree, 4);
    displayBT(tree);
    if (WFsearch(tree, 10)) {
        printf("found: 10\n");
    }else {
        printf("not found: 10\n");
    }
    if (WFsearch(tree, 3)) {
        printf("found: 3\n");
    }else {
        printf("not found: 3\n");
    }
    if (WFsearch(tree, 4)) {
        printf("found: 4\n");
    }else {
        printf("not found: 4\n");
    }
    if (WFsearch(tree, 7)) {
        printf("found: 7\n");
    }else {
        printf("not found: 7\n");
    }
    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;
}


void insert(bintree_t *t, int i)
{
    bintree_t *bt = t;
    int branch;                 /* 0: left, 1: right */
    while (1) {
        branch = rand()%2;
        if (branch==0) {        /* left */
            if (bt->left==NULL) {
                bt->left = newBT(i);
                break;
            }else {
                bt = bt->left;
            }
        }else {                /* right */
            if (bt->right==NULL) {
                bt->right = newBT(i);
                break;
            }else {
                bt = bt->right;
            }
        }
    }
}


 /* width first search using queue*/
int WFsearch(bintree_t *t, int i)
{
    queue_t *nodes = newQ();
    enqueue(nodes, t);
    while (!empty(nodes)) {
        bintree_t *top = dequeue(nodes);
        if (top==NULL) {
            continue;
        }else if (top->node == i) {
            return 1;
        }else {
            if (top->left!=NULL) {
                enqueue(nodes, top->left);
            }
            if (top->right!=NULL) {
                enqueue(nodes, top->right);
            }
        }
    }
    return 0;
}


 /* depth first search using stack*/
int DFsearch(bintree_t *t, int 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");
}

random-tree.h

#ifndef __RANDOM_TREE_H__
#define __RANDOM_TREE_H__

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


bintree_t *newBT(int i);
void       insert(bintree_t *t, int i);
int        WFsearch(bintree_t *t, int i); /* width first search */
int        DFsearch(bintree_t *t, int i); /* depth first search */
void       delete(bintree_t *t);
void       displayBT(bintree_t *t);

#endif  /* __RANDOM_TREE_H */

stack.c

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"


mystack_t *newStack(bintree_t *t)
{
    mystack_t *s = (mystack_t *)malloc(sizeof(mystack_t));
    s->len = 1;
    s->tree[s->len] = t;
    return s;
}


void push(mystack_t *s, bintree_t *t)
{
    if (s->len >= STACKSIZE) {
        printf("stack overflow.\n");
    }else {
        s->tree[(s->len)++] = t;
    }
}


bintree_t *pop(mystack_t *s)
{
    if ((int)s->len > 0) {
        return s->tree[--(s->len)];
    }else {                     /* the stack is empty */
        return 0;
    }
}


void deleteStack(mystack_t *s)
{
    free(s->tree);
}

stack.h

#ifndef __STACK_H__
#define __STACK_H__

#define STACKSIZE 256
#include "random-tree.h"


typedef struct {
    bintree_t *tree[STACKSIZE];
    size_t     len;
} mystack_t;




mystack_t *newStack(bintree_t *t);
void push(mystack_t *s, bintree_t *t);
bintree_t *pop(mystack_t *s);
void deleteStack(mystack_t *s);

#endif  /* __STACK_H__ */