Witam, czy wie ktoś może gdzie mogę znaleźć jakieś algorytmy i informacje na ich temat odnośnie algorytmów sprawdzających czy jedno drzewo zawiera się w innym?
e zara? a czasem to nie jest jedynie kwestia implementacji struktury drzewa? jezeli wiercholek ma informacje o rodzicu to skoro jest niepusty wskaznik do rodzica to drzewo zawiera sie w innym... [???]
cepa napisał(a)
e zara? a czasem to nie jest jedynie kwestia implementacji struktury drzewa? jezeli wiercholek ma informacje o rodzicu to skoro jest niepusty wskaznik do rodzica to drzewo zawiera sie w innym... [???]
nie wiem co za brednie opowiadasz. Chyba nie zrozumiałeś problemu. Masz dwa drzewa (wzorzec i cel), ewentualnie drzewo (wzorzec) i las (cel). Węzły drzewa są oznaczone (posiadają pewne wartości), kolejność między "rodzeństwem" jest istotna. Pytanie brzmi czy z drzewa (wozrca) można usuwając pewne węzły otrzymać drzewo (las) - (cel).
Wystarczy zserializowac drzewa metodą WGŁĄB tj. zapisac jako odpowiednią liste wierzcholkow i wtedy problem sprowadza się do szukania podciągu w ciągu znaków. A to jest już proste i na ogół zaimplementowane w bibliotece standardowej języka (w C, C++, Pascalu i Javie jest).
Krolik napisał(a)
Wystarczy zserializowac drzewa metodą WGŁĄB tj. zapisac jako odpowiednią liste wierzcholkow i wtedy problem sprowadza się do szukania podciągu w ciągu znaków. A to jest już proste i na ogół zaimplementowane w bibliotece standardowej języka (w C, C++, Pascalu i Javie jest).
nie jest to takie proste, proponuje rozpisać sobie bardziej złożone drzewko. Wyszukiwanie wzorca w tekście da błędny wynik. Jeśli mi nie wierzysz możesz sam to przeanalizować (nawias nawiasowi nie równy, usunięcie węzła powoduje zmianę rodzica itd...). Bardziej chodzi mi o algorytmy Weimin Chena i Yangiun Chena. Czy ktoś o nich słyszał lub posiada ich implementacje?