È normale implementare alberi di ricerca binaria con una classe interna Node
public class BinarySearchTree<TKey, TVal>
{
class Node
{
public readonly TKey Key;
public readonly TVal Val;
public Node Left, Right;
public Node(TKey key, TVal val, Node left = null, Node right = null)
{
Key = key; Val = val; Left = left; Right = right;
}
}
private Node treeRoot;
}
Questo è bello perché nasconde il codice client dall'essere in grado di modificare direttamente l'albero.
Potrebbe essere il caso, tuttavia, che vogliamo esporre l'attraversamento dell'albero (ad esempio per la stampa). In questo senso, potrebbe avere senso tirare la Node
di classe su BinarySearchTree
e riprogettare Node
per utilizzare il visitatore modello di progettazione .
interface ITreeVisitor<TKey, TVal>
{
void Visit(Node<TKey, TVal> node);
}
class InOrderTreeVisitor<TKey, TVal> : ITreeVisitor<TKey, TVal>
{
public void Visit(Node<TKey, TVal> node)
{
if (node == null) return;
node.Left.Accept(this);
// do something to node
node.Right.Accept(this);
}
}
public class Node<TKey, TVal>
{
public Node<TKey, TVal> Left
{
get;
internal set;
}
public Node<TKey, TVal> Right
{
get;
internal set;
}
public readonly TKey Key;
public readonly TVal Val;
public Node(TKey key, TVal val, Node<TKey, TVal> left = null, Node<TKey, TVal> right = null)
{
Key = key; Val = val; Left = left; Right = right;
}
public void Accept(ITreeVisitor<TKey, TVal> v)
{
v.Visit(this);
}
}
public class BinarySearchTree<TKey, TVal>
{
public Node<TKey, TVal> Root
{
get;
private set;
}
}
Il problema con questo è che i visitatori devono essere generici. Questo non ha molto senso. Un visitatore non è un contenitore e non ha davvero bisogno di sapere nulla su chiavi o valori.
C'è un modo per rendere ITreeVisitor
non generico?