Porovnanie dvoch ADT typu strom

[thom]

Dobry den,
pre svoj projekt by som potreboval porovnat dva ADT - strom, ktore vsak maju roznu hlbku a aj velkost. Takze hladam nejaky algoritmus, ktory porovna dva stromy roznej hlbky a velkosti a urci ci su tieto dva stromy rovnake alebo rozne.
Projekt riesim v Jave a nasiel triedu
DefaultMutableTreeNode - http://docs.oracle.com/javase/1.4.2/docs/api/javax/swing/tree/DefaultMutableTreeNode.html
ktora udrziava data v strome a aj vypisuje strom do hlbky aj do sirky.

[Reklama]

[andy]

Bud nechapem alebo...ved normalne prechadzas oba po 1 kroku (samozrejme rovnakou strategiou..) a ked nemozes urobit ten isty krok alebo nemaju rovnake listy, tak su rozne. Ci? Uzly si ukladas do nejakeho zasobnika.

[aaaaaaaa]

Netusim, co presne chces robit, ale na porovnanie 2 stromov je obycajne najlepsie najst pointre na koren. Potom sa 2 stromy rovnaju, ked sa rovnaju korene a vsetky ich podstromy (rekurzia). Rekurziu je potom mozne odstranit, ale "z fleku" sa to pise horsie naraz bez rekurzie.
Naco to robit nejak zlozitejsie?

[Ivan]

A co ma byt vysledek? Prunik tech stromu? Doplnek? Anebo proste "=" / "!=".

[thom]

No vysledkom by malo "=" alebo "!=" to zname, ze "ano su rovnake" alebo "nie nie su rovnke".

Uvediem priklad - a[ b[] c[] ] = a[ b[] c[] ]
                    ale a[ b[] c[] ] != a[ b[] c[] d[] ]

Nezalezi mi na tom ake prvky obsahuju, potrebujem zistit ci struktura stromov je rovnaka.

[Reklama]

[hu]

Bud nechapem alebo...ved normalne prechadzas oba po 1 kroku (samozrejme rovnakou strategiou..) a ked nemozes urobit ten isty krok alebo nemaju rovnake listy, tak su rozne. Ci? Uzly si ukladas do nejakeho zasobnika.

No jiste.

[Zopper]

Prostě udělat nějakou formu průchodu stromem (in-order, pre-order, ...) a pokud se kterýkoliv uzel liší, tak se stromy nerovnají.