// Fonction de parcours infixé d'un arbre, utilisant la récursivité des données.
// Aucun test de débordement de pile n'est réalisé.
// Testée avec 32-bit Visual C++ 1.10.

#include <stdlib.h>
#include "tree.h"

#define MAX_PUSHED_NODES   100

extern void Visit(NODE *pNode);

void WalkTree(NODE *pNode)
{
   NODE *NodeStack[MAX_PUSHED_NODES];
   NODE **pNodeStack;

   // Vérifie que l'arbre n'est pas vide
   if (pNode != NULL)
   {
      NodeStack[0] = NULL;  // empile la valeur "pile vide" 
      pNodeStack = NodeStack + 1;

      for (;;)
      {
         // Si le nœud courant a un enfant gauche, empile
         // le nœud courant et descend vers l'enfant
         // gauche pour commencer à traverser le sous-arbre gauche.
         // Poursuivre jusqu'à ce que nous atteignons un nœud 
         // dépourvu d'enfant gauche; c'est-à-dire le prochain nœud 
         // à visiter dans la bonne séquence 
         while (pNode->pLeftChild != NULL)
         {
            *pNodeStack++ = pNode;
            pNode = pNode->pLeftChild;
         }

         // Nous sommes à un nœud qui n'a pas d'enfant gauche, 
         // visitons le nœud, puis le sous-arbre droit
         // s'il y en a, ou bien le dernier nœud
         // empilé; répétons l'opération pour chaque
         // nœud dépilé jusqu'à ce que nous en trouvions un
         // avec un sous-arbre ou qu'il n'y ait plus de nœuds 
         // empilés (notez que le sous-arbre gauche des nœuds
         // empilés sont déjà visités, ils sont donc équivalents
         // aux nœuds dépourvus d'enfant gauche
         for (;;)
         {
            Visit(pNode);

            // Si le nœud a un enfant droit, fait de l'enfant
            // le nœud courant et commence à traverser
            // ce sous-arbre; sinon, dépile l'arbre
            // en visitant les nœuds que nous avons 
            // rencontré, jusqu'à ce que nous trouvions un
            // nœud avec un sous-arbre droit ou qu'il n'y ait
            // plus les nœuds empilés et nous avons fini
            if (pNode->pRightChild != NULL)
            {
               // Le nœud courant a un enfant droit;
               // traverse le sous-arbre droit
               pNode = pNode->pRightChild;
               break;
            }

            // Dépile le prochain nœud depuis la pile afin que
            // nous puissions le visiter et vérifier s'il a un  
            // sous-arbre droit à traverser
            if ((pNode = *--pNodeStack) == NULL)
            {
               // La pile est vide et le nœud courant n'a pas
               // d'enfant droit; nous avons fini
               return;
            }
         }
      }
   }
}