Implementazione di una struttura di dati forestali in Java

Spero di avere una comprensione abbastanza chiara di quale sia il tuo problema. Se sono fuori pista fammelo sapere, altrimenti il seguente dovrebbe esserti di aiuto.

Giusto per essere chiari: prenderò in considerazione tutto quanto sotto nel contesto della genealogia.

Un albero è semplicemente una struttura ramificata. Nella genealogia, potresti considerare l'ultimo bambino come la radice e creare un albero che descriva la discendenza di questa persona. Sì, l'ultimo nato è la radice, non il più antico antenato conosciuto. Questo è abbastanza contro-intuitivo e probabilmente non è proprio quello che vuoi comunque.

Ora, una volta che hai problemi di famiglia più complicati, come un uomo che ha figli con due donne diverse, ti imbatterai in problemi con gli alberi. Se hai un albero separato per ogni bambino, allora il padre deve essere duplicato per poter essere presente in ognuno di questi alberi. Non pratico per non dire altro.

Come Neil ha menzionato nel suo commento sopra, è tempo di passare a un modello di grafico. La cosa più importante è chiarire una tipica confusione: la popolazione generale parla di qualcosa chiamato "Albero genealogico di famiglia", ma come scienziato informatico bisogna rendersi conto che un tale albero non è un albero secondo le definizioni date in informatica ( o biologia per quella materia). Abbiamo una definizione matematica molto chiara e concisa di una struttura dati dell'albero, e un "albero genealogico" non corrisponde a questo.

Perché è così? Semplicemente perché negli alberi delle scienze informatiche, i diversi rami non sono in grado di ricrescere insieme. Con le famiglie, questo è possibile. Abbastanza drasticamente, si potrebbe avere il caso di un padre con due bambini, che di nuovo generano una primavera. A parte implicazioni morali, questo si traduce in una vista diamantata, che non è rappresentabile in un albero.

Entra nel mondo dei grafici: un grafico è solo un termine generico di cose che sono collegate tra loro. Quindi, ogni albero di scienza dei computer è anche un grafico. Uno molto speciale e limitato naturalmente. In un grafico non c'è più una radice, ma ci sono nodi con proprietà simili (chiamate sorgenti). Inoltre non ci sono più foglie, ma ancora nodi con proprietà simili (chiamate lavandini).

In termini di genealogia puoi limitare il grafico dei risultati rendendolo un DAG, un grafico aciclico diretto. È diretto, poiché tra due nodi è possibile dichiararne uno come lato genitore, uno come lato figlio. Ad esempio, puoi sempre puntare da genitore a figlio (questa è una direzione, l'altra è fattibile). Se vuoi essere in grado di attraversare questa struttura in entrambe le direzioni, potresti anche considerare una variante non orientata.

Acicità significa semplicemente che non ci sono cerchi nella struttura dei dati. È abbastanza chiaro che questo si applica alla genealogia (a meno che non si voglia contare nel tempo viaggiare e l'opzione implicita di diventare il proprio padre o madre). In un DAG, puoi avere un numero qualsiasi di nodi e connessioni tra di loro. È tuttavia possibile aggiungere limitazioni arbitrarie. Ad esempio, se tutte le connessioni passano da genitore a figlio, allora ogni nodo figlio potrebbe essere limitato per avere un fan-in massimo di 2. Questo è solo un gergo teorico per affermare che una persona non può avere più di due genitori.

Quindi, suggerisco di dare un'occhiata da vicino ai grafici aciclici diretti e alla teoria del grafico sottostante in generale. Si noti inoltre che pagherà. Se vuoi fare lo sviluppo del software dovresti conoscere i grafici. Sono una delle strutture dati più generali e si applicano a quasi tutto. Non sono sempre la scelta migliore, ovviamente, ma saranno una delle cose più potenti nel tuo arsenale.

Questi post sono vecchi, ma qui è comunque il mio input.
Prima di tutto, penso che la soluzione sia molto più semplice dell'uso di grafici.
Vorrei implementare una classe, chiamiamola nodo, che ha il nome della persona e altri attributi che potresti desiderare di mantenere per ogni persona della famiglia. Quindi abbiamo bisogno di un altro attributo per aggiungerlo al nodo di classe, che è una matrice di (riferimenti) dello stesso tipo (Nodo). Questi sono i figli di un particolare genitore. All'inizio saranno tutti nulli, quindi puoi istanziare qualsiasi numero di bambini in base a ciò che hai e collegarli a questo particolare genitore. Ad esempio, la classe potrebbe iniziare in questo modo:

class Node
{
    private string name;  // person name
    private int data; // any data about the person i.e number of teeth :)
    private Node [] children;  // reference to array of children
    public void Node() // constructor
    {
        // here put code to instantiate the array, for example
    }
    // other methods, for example setters and getters
}

In questo modo il nonno più vecchio si troverà nel nodo radice. ogni nodo ha un numero di bambini basato sul caso reale, che sono riferimenti a oggetti dello stesso tipo, ecc ... Probabilmente dovrai scrivere alcuni metodi per attraversare la foresta, per poterlo stampare o cercare una persona in particolare, ecc. Puoi guardare i libri delle strutture dati in java o C # per saperne di più sull'implementazione di alberi collegati in generale. Spero che questo sia utile per chiunque abbia bisogno di implementare una foresta usando il paradigma orientato agli oggetti.