Drzewo
- Korzeń : pierwszy element
- Rodzic (przodek) :
- Potomkowie (synowie) :
- Liść : element drzewa, który nie ma potomków.
- Węzeł : element drzewa
- Poddrzewo : fragment drzewa
- Drzewo binarne : drzewo, który każdy węzeł ma co najwyżej dwóch synów(potomków)
- BST – Binary Search Tree : Binarne drzewo poszukiwań
- Drzewo wyważone : Drzewo, w którym dla każdego węzła wysokość jego lewego i prawego poddrzewa różnią się co najwyżej o 1
- Drzewo dokładnie wyważone : Jeśli dla każdego węzła liczba węzłów w prawym i lewym poddrzewie jest taka sama.
Definicja typów:
type
wsk_elem = ^elem;
elem = rekord
liczba : integer;
lewy, prawy : wsk_elem;
end;
Wstawianie do drzewa
procedure wstaw(var korzen:wsk_elem; liczba:integer);
begin
if korzen = nil then
new(korzen);
korzen^.liczba:=liczba;
korzen^.lewy:=nil;
korzen^.prawy:=nil
end;
end;
else
if liczba < korzen^.liczba then
wstaw(korzen^.lewy, liczba)
else
wstaw(korzen^.prawo, liczba);
end;
Drukowanie drzewa
<przodek> : <lewy potomek>, <prawy potomek>
procedure drukuj(korzen : wsk_elem);
begin
if korzen <> nil then
begin
write(korzen^.liczba, ‘:’ );
if korzen^.lewy <> nil then
write(korzen^.lewy^.liczba);
write(‘ , ‘);
if korzen^.prawy <> nil then
write(korzen^.prawy^.liczba);
writeln;
drukuj(korzen^.lewy);
drukuj(korzen^.prawy);
end;
end;
Podobne strony
Podobne Strony • Stos • Lista Dwukierunkowa • Lista Cykliczna Jednokierunkowa • Lista Jednokierunkowa
wersja strony: 3, ostatnia edycja: 16 Jul 2009 11:25