Alberi Binari powered by Custom Iterator

In questi gg di "lenta" preparazione in vista dell' esame 70-536 ho deciso di approfondire alcuni caratteristiche sia del framework che di C# 2.0 ...

Mi sono detto: perchè nn buttare giù alcune linee di codice che coprano Generics , Custom Iterator conditi con alcune reminescenze universitarie che vanno sotto il nome di alberi binari?!!!

Cominciano con la definizione della struttura dati presa in esame, utilizzando una definizione ricorsiva:

Un albero binario è composto da un nodo radice, da un sottolabero
destro e da un sottoalbero sinistro

Dalla definizione sopra esposta viene in modo naturale definire una classe del tipo:

public class BinaryTree where T:IComparable
{
    private T dataValue;
    private BinaryTree leftSubTree;       
    private BinaryTree rightSubTree;
}
 

Come possiamo vedere la definizione ricorsiva di albero binario ci guida anche nella definizione della classe apposita; da notare il vincolo posto sul tipo generico : con questo vincolo il tipo implementando l' interfaccia IComparable permette di utilizzare il metodo CompareTo() al fine di confrontare l'istanza sul quale viene invocato con un altra dello stesso tipo ( caratteristica desiderabile in fase di inserimento di nuovi nodi nell' albero); definito uno scheletro minimale per il nostro albero binario non ci resta che scrivere un bel custom iterator che permetta di visitarne tutti i nodi; gli iteratori offrono infatti un elevato grado di flessibilità al programmatore in quanto permettono di iterare sugli elementi seguendo la propria logica applicativa; supponiamo di voler visitare gli elementi del nostro albero seguendo la logica della visita InOrder (sottoalbero sinistro, radice, sottoalbero destro); una possibile implementazione basata su un iteratore custom è la seguente:

public IEnumerable<string> InOrder(BinaryTree<T> root)
        {
            Stack<BinaryTree<T>> stack = new Stack<BinaryTree<T>>();
            for (BinaryTree<T> current = root;
                current != null || stack.Count > 0;
                current = current.RightSubTree)
            {
                while (current != null)
                {
                    stack.Push(current);
                    current = current.LeftSubTree;
                }
                current = stack.Pop();
                yield return current.DataValue.ToString();
            }
        }

Come possiamo vedere l'implementazione di un iteratore in C# 2.0 segue deve rispettare due step fondamentali:

Scrittura di una funzione il cui tipo di ritorno sia IEnumerable oppure IEnumerable.
Utilizzo all' interno della funzione definita al punto 1 delle keywords yield return oppure yield break rispettivamente per restituire un valore al chiamante oppure per abbandonare l'iterazione.

Nel metodo sopra definito ho utilizzato anche la classe generica Stack<> in modo tale che mentre si attraversa l 'albero ogni nodo figlio appartenente al sottoalbero sinistro venga inserito in cima allo stack; l'istruzione yield return restituisce quindi prima gli elementi del sottoalbero sinistro poi la radice ed infine gli elementi del sottoalbero destro; nell' esempio sopra esposto ho adottato un approccio iterativo preferendolo ad uno ricorsivo per ragioni di performance;

E' possibile ad esempio grazie alla flessibilità degli iteratori custom cambiare la logica di visita degli elementi applicando magari una logica in cui prima viene visitata la radice, successivamente il sottoalbero destro ed infine quello sinistro; di seguito una possibile implementazione fornita da Nicolò Carandini:

public IEnumerable<string> PreOrder(BinaryTree root)
 
         {
             Stack> stack = new Stack>();
             for (BinaryTree current = root;
             current != null || stack.Count > 0;
             current = current.LeftSubTree)
             {
                 if (current == null)
                 {
                     current = stack.Pop();
                 }
                 yield return current.DataValue.ToString();
                 if (current.RightSubTree != null)
                 {
                     stack.Push(current.RightSubTree);
                 }
             }
           } 

A questo punto, dato che gli iteratori restituiscono un tipo IEnumerable, è possibile lato chiamante iterare sugli elementi dell' albero ricorrendo banalmente ad un foreach:

Per una implementazione più completa dell' albero binario fatemi sapere che magari fornirò ulteriori dettagli in futuri post .