[Kos-dev] Parcours d'arbre non récursif

[Thomas Petazzoni]

Salut,

Ce soir un copain (Christophe Bliard) dinait à la maison, il s'est lancé
sur le problème. Il a pondu ça :

const tree_node_t *_splay_visit(const tree_node_t *node, 
				visitor_t visitor_in_order, 
				visitor_t visitor_reverse_order, 
				void *client_data)
{
  tree_node_t *cur;
  enum { COME_LEFT, COME_RIGHT, GO_DOWN, END } state;

  if (node == NULL)
    return node;
  cur = node;
  state = GO_DOWN;
  do {
    if ((cur->left != NULL) && (state == GO_DOWN)) {
      state = GO_DOWN;
      cur = cur->left;
    }
    else if ((cur->right != NULL) && (state == GO_DOWN || state ==
COME_LEFT)) {      if (state == COME_LEFT || (cur->left == NULL && state
== GO_DOWN)) {	printf("node key : %d\n", cur->key);
      }
      state = GO_DOWN;
      cur = cur->right;
    }
    else {
      if (state == GO_DOWN || (state == COME_LEFT && cur->right ==
NULL)) {	printf ("node key : %d\n", cur->key);
      }
      if (cur->up == NULL) {
	printf("plus de parent\n");
	state = END;
      }
      else if (cur->key < cur->up->key) {
	state = COME_LEFT;
	cur = cur->up;
      }
      else {
	state = COME_RIGHT;
	cur = cur->up;
      }
    } 
  } while (state != END);
  return node;
}

Et j'ai testé jusqu'à 100, ça affiche bien les nombres dans l'ordre ...

Quelqu'un pour vérifier ?

Thomas
-- 
PETAZZONI Thomas - thomas.petazzoni at enix.org - UIN : 34937744
http://www.enix.org/~thomas/
KOS: http://kos.enix.org/ - Lolut: http://lolut.utbm.info
Fingerprint : 0BE1 4CF3 CEA4 AC9D CC6E  1624 F653 CB30 98D3 F7A7