Esposizione di nodi in una generica implementazione dell'albero di ricerca binario a modello di visitatore

4

È 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?

    
posta rookie 26.10.2015 - 22:40
fonte

2 risposte

3

Nel tuo caso il visitatore non ha bisogno di preoccuparsi del tipo generico perché tratta direttamente con il nodo e non richiama alcuna logica specifica del tipo (ad esempio ToString() dovrebbe essere sufficiente).

Hai due opzioni:

  1. Attacca con un tipo generico e usa la chiave e i tipi di valore appropriati ogni volta che crei il tuo oggetto visitatore.

  2. Crea una seconda interfaccia per i visitatori e un'implementazione non generica. Si erediterà quindi l'uno o l'altro a seconda che il visitatore specifico tratti i dati del nodo o solo il nodo.

Il compromesso è più prolisso durante la creazione di oggetti o più dettagliato con interfacce ridondanti.

    
risposta data 26.10.2015 - 22:59
fonte
1

Sostituisci il metodo ToString() nella tua classe Node, quindi usa un visitatore non generico per raccogliere i risultati della chiamata di ToString() su ciascun nodo.

    
risposta data 26.10.2015 - 23:47
fonte

Leggi altre domande sui tag