Drzewa BST

Ogólnie pomysł drzew jest bardzo prosty: Mając jeden element główny (zwany węzłęm głównym), tworzymy jego "dzieci", które są połączone z węzłem głównym z lewej i prawej strony (tzw. dziec - z lewej dziecko o mniejszej wartości a z prawej o większej). Każde dziecko może posiadać kolejną dwójkę dzieci (lewe i prawe). Węzeł główny (jak i dzieci) to nic innego jak rekordy w pamięci, skłądające się takich pól jak: dane różnych typów, oraz zmiennych typu takiego jak drzewko (lewy i prawy potomek). Jest to prosty przykład, jak korzystać z takich struktur danych jak drzewa BST. Poniżej zamieszczam kod:

uses
  SysUtils;
type
  TDana = integer; // deklaracja jakiejś danej
  Drzewo = ^TDrzewo; // typ wskazujący na drzewko bo przecież musimy pamiętac jego potomków...
  TDrzewo = record   // drzewko
    etykieta: TDana;  // to jest nasza dana, może być ich oczywiście więcej 
    lewy, prawy: Drzewo;  // potomkowie
  end;

var
  i, a, n: integer;
  dana: TDana;
  drzewko: Drzewo;

// procedura wstawiania
procedure Wstaw(var W : Drzewo; Co : TDana);
begin
  if W = nil then
  begin
    new(W);
    if W = nil then
      exit;
    W^.lewy:=nil;
    W^.prawy:=nil;
    W^.etykieta:=Co;
  end
  else
  if W^.etykieta > Co then
    Wstaw(W^.lewy,Co)
  else
  if W^.etykieta < Co then
    Wstaw(W^.prawy,Co);
end;

// procedura usuwania
procedure Usun(var W : Drzewo; Co : TDana);
var
  T,X,Y,Z: Drzewo; {X?rodzic, Y-usuwany, Z-dziecko}
begin
  X:=nil;
  Y:=W;
  while Y<>nil do
  begin
  if Y^.etykieta = Co then
    break
  else
  begin
    X:=Y;
    if Y^.etykieta > Co then
      Y:=Y^.lewy
    else
      Y:=Y^.prawy;
  end;
  end;
  if Y<>nil then
    if (Y^.lewy= nil) or (Y^.prawy=nil) then
    begin
      if (Y^.lewy = nil) and (Y^.prawy = nil) then
        Z:=nil
      else
        if (Y^.lewy =nil) then
          Z:=Y^.prawy
        else
          Z:=Y^.lewy;
      if X=nil then
        W:=Z
      else
        if Y=X^.lewy then
          X^.lewy:=Z
        else
          X^.prawy:=Z;
      dispose(Y);
    end
    else
    begin
      Z:=Y^.prawy;
      if Z^.lewy=nil then
        Y^.prawy:= Z^.prawy
      else
      begin
        repeat
          T:=Z;
          Z:=Z^.lewy;
        until
          Z^.lewy=NIL;
        T^.lewy:=Z^.prawy;
      end;
      Y^.etykieta:= Z^.etykieta;
      dispose(Z);
    end;
end;

{ 
  procedura wyświetlania. tutaj użyłem metody Inorder (lewe dziecko, dana, prawe dziecko).
  ale są jeszcze dwie: Postorder (lewe dziecko, prawe dziecko, dana) i 
  Preorder (dana, lewe dziecko i prawe dziecko).
}
procedure drukuj(W : Drzewo);
begin
  if W <> nil then
  begin
    drukuj(W^.Lewy);
    Writeln(W^.Etykieta);
    drukuj(W^.Prawy);
  end;
end;

// procedura szukania - zwykłe przejście przed drzewo
procedure szukaj(W : Drzewo; dana: tdana);
begin
  if W <> nil then
  begin
    szukaj(W^.Lewy, dana);
    if W^.etykieta = dana then
    begin
      Writeln('znaleziona: ', W^.etykieta);
      Exit;
    end;
    szukaj(W^.Prawy, dana);
  end;
end;

// program główny - wywołanie tego co napisałem wyżej...
begin
  Writeln('Podaj liczbe wartosci');
  Readln(a);
  Writeln('Podaj ', a, ' liczb');
  for i:= 1 to a do
  begin
    Readln(n);
    Wstaw(drzewko, n);
  end;
  writeln;
  Writeln('zawartosc drzewa:');
  drukuj(drzewko);
  Writeln;
  Writeln('podaj szukana wartosc:');
  Readln(a);
  szukaj(Drzewko, a);
  Writeln;
  Writeln('podaj wartosc do usuniecia');
  readln(a);
  usun(drzewko, a);
  writeln;
  drukuj(Drzewko);
  Readln;
end.

A oto implementacja drzewa BST w języku C. Algorytm wstawiania jest rekurencyjny. Przykład pochodzi z witryny: http://programmuj.blogspot.com/2011/08/implementacja-drzewa-bstbinarnego.html

    #include  <stdlib.h>
    #include  <stdio.h>
    #include  <string.h>
     
     
    struct node{
    int key;
    struct node *lewy;
    struct node *prawy;
    }*korzen=NULL;
     
     
     
    void push(struct node *&korzen,int x)
    {
         if(korzen==NULL)
         {
           korzen=(struct node*)malloc(sizeof(struct node));
           korzen->lewy=NULL;
           korzen->prawy=NULL;
           korzen->key=x;
           return;
           }else
           {
                if(x<korzen->key)
                push(korzen->lewy,x);
                else push(korzen->prawy,x);
                }
    }
     
     
     
    void showrek(struct node *korzen) //lewe poddrzewo, prawe,rekurencyjnie
    {
         
    if(korzen)
    {
           
         
              showrek(korzen->lewy);
              printf("%d ",korzen->key);
              showrek(korzen->prawy);
    }        
    }
     
     
    int main()
    {
        int n,i,x;
        printf("Ile elementow dodad do drzewa??\n");
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
          scanf("%d",&x);
          push(korzen,x);
         }
       showrek(korzen);
    system("PAUSE");
     
    }

No i to byłoby na tyle. Sądze, że nikt nie powinien mieć problemu ze zrozumieniem tego. Wspomnę jeszcze (dla tych co nie wiedzą), że mamy jeszcze inne drzewka - drzewa AVL (znane jako drzewa "wyważone"), drzewa 2-3-4 i drzewa czerwono - czarne - ale o tym może w następnym artykule.