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.