Skopiowanie drzewa BST i iteracyjna wysokość drzewa AVL

Question

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.

Answer 1

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 

}

 

 

Comments

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ąć.