Czytam łamanie wywiadu kodowania i mam pytanie dotyczące rozwiązania następującego problemu: Masz dwa bardzo duże drzewa binarne: T1, z milionami węzłów, i T2, z setkami węzłów. Utwórz algorytm, aby zdecydować, czy T2 jest poddrzewem T1.Algorytmy do określenia, czy drzewo jest poddrzewem innego drzewa
Najprostszym rozwiązaniem, które sugeruje, jest utworzenie ciągu znaków reprezentującego nieregularne i poprzedzające zamówienia ruchy i sprawdzenie, czy przemieszczenie T2 w kolejności/kolejności w kolejności jest podciąganiu w kolejności T1 w kolejności.
Zastanawiam się, dlaczego potrzebujemy porównać obie traversale? I dlaczego dokładnie te dwie traversale, dlaczego nie na przykład w kolejności i po zamówieniu. A przede wszystkim wystarczy nie tylko jedno przejście? Powiedzieć tylko traversal w kolejności lub w przedsprzedaży?
Najpierw wyjaśnijmy, co masz na myśli przez "podtekst". Standardowe znaczenie teoretyczno-graficzne byłoby "pod-grafem utworzonym przez usunięcie zer lub więcej wierzchołków i krawędzi z drzewa, a które samo jest drzewem" - ale jest jeszcze inne powszechnie używane znaczenie, mianowicie "usuń krawędź", 2 połączone komponenty pozostać, z których oba są poddresami ". Ta pierwsza definicja obejmuje niektóre drzewa, których ta druga nie. –
Co ciekawe, algorytm, który podałeś, nie zadziała dla pewnych sensownych definicji "poddrzew": jako matematyk nazwałbym 2 <-1-> 3 poddrzewo 4 <-2<-1-> 3-> 5. Ale preorder pierwszego nie jest podciągiem drugiego. – Joel
Kiedy mówisz "Drzewo binarne", czy możemy założyć, że są one "drzewem binarnym wyszukiwania" (tzn. Rodzic jest mniejszy od któregokolwiek z jego dwójki dzieci)? Czy wartości w węzłach są unikalne w każdym drzewie, czy też nie? –