znajdowanie dwóch najbardziej odległych elementów w drzewie binarnym

Question

Szukam algorytmu, który mógłby znaleźć dwa najbardziej odległe elementy w drzewie binarnym, nie szukając żadnego specjalnego języka, tylko dla algorytmu.

Dzięki.

Answer 1

Nazywa się średnicę drzewa.

int diameter(Tree * t) // post: return diameter of t 
{ 
    if (t == 0) return 0; 
    int lheight = height(tree->left); 
    int rheight = height(tree->right); 
    int ldiameter = diameter(tree->left); 
    int rdiameter = diameter(tree->right); 
    return max(lheight + rheight + 1, max(ldiameter,rdiameter)); 
} 

alt text http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.jpg

copied code and images from here.

Answer 2

To, czego szukasz, można nazwać graph diameter. Aby go zdobyć, musisz obliczyć ścieżkę od dowolnego wierzchołka do dowolnego innego, a następnie przejść przez wszystkie z nich i znaleźć największy.
Można to osiągnąć za pomocą Dijkstra's algorithm lub po prostu distance matrix (co można osiągnąć, zasilając adjacency matrix), chociaż zajmie to więcej czasu niż algorytm Dijkstry.

Answer 3

Ponieważ jest to drzewo, istnieje tylko jedna ścieżka między dowolną parą wierzchołków. Dzięki temu łatwiej nam znaleźć średnicę wykresu.

Najprostszym sposobem na zrobienie tego jest wykonanie dwóch prostych przemieszczeń drzewa. Po pierwsze, weź dowolny dowolny węzeł jako root i oblicz odległość od niego za pomocą prostego systemu plików DFS/BFS. Teraz weź węzeł znajdujący się najdalej od katalogu głównego (ten pierwszy węzeł najbardziej odległej pary), a czyniąc go nowym katalogiem głównym, przeprowadź kolejne przejście odległości obliczeniowych drzewa. Najdalszym węzłem jest drugi węzeł pary.

Dowód na to, że to działa, jest pozostawiony jako ćwiczenie.

Istnieje również inny sposób obliczania najbardziej odległej pary przez obliczanie i porównywanie najdalszych par dla każdego poddrzewa drzewa, zaczynając od dowolnego węzła jako root (wspomnianego już w innej odpowiedzi).