Drzewa binarne

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ń).