Alberi binari, Generics e Costruttori, Custom Iterators

Leggendo il post di Luca del Tongo su Alberi Binari powered by Custom Iterator ho fatto un tuffo nel passato e incuriosito dall'uso dei generics e degli iteratori custom ho provato a scrivere una applicazione console giusto per testare il codice.

La prima cosa che ho imparato implementando la classe BinaryTree<T> è che con le classi che fanno uso di generics occorre usare Default(T) per passare un parametro "nullo" ad un costruttore.

Se ad esempio, per una classe BinaryTree così definita:

public class BinaryTree { private object rootData; private BinaryTree leftSubTree; private BinaryTree rightSubTree; }

possiamo definire i costruttori:

public BinaryTree() : this(null) { } public BinaryTree(object rootData) : this(rootData, null, null) { } public BinaryTree(object datavalue, BinaryTree leftSubTree, BinaryTree rightSubTree) { this.rootData = rootData; this.leftSubTree = leftSubTree; this.rightSubTree = rightSubTree; }

nel caso della classe proposta da Luca del Tongo:

public class BinaryTree<T> where T : IComparable { private T datavalue; private BinaryTree<T> leftSubTree; private BinaryTree<T> rightSubTree;

dobbiamo definire i costruttori in questo modo:

public BinaryTree() : this(default(T)){} public BinaryTree(T datavalue) : this(datavalue, null, null){} public BinaryTree(T datavalue, BinaryTree<T> leftSubTree, BinaryTree<T> rightSubTree) { this.datavalue = datavalue; this.leftSubTree = leftSubTree; this.rightSubTree = rightSubTree; }

Come è facile notare, l'unica vera differenza sta nell'usare default(T) al posto di null per il datavalue, che è di tipo generico e che quindi in fase di utilizzazione potrebbe prevedere un valore piuttosto che un riferimento null.

Come seconda cosa, visto che l'algoritmo di iterazione per la visita in PreOrder non sembra essere corretto, ho buttato giù una mia implementazione:

public IEnumerable<string> PreOrder(BinaryTree<T> root)
{
    Stack<BinaryTree<T>> stack = new Stack<BinaryTree<T>>();
    for (BinaryTree<T> 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);
        }
    }
}

Come al solito, vista l'ora, concludo con... Buonanotte!

posted @ mercoledì 2 maggio 2007 05:04

Print

Comments on this entry:

# Alberi Binari powered by Custom Iterator

Left by WetBlog at 03/05/2007 07:14
Gravatar
Comments have been closed on this topic.
«ottobre»
domlunmarmergiovensab
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456