Drzewo binarne

Drzewo binarne – drzewo, w którym stopień każdego wierzchołka jest nie większy od 3.
Ukorzenione drzewo binarne to drzewo binarne, w którym wyróżniono jeden z wierzchołków (zwany korzeniem) stopnia najwyżej 2.
W informatyce drzewo binarne to jeden z rodzajów drzewa (struktury danych), w którym liczba synów każdego wierzchołka wynosi nie więcej niż dwa. Wyróżnia się wtedy lewego syna i prawego syna danego wierzchołka.
Drzewo binarne, w którym liczba synów każdego wierzchołka wynosi albo zero albo dwa, nazywane jest drzewem regularnym. Przykładem takich drzew są drzewa Huffmana (omawiane wcześniej na lekcji o kompresji danych).

Zadanie 1

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.

 

Author: ZSE

Admnistrator serwisu. Nauczyciel przedmiotów informatycznych

Share This Post On

Submit a Comment

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *