• 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
69 wizyt
pytanie zadane 20 marca 2017 w Algorytmy przez J0ker Obywatel (1,290 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ź

+1 głos
odpowiedź 14 kwietnia 2017 przez d0n Mądrala (6,460 p.)
wybrane 2 maja 2017 przez J0ker
 
Najlepsza

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 

}

 

 

1
komentarz 2 maja 2017 przez J0ker Obywatel (1,290 p.)
Serdecznie dziękuję za odpowiedź. Niestety nie udało mi się zrobić tamtej pracy domowej, Doceniam jednak to, że znalazł Pan czas na odpowiedź.

 

Pozdrawiam.

Temat administracja może zamknąć.

Podobne pytania

0 głosów
0 odpowiedzi 116 wizyt
pytanie zadane 23 maja 2017 w C i C++ przez kakola3 Początkujący (250 p.)
0 głosów
1 odpowiedź 44 wizyt
0 głosów
1 odpowiedź 136 wizyt
pytanie zadane 19 grudnia 2016 w Java przez Patryk Rafał Bywalec (2,410 p.)
Porady nie od parady
Pytania na temat serwisu SPOJ należy zadawać z odpowiednią kategorią dotyczącą tej strony.
Ciekawy innych porad? Odwiedź tę stronę!

45,699 zapytań

86,090 odpowiedzi

171,933 komentarzy

22,166 pasjonatów

Przeglądających: 214
Pasjonatów: 10 Gości: 204

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...