Traversée de l'arbre BFS modifié

Question

J'essayais d'implémenter un algorithme de traversée d'arbre similaire à BFS, mais avec une petite modification. Chaque fois que nous passons à la ligne suivante, nous devrions commencer par l'enfant le plus proche (enfant du dernier nœud de la rangée) au lieu du nœud le plus éloigné de la ligne suivante. Comment puis-je modifier le code BFS pour y parvenir?

Voici le code BFS d'origine:

public void bfs() 
    { 
     // BFS uses Queue data structure 

     Queue q = new LinkedList(); 

     q.add(rootNode); 
     visited[rootNode] = true; 

     printNode(rootNode); 

     while(!q.isEmpty()) 
     { 
     int n, child; 

     n = (q.peek()).intValue(); 

     child = getUnvisitedChildNode(n); // Returns -1 if no unvisited niode left  

     if (child != -1) 
     { // Found an unvisted node 

      visited[child] = true;  // Mark as visited 

      printNode(child); 

      q.add(child);  // Add to queue 
     } 
     else 
     { 
      q.remove();     // Process next node 
     } 
     } 
    } 

Voici comment ma modification souhaitée BFS devrait fonctionner:

Answer 1

ont 2 piles - un pour le courant niveau, un pour le niveau suivant.

Examinez le niveau actuel et passez au niveau suivant. Si le niveau actuel est vide, permutez les deux piles (de sorte que le niveau suivant devienne le niveau actuel et vice versa).

Il ressemblerait à quelque chose comme ceci:
(comme votre code mais avec q remplacé par current et next, et échanger les deux)

Stack current, next; 
// ... 
current.push(rootNode); 
while (!current.isEmpty() || !next.isEmpty()) 
{ 
    if (current.isEmpty()) 
    { 
     current = next; 
     next.clear(); 
    } 
    int n = current.peek(); 
    // ... 
    next.add(child); 
    // ... 
    current.pop(); 
} 

getUnvisitedChildNode aurait aussi besoin de changer (car les forces actuellement vraisemblablement une direction de gauche à droite sur un nœud individuel). Une option consisterait à passer une direction vers le bas pour décider si l'enfant suivant doit être renvoyé du côté gauche ou droit (que vous inversez lors de l'échange next et current).

---

Il est possible de le faire sans changer getUnvisitedChildNode, mais il faudrait un code « laid » - l'idée de base serait d'appeler getUnvisitedChildNode dans une boucle jusqu'à ce que vous avez tous les enfants de un nœud donné, jeter tous ces enfants dans un tableau (sans traitement, c'est-à-dire en les imprimant), puis en choisissant la direction dans laquelle les traiter en utilisant une variable de direction similaire à celle décrite ci-dessus.

Si vous avez déjà accès au tableau enfants, vous pouvez probablement faire une boucle directement à gauche ou à droite.