Traverser arbitrairement un grand arbre binaire en ordre

Question

Je suis bloqué pour trouver une solution. C#, .NET 4.0, VS2010

Je peux facilement écrire un récursif, mais je ne peux pas, pour la vie de moi, trouver quelque chose qui ne débordera pas la pile si l'arbre est arbitrairement grand.

C'est une question d'arbre binaire, et je suis en train d'écrire une méthode

public IEnumerable<T> Values() 

.

Voici le code complet dans le cas où vous êtes intéressé: http://pastebin.com/xr2f3y7g

De toute évidence, la version actuellement là-bas ne fonctionne pas. Je devrais probablement mentionner que je suis un débutant en C#, en transition de C++.

Answer 1

Voici une méthode pour afinde traversal, qui utilise la pile explicite. La pile est créée sur le tas, elle peut donc être beaucoup plus grande que la pile utilisée par le processeur.

public IEnumerable<T> Values() 
{ 
    Stack<Node> stack = new Stack<Node>(); 
    Node current = this.root; 
    while(current != null) 
    { 
     while(current.leftChild != null) 
     { 
      stack.Push(current); 
      current = current.leftChild; 
     } 
     yield return current.data; 
     while(current.rightChild == null && stack.Count > 0) 
     { 
      current = stack.Pop(); 
      yield return current.data; 
     } 
     current = current.rightChild; 
    } 

} 

Si vous ne pouvez pas utiliser une pile et vos noeuds arrive d'avoir des pointeurs de parents, vous pouvez essayer des solutions de this question

Answer 2

Si l'on suppose l'arbre est loin d'équilibre, sa profondeur maximale est log2 (n), de sorte que vous auriez besoin d'un grand arbre pour déborder la pile.

Vous pouvez transformer tout algorithme récursif dans un processus itératif, mais dans ce cas, il aura probablement besoin soit des pointeurs vers l'arrière ou une pile explicite, les deux qui ont l'air cher. Cela dit, la récursivité est généralement moins bonne dans .NET car aucune variable locale dans les instances appelantes d'une méthode ne peut être GC'ed jusqu'à ce que la pile soit déroulée après la condition de terminaison. Je ne sais pas si le JIT optimisera automatiquement la récursion de queue pour la rendre itérative, mais cela aiderait.