Umówię się do napisania algorytmu rekurencyjnego, aby wyodrębnić maksimum (root) z max sterty. Sterta jest skonstruowana jako drzewo. Wiem, że powinienem zamienić ostatni węzeł z korzeniem i pchnięto rekurencyjnie. Ale nie ma pseudokodu w Internecie ani przepełnienie stosu, aby poradzić sobie z drzewami. Algorytmy ekstraktu, które widziałem, są oparte na tablicach.

Powiedzmy więc, że znajduję właściwy najbardziej liść.

Czy jest jakieś rozwiązanie, które możesz sugerować?


void find_last(heap_node* root,int level,int* last_level,bool isRight,heap_node** res){

if(root ==  NULL)
    return;

if(isRight && !root->left && !root->right && level > *last_level){
    *res = root;
    *last_level = level;
    return;

}
find_last(root->right,level+1,last_level,true,res);
find_last(root->left,level+1,last_level,false,res);
}

I zrobiłem taką funkcję

            heap_node* last = NULL;
            int last_level = -1;
            find_last(root,0,&last_level,false,&last);

To jest kodeks znalezienia najgłębszego właściwego węzła. I nie działa: D

-1
TuMama 21 marzec 2020, 12:50

1 odpowiedź

Najlepsza odpowiedź

Efektywne znalezienie ostatniego węzła w sterty, który jest wdrażany jako drzewo wymaga, aby utrzymać liczbę węzłów. To znaczy, wiesz, ile elementów jest w sterty.

Jeśli wiesz, ile elementów jest w sterty, a następnie otrzymasz reprezentację binarną numeru i użyć tego do śledzenia przez drzewo do ostatniego węzła. Dam ci przykład. Masz tę stertę:

         1
     /       \
    2         3
  /   \     /   \
 4     5   6

W sterty znajduje się 6 sztuk. Reprezentacja binarna to 110.

Teraz, przechodząc od prawa do lewej w reprezentacji binarnej. Usuwasz pierwszą "1" i jesteś w węźle korzeniowym. Regułą polega na tym, że pójdziesz w prawo, jeśli cyfra jest "1", a jeśli cyfra jest "0". W węźle root masz 10. Więc idziesz w prawo i usuwaj tę cyfrę, pozostawiając cię z 0. Jesteś na węźle oznaczonym "3". Pozostała cyfra jest 0, więc idziesz w lewo. To stawia cię na ostatnim węźle w sterty.

Algorytm do przesiewania przez stertę jest taki sam niezależnie od tego, czy sterta jest reprezentowana jako tablica, czy jako drzewo. Oczywiście rzeczywiste kroki, które biorą do swapu. Podczas wymiany węzłów należy uważać, aby prawidłowo ustawić wskaźniki dziecka. Jednym miejsce ludzie często zapominają, że zamieniając węzeł korzenia ostatniego węzła.

Moja sugestia jest tym, że kodujesz to, a następnie pojedynczy krok w debuggerze, aby upewnić się, że masz odpowiednie zadania wskaźnik.

0
Jim Mischel 23 marzec 2020, 19:11