Algorytmy

Drzewa binarne

  • 2006-04-16 22:59
  • 1 komentarz
  • 3371 odsłon
  • Oceń ten tekst jako pierwszy
Drzewa binarne są to drzewa, które posiada węzeł główny (drzewo), który posiada co najwyżej  dwójkę potomków ? lewy i prawy (poddrzewa). Każdy z potomków może posiadać również najwyżej dwójkę dzieci (lewe dziecko i prawe dziecko).
Definicja takiego drzewa w języku Pascal (w tym artykule będę posługiwać się jedynie tym językiem) może wyglądać tak:

Drzewo = ^wezel;
Wezel = record
        Dana: int; { może być jakikolwiek typ wbudowany czy też zdefiniowany przez użytkownika}
        Lewy, prawy: Drzewo;
end;


Przejście przez drzewo binarne.
Rozróżniamy 3 takie przejścia przez ów drzewa: Inorder, Postorder, Preorder.
 - Inorder: najpierw należy odwiedzić lewe poddrzewo, następnie etykietę (dana) a potem prawe. Przykład wykonania tego rekurencyjnie:

procedure Inorder( W : Drzewo);
begin
  if W <> nil then 
  begin
    Inorder(W^.Lewy);
    WriteLn(W^.Etykieta);
    Inorder(W^.Prawy);
  end; 
end;


 - Postorder: najpierw należy przejść do lewego poddrzewa, potem prawego a na końcu odwiedzić etykietę (dana). Przykład wykonania tego rekurencyjnie:

procedure Postorder( W : Drzewo);
begin
  if W <> nil then 
  begin
    Postorder(W^.Lewy);
    Postorder(W^.Prawy);
    WriteLn(W^.Etykieta);
  end;
end;


 - Preorder: najpierw trzeba odwiedzić etykietę (dana), następnie lewe poddrzewo a na końcu prawe poddrzewo. Przykład wykonania tego rekurencyjnie:
procedure Preorder( W : Drzewo);
begin
  if W <> nil then 
  begin
    Writeln(W^.Etykieta);
    Preorder(W^.Lewy);
    Preorder(W^.Prawy);
  end;
end;



Aby przybliżyć temat drzew i operacji, jakie możemy na nich wykonywać, zachęcam do przeczytania artykułu o drzewach BST (Drzewa Binarnych Poszukiwań).

1 komentarz

dRum 2007-08-14 11:29

mi sie podoba, ale moja wykladowczyni i tak by sie przyczepila ;] pozdrawiam