Pravljenje in-order i ispis binarnog stabla

1. Definicija binarnog stabla

type cvor = ^slog;
    slog = record
        vrednost: Integer;
        levo: cvor;
        desno: cvor;
    end;

• cvor je pokazivač na zapis (rekord) tipa slog.
• slog sadrži:
  • vrednost: broj koji se čuva u čvoru.
  • levo: pokazivač na levo dete čvora.
  • desno: pokazivač na desno dete čvora.

2. Funkcija KreirajCvor

function KreirajCvor(Vrednost: integer): cvor;
var NoviCvor: cvor;
begin
New(NoviCvor);
NoviCvor^.Vrednost := Vrednost;
NoviCvor^.Levo := nil;
NoviCvor^.Desno := nil;
KreirajCvor := NoviCvor;
end;

• Kreira novi čvor u stablu sa zadatom vrednošću.
• Inicijalizuje pokazivače levo i desno na nil, jer novokreirani čvor nema decu.

3. Procedura DodajUCvor

procedure DodajUCvor(var Trenutni: cvor; Vrednost: integer);
begin
if Trenutni = nil then
    Trenutni := KreirajCvor(Vrednost)
else if Vrednost < Trenutni^.Vrednost then
    DodajUCvor(Trenutni^.levo, Vrednost)
else
    DodajUCvor(Trenutni^.desno, Vrednost);
end;

• Dodaje novu vrednost u stablo:
  1. Ako je trenutni čvor nil, kreira se novi čvor pomoću KreirajCvor.
  2. Ako je vrednost manja od vrednosti u trenutnom čvoru, dodaje se u levo podstablo (levo).
  3. Ako je vrednost veća ili jednaka, dodaje se u desno podstablo (desno).
• Rekurzivno se poziva dok ne pronađe mesto za novu vrednost.

4. Procedura IspisiStablo

procedure IspisiStablo(element: cvor);
begin
if element <> nil then
    begin
    IspisiStablo(element^.levo);
    Write(element^.Vrednost, ' ');
    IspisiStablo(element^.desno);
    end;
end;

• Ispisuje stablo koristeći in-order redosled:
  1. Prvo obilazi levo podstablo.
  2. Ispisuje trenutnu vrednost.
  3. Na kraju obilazi desno podstablo.
• Ovaj redosled rezultira ispisom elemenata u rastućem poretku.

5. Glavni program

var Koren: cvor;
    n, i, x :integer;
begin
Koren := nil;
readln(n);
for i := 1 to n do
    begin
    readln(x);
    DodajUCvor(Koren, x);
    end;
write('Ispis stabla: ');
writeln;
IspisiStablo(Koren);
end.

• Koren je početni čvor stabla, inicijalizovan na nil.
• n: broj elemenata koji će biti uneti u stablo.
• Petlja za unos elemenata:
  1. Korisnik unosi n brojeva.
  2. Svaki broj se dodaje u stablo pomoću DodajUCvor.
• Nakon unosa svih brojeva, ispisuje se sadržaj stabla korišćenjem IspisiStablo.