Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
ProblemNależy przedstawić w oknie konsoli strukturę drzewa binarnego. |
W rozdziale zaprojektujemy prosty sposób prezentacji drzew binarnych. Przedstawiamy go na poniższym rysunku
→ |
┌─L ┌─G ┌─C │ │ ┌─K │ └─F A │ ┌─E │ │ └─J └─B │ ┌─I └─D └─H |
|
Każdy węzeł drzewa znajduje się w osobnym wierszu okna konsoli. Jeśli przyjrzymy się ich kolejności, to zauważymy, że są one w porządku odwrotnym do przejścia in-order. Taką kolejność przejścia węzłów uzyskamy przez odwrócenie w algorytmie in-order kolejności odwiedzania poddrzew:
zwykłe in-order | odwrotne in-order | |
K01:
Jeśli v = nil, to zakończ K02: inorder (v→left) K03: Odwiedź węzeł wskazany przez v K04: inorder (v→right) K05: Zakończ |
K01:
Jeśli v = nil, to zakończ K02: inorder (v→right) K03: Odwiedź węzeł wskazany przez v K04: inorder (v→left) K05: Zakończ |
Położenie węzła w wierszu zależy od jego poziomu. Korzeń znajduje się w kolumnie 0. Węzły pierwszego poziomu znajdują się w kolumnie 2, węzły drugiego poziomu w kolumnie 4, następne w kolumnie 6, itd.
Od kolumny węzła do kolumny poprzedzającej syna jest zawsze wypisywany tekst:
┌─ dla prawego syna └─ dla lewego syna |
Dodatkowo musimy umieszczać znaki │ ponad i poniżej węzła, jeśli posiada on synów. Problem ten rozwiążemy łatwo zapamiętując w osobnej zmiennej sp tekst, który należy wyświetlić w wierszach pośrednich. Poniżej przedstawiamy odpowiedni algorytm wraz z opisem poszczególnych operacji.
sp | : | tekst do wyświetlenia w wierszu pośrednim |
sn | : | tekst do wyświetlenia przed węzłem |
v | : | wskazanie bieżącego węzła drzewa |
s | : | tekst do wyświetlenia w wierszach pośrednich dla synów |
K01: | Jeśli v = nil, to zakończ |
otrzymaliśmy puste wskazanie, nic nie robimy |
K02: | s ← sp | w s umieszczamy tekst dla wierszy pośrednich |
K03: | Jeśli sn = "┌─", to s [| s | - 2] ← " " |
dla prawego syna usuwamy z sn ostatni znak | |
K04: | printBT (s + "│ ", "┌─", (v→right)) | wywołujemy algorytm rekurencyjnie dla prawego syna |
K05: | s ← sp [0 : | s | - 2] | w s umieszczamy sn bez ostatnich dwóch znaków, które zastąpi tekst przed węzłem |
K06: | Pisz s, sn, (v→data) | wypisujemy wiersz węzła |
K07: | s ← sp | powtarzamy operacje dla lewego syna |
K08: | Jeśli sn = "└─", to s [| s | - 2] ← " " |
dla lewego syna usuwamy z sn ostatni znak | |
K09: | printBT (s + "│ ", "└─", (v→left)) | wywołujemy algorytm rekurencyjnie dla lewego syna |
K10: | Zakończ |
Pierwsze wywołanie algorytmu powinno być z pustymi tekstami sp i sn oraz z v wskazującym korzeń drzewa.
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program odczytuje ze standardowego wejścia definicję drzewa. Definicja składa się z liczby n określającej ilość węzłów oraz n trójek, które dla kolejnych węzłów oznaczają odpowiednio: zawartość węzła, numery lewego i prawego syna. Brak syna oznaczany jest liczbą 0. Na podstawie tej definicji program tworzy odpowiednie drzewo binarne, wyświetla je, a na koniec usuwa z pamięci. |
Przykładowe dane (przekopiuj do schowka i
wklej do okna konsoli):
|
Pascal// Prezentacja drzewa binarnego // Data: 03.02.2013 // (C)2013 mgr Jerzy Wałaszek //------------------------------ program show_BT; // Typ węzłów drzewa type PBTNode = ^BTNode; // wskazanie węzła BTNode = record // rekord węzła left : PBTNode; // lewy syn right : PBTNode; // prawy syn data : integer; // dane węzła end; // Zmienne globalne var n : integer; // liczba węzłów root : PBTNode; // wskazanie korzenia drzewa cr, cl, cp : string; // łańcuchy do znaków ramek // Procedura inicjuje dane, odczytuje definicję drzewa // ze standardowego wejścia i tworzy jego strukturę w // pamięci. Na wyjściu w zmiennej root zostaje umieszczony // adres korzenia drzewa //-------------------------------------------------------- procedure readBT; var vp : array of PBTNode; // tablica wskaźników i, d, l, r : integer; begin read (n); // odczytujemy liczbę węzłów drzewa binarnego SetLength (vp, n); // tworzymy tablicę dynamiczną wskaźników for i := 0 to n - 1 do new (vp [i]); // tworzymy dynamicznie węzeł for i := 0 to n - 1 do begin read (d, l, r); // odczytujemy dane węzła i numery synów vp [i]^.data := d; // wprowadzamy do węzła dane if l > 0 then vp [i]^.left := vp [l] // ustawiamy lewego syna else vp [i]^.left := nil; // jeśli istnieje if r > 0 then vp [i]^.right := vp [r] // ustawiamy prawego syna else vp [i]^.right := nil; // jeśli istnieje end; root := vp [0]; // zapamiętujemy korzeń drzewa SetLength (vp, 0); // usuwamy tablicę wskaźników end; // Procedura DFS:postorder usuwająca drzewo //----------------------------------------- procedure DFSRelease (v : PBTNode); begin if v <> nil then begin DFSRelease (v^.left); // usuwamy lewe poddrzewo DFSRelease (v^.right); // usuwamy prawe poddrzewo dispose (v); // usuwamy sam węzeł end; end; // Procedura wypisuje drzewo //-------------------------- procedure printBT (sp, sn : string; v : PBTNode); var s : string; begin if v <> nil then begin s := sp; if sn = cr then s [length (s) - 1] := ' '; printBT (s + cp, cr, v^.right); s := Copy (sp, 1, length (sp) - 2); writeln(s, sn, v^.data); s := sp; if sn = cl then s [length (s) - 1] := ' '; printBT (s + cp, cl, v^.left); end; end; // ********************** // *** PROGRAM GŁÓWNY *** // ********************** begin // ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają // wstawiać znaki konsoli do tworzenia ramek. // cr = +-- // | // cl = | // +-- // cp = | // | cr := #218#196; cl := #192#196; cp := #179#32; readBT; // odczytujemy drzewo printBT ('', '', root); // wyświetlamy drzewo DFSRelease (root); // usuwamy drzewo z pamięci end. |
// Prezentacja drzewa binarnego // Data: 03.02.2013 // (C)2013 mgr Jerzy Wałaszek //------------------------------ #include <iostream> #include <string> using namespace std; // Typ węzłów drzewa struct BTNode { BTNode * left; // lewy syn BTNode * right; // prawy syn int data; // dane węzła }; // Zmienne globalne int n; // liczba węzłów BTNode * root; // wskazanie korzenia drzewa string cr, cl, cp; // łańcuchy do ramek // Procedura inicjuje dane, odczytuje definicję drzewa // ze standardowego wejścia i tworzy jego strukturę w // pamięci. Na wyjściu w zmiennej root zostaje umieszczony // adres korzenia drzewa //-------------------------------------------------------- void readBT() { BTNode ** vp; // tablica wskaźników int i, d, l, r; cin >> n; // odczytujemy liczbę węzłów drzewa binarnego vp = new BTNode * [n]; // tworzymy tablicę dynamiczną wskaźników for(i = 0; i < n; i++) vp [i] = new BTNode; // tworzymy dynamicznie węzeł for(i = 0; i < n; i++) { cin >> d >> l >> r; // odczytujemy dane węzła i numery synów vp [i] ->data = d; // wprowadzamy do węzła dane if(l) vp [i] ->left = vp [l]; // ustawiamy lewego syna else vp [i] ->left = NULL; // jeśli istnieje if(r) vp [i] ->right = vp [r]; // ustawiamy prawego syna else vp [i] ->right = NULL; // jeśli istnieje } root = vp [0]; // zapamiętujemy korzeń drzewa delete [] vp; // usuwamy tablicę wskaźników } // Procedura DFS:postorder usuwająca drzewo //----------------------------------------- void DFSRelease (BTNode * v) { if(v) { DFSRelease (v->left); // usuwamy lewe poddrzewo DFSRelease (v->right); // usuwamy prawe poddrzewo delete v; // usuwamy sam węzeł } } // Procedura wypisuje drzewo //-------------------------- void printBT (string sp, string sn, BTNode * v) { string s; if(v) { s = sp; if(sn == cr) s [s.length() - 2] = ' '; printBT (s + cp, cr, v->right); s = s.substr (0, sp.length() - 2); cout << s << sn << v->data << endl; s = sp; if(sn == cl) s [s.length() - 2] = ' '; printBT (s + cp, cl, v->left); } } // ********************** // *** PROGRAM GŁÓWNY *** // ********************** int main() { // ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają // wstawiać znaki konsoli do tworzenia ramek. // cr = +-- // | // cl = | // +-- // cp = | // | cr = cl = cp = " "; cr [0] = 218; cr [1] = 196; cl [0] = 192; cl [1] = 196; cp [0] = 179; readBT(); // odczytujemy drzewo printBT ("", "", root); // wyświetlamy drzewo DFSRelease (root); // usuwamy drzewo z pamięci return 0; } |
Basic' Prezentacja drzewa binarnego ' Data: 03.02.2013 ' (C)2013 mgr Jerzy Wałaszek '------------------------------ ' Typ węzłów drzewa Type BTNode left As BTNode Ptr right As BTNode Ptr data As Integer End Type ' Zmienne globalne Dim Shared As Integer n ' liczba węzłów Dim Shared As BTNode Ptr root ' wskazanie korzenia drzewa Dim Shared As String * 2 cr, cl, cp ' łańcuchy do ramek ' Procedura inicjuje dane, odczytuje definicję drzewa ' ze standardowego wejścia i tworzy jego strukturę w ' pamięci. Na wyjściu w zmiennej root zostaje umieszczony ' adres korzenia drzewa '-------------------------------------------------------- Sub readBT() Dim As BTNode Ptr Ptr vp ' tablica wskaźników Dim As Integer i, d, l, r Open Cons For Input As #1 Input #1, n ' odczytujemy liczbę węzłów drzewa binarnego vp = new BTNode Ptr [n] ' tworzymy tablicę dynamiczną wskaźników For i = 0 To n - 1 vp [i] = new BTNode ' tworzymy dynamicznie węzeł Next For i = 0 To n - 1 Input #1, d, l, r ' odczytujemy trójkę liczb vp [i] ->data = d ' wprowadzamy do węzła dane ' ustawiamy lewego syna, jeśli istnieje If l > 0 Then vp [i] ->left = vp [l] Else vp [i] ->Left = 0 End If ' ustawiamy prawego syna, jeśli istnieje If r > 0 Then vp [i] ->right = vp [r] Else vp [i] ->Right = 0 End If Next Close #1 root = vp [0] ' zapamiętujemy korzeń drzewa delete [] vp ' usuwamy tablicę wskaźników End Sub ' Procedura DFS:postorder usuwająca drzewo '----------------------------------------- Sub DFSRelease (v As BTNode Ptr) If v Then DFSRelease (v->left) ' usuwamy lewe poddrzewo DFSRelease (v->right) ' usuwamy prawe poddrzewo Delete v ' usuwamy sam węzeł End If End Sub ' Procedura wypisuje drzewo '-------------------------- Sub printBT (sp As String, sn As String, v As BTNode Ptr) Dim As String s If v Then s = sp If sn = cr Then Mid (s, Len (s) - 1, 1) = " " printBT (s + cp, cr, v->right) s = Mid (s, 1, Len (sp) - 2) Print Using "&&&";s;sn;v->Data s = sp If sn = cl Then Mid (s, Len (s) - 1, 1) = " " printBT (s + cp, cl, v->Left) End If End Sub ' ********************** ' *** PROGRAM GŁÓWNY *** ' ********************** ' ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają ' wstawiać znaki konsoli do tworzenia ramek. ' cr = +-- ' | ' cl = | ' +-- ' cp = | ' | cr = Chr (218) + Chr (196) cl = Chr (192) + Chr (196) cp = Chr (179) + " " readBT() ' odczytujemy drzewo printBT ("", "", root) ' wyświetlamy drzewo DFSRelease (root) ' usuwamy drzewo z pamięci End |
Wynik: |
┌─2 ┌─1 ┌─7 │ │ ┌─0 │ └─9 5 │ ┌─8 │ │ └─3 └─2 │ ┌─5 └─3 └─6 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.