Znalezienie średnicy drzewa - c ++, algorytm, drzewo

Napisałem kod do znalezienia średnicy drzewa binarnego. Ale nie jestem w stanie dowiedzieć się, co się dzieje. Dwie funkcje, które napisałem i ich definicja są następujące:

    int btree::diameteroftree(node* leaf)
{
if (leaf==NULL)
return 0;

int lheight = hieghtoftree(leaf->left);
int rheight = hieghtoftree(leaf->right);

int ldiameter = diameteroftree(leaf->left);
int rdiameter = diameteroftree(leaf->right);

return max(lheight + rheight + 1,max(ldiameter,rdiameter));
}


int btree::hieghtoftree(node* leaf)
{
int left=0,right=0;
if(leaf==NULL)
return -1;
else
{
left=hieghtoftree(leaf->left);
right=hieghtoftree(leaf->right);
if(left > right)
return left +1;
else
return right+1;
}
}

Nie jestem w stanie dowiedzieć się, gdzie idę źle. Czy ktoś może dać mi znać ...

Odpowiedzi:

1 dla odpowiedzi № 1

Chcesz zwrócić liczbę węzłów na najdłuższej ścieżce. Dlatego problem w twoim algorytmie jest taki:

return max(lheight + rheight + 1,max(ldiameter,rdiameter));

gdzie

rootDiameter = lheight + rheight + 1

to długość ścieżki od najgłębszego węzłalewego drzewa do najgłębszego węzła prawego drzewa. Jednak te obliczenia nie są poprawne. Pojedynczy węzeł zwraca wysokość 0, więc nie zostanie policzony. Masz dwie możliwości:

1. Zmiana hieghtoftree aby zwrócić liczbę węzłów na najgłębszej ścieżce, a nie liczbę „przeskoków”
2. Rozwiąż ten problem w swoim podsumowaniu

.

return max(lheight + rheight + 3,max(ldiameter,rdiameter));

---

0 dla odpowiedzi nr 2

W ukierunkowanym, zrootowanym drzewie zawsze istnieje co najwyżej jedna ścieżka między dowolną parą węzłów, a najdłuższa ścieżka do dowolnego węzła zawsze zaczyna się w korzeniu. Wynika z tego, że średnica to po prostu wysokość całego drzewa height(root), który można obliczyć za pomocą rekursji

height(leaf) = 0
height(node) = max(height(node.left), height(node.right)) + 1

EDYTOWAĆ: strona, do której link znajduje się w komentarzu, opisuje średnicę pliku bezkierunkowy drzewo. Potrzebujesz innej reprezentacji drzewa, np. macierz sąsiedztwa.

---

0 dla odpowiedzi № 3

Rozważmy drzewo z 3 węzłami z korzeniem R i 2 liśćmi L1, L2. Wtedy heightoftree (L1) == heightoftree (L2) == -1. Diameteroftree (R) to (-1) + (- 1) +1 = -1?!?

Proponuję zwrócić -1; -> return 0; i return max (lheight + rheight + 1, max (ldiameter, rdiameter)); -> return max (lheight + rheight + 2, max (ldiameter, rdiameter));

Wynikiem byłaby liczba krawędzi na ścieżce. Jeśli policzysz liczbę węzłów, dodaj jeden lub odejmij jeden od wyniku końcowego zgodnie z potrzebami.

---