Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: thom 26. 01. 2012, 15:05:42
-
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.
-
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.
-
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?
-
A co ma byt vysledek? Prunik tech stromu? Doplnek? Anebo proste "=" / "!=".
-
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.
-
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.
-
Prostě udělat nějakou formu průchodu stromem (in-order, pre-order, ...) a pokud se kterýkoliv uzel liší, tak se stromy nerovnají. :)