Forum Coders' city Strona Główna Coders' city
Nasza pasja to programowanie!
 

 PomocPomoc   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy  RejestracjaRejestracja 
Archiwum starego forum + teoria    RSS & Panel/SideBar
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Potrzebuję szybkiej odpowiedzi na moje pytanie... Zasady

Przekształcenie drzewa binarnego w listę dwukierunkową



 
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Mariusz M
Gość





PostWysłany: Sro Maj 23, 2018 9:35 am  OP    Temat postu: Przekształcenie drzewa binarnego w listę dwukierunkową Odpowiedz z cytatem Pisownia

Przeglądając sieć znalazłem w sieci procedure do przekształcenia drzewa binarnego w listę dwukierunkową
Była mi ona potrzebna do sortowania
Mając tę funkcję i funkcję wstawiającą do drzewa BST
łatwo napisać procedurę sortującą

Kod:

void BinaryTree2DoubleLinkedList(node *root, node **head)
{
    // Base case
    if (root == NULL) return;

    // Initialize previously visited node as NULL. This is
    // static so that the same value is accessible in all recursive
    // calls
    static node* prev = NULL;

    // Recursively convert left subtree
    BinaryTree2DoubleLinkedList(root->left, head);

    // Now convert this node
    if (prev == NULL)
        *head = root;
    else
    {
        root->left = prev;
        prev->right = root;
    }
    prev = root;

    // Finally convert right subtree
    BinaryTree2DoubleLinkedList(root->right, head);
}



Czy użycie zmiennej statycznej aby na pewno jest dobrym pomysłem
Jak poprawilibyście kod tej procedury
Powrót do góry
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Sro Maj 23, 2018 9:54 am      Temat postu: Odpowiedz z cytatem Pisownia

Hej,
lepiej chyba przekształcać bezpośrednio, looknij może tutaj... DSW. Oprócz drzew BST ciekawe są jeszcze samobalansujące się drzewa typu splay, pzdr...

_________________
miasto nauki praktycznej
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
Mariusz M
Gość





PostWysłany: Sro Maj 23, 2018 11:13 am  OP(?)    Temat postu: Odpowiedz z cytatem Pisownia

Algorytm na pierwszy rzut oka wygląda ciekawie
Czy można go użyć do eliminacji przypadku pesymistycznego dla sortowania drzewem BST

Konwersja do listy dwukierunkowej też może być przydatna
np do otoczki wypukłej Diks i Rytter proponują użycie cyklicznej listy dwukierunkowej dla
otoczki wypukłej
Otoczka wypukła to tylko przykład gdzie sortowanie przyśpiesza algorytm
Powrót do góry
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Sro Maj 23, 2018 12:08 pm      Temat postu: Odpowiedz z cytatem Pisownia

sorki, ale nie znam się zbyt dobrze nad tym... :) powodzenia, może ktoś inny pomoże... :)
_________________
miasto nauki praktycznej
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
Mariusz M
Gość





PostWysłany: Sro Maj 23, 2018 8:33 pm      Temat postu: Odpowiedz z cytatem Pisownia

Patrzyłeś na poprzedni temat ?

Jeśli chodzi o sortowanie przez scalanie to masz pomysł jak ustawić wskaźniki na poprzedniki
Gdybyśmy pamiętali także wskaźnik na ogon to procedurę rozdzielającą można by nieco przyśpieszyć
szukając węzła po którym należy rozdzielić listę z dwóch stron
Powrót do góry
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Czw Maj 24, 2018 6:29 am      Temat postu: Odpowiedz z cytatem Pisownia

sorki, ale to są tematy typu standard, poszukaj kodów w sieci, i porównaj, powodzenia... :)
_________________
miasto nauki praktycznej
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
Mariusz M
Gość





PostWysłany: Czw Maj 24, 2018 8:42 am      Temat postu: Odpowiedz z cytatem Pisownia

sorki ale myślę że we wpisie z Sro Maj 23, 2018 12:08 pm
napisałeś prawdę tylko po co odpisujesz ?
Powrót do góry
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Czw Maj 24, 2018 8:59 am      Temat postu: Odpowiedz z cytatem Pisownia

to forum nie było nigdy od rozwiązywania problemów szkolnych, że tak to ujmę... no chyba, że się coś zmieniło... a odpisałem dlatego, żeby Cię jakoś nakierować... w sieci jest mnóstwo tego typu przykładów, bo to raczej standard, więc szkoda mi po prostu czasu, mam co robić, sorki, jeżeli źle odebrałeś, powodzenia... :) PS. swoją drogą proponuję zmienić podejście z Polskiego na ciut bardziej przyjazne, bo to mnie na przykład zniechęca do zabierania głosu w tym wątku... :)
_________________
miasto nauki praktycznej
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
Wyświetl posty z ostatnich:   
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania Wszystkie czasy w strefie CET (Europa)

Strona 1 z 1

 
Skocz do:  
Możesz pisać nowe tematy
Możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
Możesz dodawać załączniki na tym forum
Możesz pobierać pliki z tego forum




Debug: strone wygenerowano w 0.31503 sekund, zapytan = 11
contact

| Darmowe programy i porady Jelcyna | Tansze zakupy w Helionie | MS Office Blog |