• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Skopiowanie drzewa BST i iteracyjna wysokość drzewa AVL

0 głosów
38 wizyt
pytanie zadane 20 marca w Algorytmy przez J0ker Początkujący (300 p.)
Dzień dobry, mam 2 problemy:

1. Skopiowanie drzewa BST.- argument - wskaźnik do korzenia.

2. Na ćwiczeniach było rekurencyjne obliczenie wysokości drzewa AVL, a ja muszę zrobić iteracyjne.

Umieściłęm temat w Dziale Algorytmy, ponieważ mam problem z samą metodą jak to zrobić (konkretnie mam to napisać w języku C). Domyślam, się, że skopiowanie będzie rekurencyjne (kopiuj wierzchołek, kopiuj->lewe,kopiuj>prawe) ale nie ogarniam. W obu procedurach i tego jestem pewny zacząłbym od sprawdzenia czy drzewo jest puste i jeśli tak zwróciłbym 0 (return 0;) Zupełnie natomiast nie mam pomysłu na iteracyjne AVL.

Ogólnie to rozumiem dobrze funkcje z wykładu i ćwiczeń gdy są juz gotowe podane na tacy, ale sam je wymyślać to bym nie wymyśił nic z nich...

Prosiłbym raczej o porady, wskazówki niż gotowe rozwiązania. Z góry dziękuję za każdą pomoc.

1 odpowiedź

0 głosów
odpowiedź 14 kwietnia przez d0n Obywatel (1,560 p.)

Jeśli chodzi o drzewo BST, to jeśli implementacja samego drzewa jest taka, że przez NULL oznaczamy brak danego syna, a każdy węzel posiada składowe wskaźniki node* lewy i node* prawy to z grubsza wyglądało by to tak

void dfs ( node* v, node* v_w_nowym_drzewie )
{
 skopiuj wszystkie wartosci z v do v_w_nowym_drzewie oprócz adresów synów
 
 jesli lewy syn v != NULL
    przypisz v_w_nowym_drzewie pamiec na lewego syna
    wywolaj dfs( adres lewego syna v, adres lewego syna v_w_nowym_drzewie)
 potem to samo dla prawego syna 

}

 

 

Podobne pytania

0 głosów
1 odpowiedź 63 wizyt
pytanie zadane 19 grudnia 2016 w Java przez Patryk Rafał Bywalec (2,040 p.)
+1 głos
1 odpowiedź 123 wizyt
pytanie zadane 16 czerwca 2015 w Algorytmy przez Jaskrowicz Obywatel (1,200 p.)
0 głosów
1 odpowiedź 62 wizyt
pytanie zadane 21 stycznia w Algorytmy przez WWOTEX Mądrala (6,180 p.)
...