Homework :)

I had plenty of other things to do today, so I iterated from that code :
http://encrypt3d.wordpress.com/2007/06/19/level-order-traversal/ , which I found pretty elegant.

Function of the code:

Breadth first tree traversal, display the level and show if the node is the first one of its level (starting from the left).

Missing:

As it was homework, I had to give the is_first property. What would be better would be to display the order of the node in the level.
Also, wondering about the best way to display a tree.
May'be starting by the bottom ?


Code:


typedef struct s_infos
{
  int is_first;
  int level;
  t_btree *node;
} t_infos;

t_infos    *create_new(t_infos *par, t_btree *n, int first)
{
  t_infos    *q;

  q = malloc(sizeof(t_infos));
  q->node = n;
  q->is_first = first ? 0 : 1;
  if (par)
    q->level = par->level + 1;
  else
    q->level = 0;
  return(q);
}

void    levelorder(t_btree *p,
        void (*applyf)(void *item,
                   int current_level,
                   int is_first_elem),
        int *size,
        int *qptr)
{
  t_infos    **queue;
  int    *tab;
  t_infos    *q;

  q = create_new(0, p, 0);
  tab = malloc(sizeof(int) * 100);
  queue = malloc(sizeof(t_infos *) * 100);
  while(q)
    {
      applyf(q->node->item, q->level, q->is_first);
      if(q->node->left)
    {
      queue[*size] = create_new(q, q->node->left, tab[q->level + 1]);
      *size += 1;
      tab[q->level + 1] = 1;
    }
      if(q->node->right)
    {
      queue[*size] = create_new(q, q->node->right, tab[q->level + 1]);
      *size += 1;
      tab[q->level + 1] = 1;
    }
      q = queue[*qptr];
      *qptr += 1;
    }
}

void    *btree_apply_by_level(t_btree *root,
                              void (*applyf)(void *item,
                                             int current_level,
                                             int is_first_elem))
{
  int    size;
  int    qptr;

  size = 0;
  qptr = 0;
  levelorder(root, applyf, &size, &qptr);
}

Usage:

Let root be the root of the tree, and applyf the adress of a function returning void and using as arguments the data of each processed node, its level and its is_first property (Crap how useless is that ..) Also, t_btree is a classical node structure containing the left child, the right child and the data.

Also, today I coded a function that allows you to insert a data in a red black tree.
I'll try to post that  when I have time, it's a little longer but I think it's worth it.