MAssimo sottoalbero comune

[Eruc]

Salve a tutti ho un problema, ho bisogno di ricavare il massimo sottoalbero comune tra due alberi non ordinati non binari.
In pratica ho ricavato due alberi DOM a partire da 2 pagine HTML.
Come estraggo il MAX sottoalbero comune?????
Grazie a tutti

[Pastore12]

dati due alberi A e B

Per ogni foglia Afi di A
  Per ogni foglia Bfj di B
    Se Afi e Bfj sono uguali => sottoalbero di altezza 1
    Se Il padre Api di Afi è uguale al padre Bpj di Bfj e tutti i "fratelli" di Afi sono uguali ai fratelli di Bjj
      sottoalbero con radice Api comune ai due alberi
    Ripeti per il padre di Api e di Bpj ...
    Fermati quando raggiungi la radice di A e B oppure trovi due nodi diversi.
    Memorizza da qualche parte il nodo e la sua altezza se maggiore dell'altezza trovata per una foglia precedente.

Evidentemente questa roba è solo una bozza.
Forse non devi considerare l'altezza, ma il numero di foglie.
Se una foglia fa parte di un sottoalbero già analizzato, non ha senso analizzarla una seconda volta: si ritroverà comunque un sottoalbero già ottenuto

Forse si può usare un approccio alternativo: quando un trovi due sottoalberi uguali nei due alberi, sostituisci i sottoalberi con una foglia (che avrà un campo apposito in cui indicare il numero di nodi o l'altezza del sottoalbero che sostituisce).
I sottoalberi uguali che devi cercare sono sempre formati da una foglia, il suo padre e tutti i suoi fratelli.
Passi in rassegna tutte le foglie in questo modo. Quando hai finito fai una nuova passata e vai avanti fino a quando non hai un passaggio in cui non individui nessun sottoalbero comune.
A Questo punto analizzando le foglie (che rappesentano veramente foglie, oppure sottoalberi) è possibile individuare il sottoalbero più grosso.

mm.. beh.. ora valuta se qualche idea ti sembra sensata..

[Eruc]

Grazie per la risposta.
Hai del codice java di esempio da farmi vedere?
Il tuo approccio è del tipo bottom-up. Se invece volessi partire dalla radice degli alberi e navigare fino alle foglie?

[Pastore12]

Grazie per la risposta.

Prego. Ritengo che pensare all'ideazione di algoritmi non banali e non troppo complicati.. sia una delle cose più divertenti dell'informatica.

Hai del codice java di esempio da farmi vedere?

No. Quel che ho scritto l'ho pensato al momento. non mi dedico agli alberi da.. quasi 7 anni..
Scusa una domanda, ma questo è il tuo primo tentativo di scrivere codice java?

Se invece volessi partire dalla radice degli alberi e navigare fino alle foglie?

Bah.. Se calcoli la dimensione di un sottoalbero sei costretto a calcolare anche la dimensione dei sottoalberi del sottoalbero.. per forza di cose devi arrivare alle foglie, in questo modo devi star attento a non ripetere i calcoli gia' fatti... certo, la dimensione di un albero generato da una pagina web non è immensa, per cui potresti anche pensare di cavartela con un algoritmo stupido che confronta tutti i sottoalaberi di A con i tutti i sottoalberi di B.
In questo caso la cosa è banale perchè ad ogni sottoalbero corrisponde un nodo.