print binary tree in level order proof-of-concept

level_order.c

/*
 * XXX: This code might not work as-is. I'm cutting and pasting the relevant
 * parts from a working implementation in my hash tree project that may or may
 * not get pushed to github later. That's why I'm putting it here for reference.
 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/queue.h>

struct rbt_node_s {
    unsigned long key;
    int color;
    char *strkey;
    int vlen;
    struct rbt_node_s *p;
    struct rbt_node_s *left;
    struct rbt_node_s *right;
};

struct queue_entry_node_s {
    struct rbt_node_s *n;
    TAILQ_ENTRY(queue_entry_node_s) q_entries;
};

static struct rbt_node_s *NIL;

struct level_entry_s {
    int level;
    TAILQ_ENTRY(level_entry_s) l_entries;
};

/*
 * In the version of bfs I'm going to use for writing to disk I'll probably use
 * a mmap'd file for storing the node queue rather than malloc'ing each queue entry.
 */
static void print_level_order(struct rbt_node_s *z) {
    int level, prev_level;
    struct level_entry_s *l_entry, *c_entry;

    struct rbt_node_s *u;
    struct queue_entry_node_s *q_entry, *u_entry;

    TAILQ_HEAD(queue_head_s, queue_entry_node_s) Q;
    TAILQ_INIT(&Q);

    q_entry = malloc(sizeof(struct queue_entry_node_s));
    q_entry->n = z;
    TAILQ_INSERT_TAIL(&Q, q_entry, q_entries);

    prev_level = 1;

    TAILQ_HEAD(level_head_s, level_entry_s) L;
    TAILQ_INIT(&L);
    l_entry = malloc(sizeof(struct level_entry_s));
    l_entry->level = prev_level;
    TAILQ_INSERT_TAIL(&L, l_entry, l_entries);


    while (!TAILQ_EMPTY(&Q)) {
        u_entry = TAILQ_FIRST(&Q);
        TAILQ_REMOVE(&Q, u_entry, q_entries);
        u = u_entry->n;

        c_entry = TAILQ_FIRST(&L);
        TAILQ_REMOVE(&L, c_entry, l_entries);
        level = c_entry->level;

        if (level > prev_level) {
            printf("\n");
            prev_level = level;
        }

        printf("%s ", u->strkey);

        if (u->left != NIL) {
            q_entry = NULL;
            q_entry = malloc(sizeof(struct queue_entry_node_s));
            q_entry->n = u->left;
            TAILQ_INSERT_TAIL(&Q, q_entry, q_entries);

            l_entry = NULL;
            l_entry = malloc(sizeof(struct level_entry_s));
            l_entry->level = level+1;
            TAILQ_INSERT_TAIL(&L, l_entry, l_entries);
        }

        if (u->right != NIL) {
            q_entry = NULL;
            q_entry = malloc(sizeof(struct queue_entry_node_s));
            q_entry->n = u->right;
            TAILQ_INSERT_TAIL(&Q, q_entry, q_entries);

            l_entry = NULL;
            l_entry = malloc(sizeof(struct level_entry_s));
            l_entry->level = level+1;
            TAILQ_INSERT_TAIL(&L, l_entry, l_entries);
        }
    }

    printf("\n");

    while (!TAILQ_EMPTY(&Q)) {
        u_entry = TAILQ_FIRST(&Q);
        TAILQ_REMOVE(&Q, u_entry, q_entries);
        free(u_entry);
    }

    while (!TAILQ_EMPTY(&L)) {
        c_entry = TAILQ_FIRST(&L);
        TAILQ_REMOVE(&L, c_entry, l_entries);
        free(c_entry);
    }
}