1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| struct etat_parcours
{
noeud* pNoeudActuel;
int dernierFilsTraite; //-1 si on vient d'entrer, 0 si on revient du gauche, 1 si on revient du droit
etat_parcours(noeud* p, int f) : pNoeudActuel(p), dernierFilsTraite(f) {}
};
void parcours_arbre_nonsysteme(noeud* pRacine, callback_parcours_cpp cbPrefixe, callback_parcours_cpp cbInfixe, callback_parcours_cpp cbPostfixe)
{
stack<etat_parcours> pile;
pile.push(etat_parcours(pRacine, -1));
while(!pile.empty())
{
etat_parcours etat = pile.top();
pile.pop();
noeud* pNoeud = etat.pNoeudActuel;
//cout << "Taille pile: " << etat.size() << "Noeud depile:" << () << "Dernier fils traite:" << etat.dernierFilsTraite << endl;
switch(etat.dernierFilsTraite)
{
case -1: //On vient d'entrer
if(pNoeud==nullptr) { break; } //Noeud vide: rien du tout, on laisse remonter (le break quitte le switch)
if(cbPrefixe) { cbPrefixe(pNoeud); }
//Le prochain à parcourir est le fils gauche, puis il faudra revenir à ce noeud
pile.push(etat_parcours(pNoeud, 0));
pile.push(etat_parcours(pNoeud->pFilsGauche, -1));
break;
case 0: //On revient du fils gauche
if(cbInfixe) { cbInfixe(pNoeud); }
//Le prochain à parcourir est le fils droit, puis il faudra revenir à ce noeud
pile.push(etat_parcours(pNoeud, 1));
pile.push(etat_parcours(pNoeud->pFilsDroit, -1));
break;
case 1: //On revient du fils droit
if(cbPostfixe) { cbPostfixe(pNoeud); }
//On laisse remonter
break;
}
}
} |
Partager