28.Prednaska

Z Pascal
Prejsť na: navigácia, hľadanie
28. Prednáška

úlohy | cvičenie


Dátová štruktúra strom

V dátovej štruktúre strom sa podobne ako pri spájaných zoznamoch nejako udržuje množina vrcholov. Pri spájaných zoznamoch bol dôležitý prvý vrchol, za ktorým boli napojené všetky ďalšie (každý vrchol mal jedného nasledovníka). Posledný vrchol v tejto štruktúre nemal žiadneho nasledovníka. V štruktúre strom je tiež najdôležitejším prvý vrchol (hovoríme mu koreň), pričom všetky ďalšie sú nejako napojené buď na tento koreň alebo na niektorý z už skôr napojených. Na koreň sú napojené tzv. podstromy. Tieto vznikajú tak, že všetky vrcholy okrem koreňa rozdelíme do disjunktných podmnožín. Každá z týchto podmnožín je tiež stromom (podstrom) a teda má svoj koreň (tento jediný je napojený na koreň celého stromu) a svoje podstromy.

Zo štruktúrou strom ste sa už mohli stretnúť, napr. pri

  • zobrazovaní rodokmeňa, napr. šľachtických alebo kráľovských rodov
  • zobrazení hierarchickej štruktúry priečinkov nejakého disku
  • hierarchickom systéme rastlín a živočíchov
  • organizačná štruktúra fakulty

Napríklad, na tomto obrázku môžete vidieť časť rodokmeňa anglickej kráľovskej rodiny:

rodokmeň

V tejto štruktúre je koreňom vrchol Elizabeth II. Z tohto vrcholu vychádzajú štyri podstromy (ich koreňmi sú Charles, Anna, Andrew a Edward). V týchto podstromoch sú okrem vrcholov, ktoré sú koreňmi aj ďalšie vrcholy, ktoré z tohto koreňa vychádzajú. Zrejme, keby sme vytvárali rodokmeň, v ktorom by sa objavil aj kráľovský predok kráľovnej Elizabeth II kráľ George VI, tak tento strom by bol iba podstromom tohto väčšieho stromu (kráľ George VI mal dvoch potomkov: dcéry Elizabeth II a Margaret a teda z tohto vrcholu vychádzajú dva podstromy).

Vrcholy v strome sú spojené tzv. hranami - sú to orientované spojnice (najčastejšie ich kreslíme šípkami) v smere od koreňa k podstromom. V takomto strome táto hrana - teda šípka určuje vzťah: od vrchola k jeho nasledovníkovi. Tu sa používa terminológia ako v rodokmeňoch: kde predchodcom vrchola je tzv. rodič (niekedy hovoríme otec) a nasledovníkovi hovoríme potomok (alebo syn). Vrcholom, ktoré majú spoločného rodiča, hovoríme súrodenci (používa sa aj brat) . V našom rodokmeni sú niektoré vrcholy ženského rodu, napriek tomu sa im hovorí otec - syn - brat.

V stromovej štruktúre jedine koreň nemá predka, všetky ostatné vrcholy majú práve jedného predka. Ak nejaký vrchol nemá žiadneho potomka, hovoríme mu list. Zrejme každý neprázdny strom má práve jeden koreň a aspoň jeden list. Vrcholu, ktorý má aspoň jedného potomka, hovoríme vnútorný vrchol. Na obrázku rodokmeňa sú listami napr. William, Harry, Savannah, Isla, Zara, ... Vnutornými vrcholmi sú napr. Elizabeth II, Charles, Anna, Peter, ... Súrodencami (bratia) sú napr. Charles, Anna, Andrew a Edward. Zrejme aj William a Harry sú tiež súrodenci.

Počtu potomkov vrchola hovoríme stupeň vrcholu, napr. vrchol Elizabeth II má stupeň 4 a Harry má stupeň 0. Vidíme, že v strome sú vrcholy rôzmych stupňov. Stupeň stromu potom znamená najvyšší stupeň vrchola v strome. V tomto príklade je stupeň celého stromu 4.

Ďalším dôležitým pojmom je cesta v strome. Je to postupnosť vrcholov spojených hranami (postupujeme len v smere šípok). Dĺžka cesty je počet hrán na tejto ceste, t.j. je to počet vrcholov mínus 1. Vrcholy potom môžeme rozlišovať podľa toho, ako ďaleko sú od koreňa (aká dlhá je cesta od koreňa k vrcholu) - hovoríme tomu úroveň vrcholu. Zrejme koreň má úroveň 0 (Elizabeth II). Potomkovia koreňa sú v 1. úrovni (Charles, Anna, Andrew a Edward). Potomkovia vrcholov v 1. úrovni sú v 2. úrovni (William, Harry, Peter, Zara, Beatrice, Eugenie, Louise, James). Potomkovia vrcholov v 2. úrovni sú v 3. úrovni (Savannah, Isla). Keďže vrcholy v 3. úrovni už ďalej nemajú potomkov, hovoríme, že maximálna úroveň v strome je 3. Takejto maximálnej úrovni sa hovorí Hĺbka stromu (niekedy aj výška stromu). Ak má strom len koreň, potom hĺbka stromu je 0. Pre prázdny strom (neobsahuje žiaden vrchol) zvykneme hĺbku stromu definovať ako -1.


Binárne stromy

V ďalšej časti tejto prednášky nás budú zaujímať iba binárne stromy, t.j. stromy stupňa maximálne 2. Pre binárne stromy nás bude zaujímať ešte jedna dôležitá vlastnosť: pre každého potomka budeme špecifikovať, či je to ľavý alebo pravý syn. Môže nastať aj prípad, že pre nejaký vrchol je definovaný iba pravý syn a ľavý pritom neexistuje.

Napríklad pre 3 vrcholy existuje týchto 5 rôznych binárnych stromov:

5 binárnych stromov

Reprezentácie binárnych stromov

Stromy môžeme reprezentovať najrôznejšími spôsobmi. Skôr ako ukážeme najbežnejší spôsob pomocou smerníkov a objektov, ukážeme aj iné reprezentácie.



Jednorozmerné pole vrcholov



Neskôr sa budeme učiť usporiadanie prvkov v poli typu "halda". Tu sa využívajú pozície (indexy) prvkov poľa ako informácie o otcoch a synoch (predpokladajme, že prvky poľa číslujeme od 1). Koreň stromu je potom uložený v prvom prvku poľa (index 1). Jeho synovia sú na pozíciách 2 a 3. Synovia vrcholu v prvku 2 sú na indexoch 4 a 5 atď. Vo všeobecnosti platí, že I-ty vrchol má synov na indexoch 2*I a 2*I+1. Pri tejto reprezentácii treba ale zabezpečiť evidovanie neexistujúcich prvkov, napr. ak v strome neexistuje druhý syn koreňa, tak v 3-ťom prvku poľa musí byť o tom informácia - a zrejme potom nebudú existovať ani vrcholy v prvkoch 6 a 7, atď. V takejto reprezentácii stromu môže často vzniknúť veľa "dier" - prvkov, ktoré nereprezentujú vrcholy - a preto sa využíva hlavne na také binárne stromy, pre ktoré má väčšina vrcholov dvoch synov (zrejme okrem listov).



Jednorozmerné pole vrcholov s informáciami o synoch



Všetky vrcholy stromu uložíme do jednorozmerného poľa, pričom pri každom budeme uchovávať aj informáciu o jeho synoch, t.j. pri každom vrchole si budeme pamätať dva indexy pre ľavého a pravého syna. Nejako si musíme zaznačiť stav, keď daný syn neexistuje (napr. nulový alebo záporný index). Koreň stromu je najčastejšie prvým prvkom v poli.



Jednorozmerné pole vrcholov so spájaným zoznamom



Opäť máme pole vrcholov, pričom každý vrchol si okrem informačnej časti pamätá aj jednosmerný spájaný zoznam synov. V tomto zozname máme uložené indexy tých prvkov, ktoré sú synmi daného vrcholu. Takáto reprezentácia sa dá použiť nielen na binárny strom ale aj na ľubovoľný strom, ktorý nemá ohraničenie na počet synov (hovoríme mu všeobecný strom).



Smerník na záznam



Podobne ako sme spájané zoznamy najprv reprezentovali pomocou záznamu a smerníka na záznam, môžeme reprezentovať aj binárny strom:

type
  PStrom = ^TStrom;
  TStrom = record
    Info: Integer;
    L, P: PStrom;
  end;

Vidíme, že namiesto jedného smerníka na nasledovníka (Next) v každom vrchole, máme dva pokračujúce smerníky: na ľavého a pravého syna.



Dynamická definícia pomocou objektov



Toto je najčastejšia reprezentácia binárnych stromov. Vychádza z realizácie jednosmerných spájaných zoznamov, pričom v každom vrchole si namiesto jedného nasledovníka pamätáme dvoch nasledovníkov: ľavého a pravého syna. Týchto nasledovníkov budeme značiť stavovými premennými L a P:

type
  TStrom = class
    Info: Integer;
    L, P: TStrom;
    constructor Create(NoveInfo: Integer);
    constructor Create(NoveInfo: Integer; NoveL, NoveP: TStrom);
    function Text: string; virtual;
  end;
 
constructor TStrom.Create(NoveInfo: Integer);
begin
  Info := NoveInfo;
  L := nil;
  P := nil;
end;
 
constructor TStrom.Create(NoveInfo: Integer; NoveL, NoveP: TStrom);
begin
  Info := NoveInfo;
  L := NoveL;
  P := NoveP;
end;
 
function TStrom.Text: string;
begin
  Result := ' ' + IntToStr(Info);
end;
 
var S: TStrom;
 
...
  S := nil;             // prázdny strom

  S := TStrom.Create(1, nil, nil);
  S := TStrom.Create(1, TStrom.Create(2, nil, nil),
                        TStrom.Create(3, nil, nil));
  S := TStrom.Create(1, TStrom.Create(2, TStrom.Create(4, nil, nil),
                                         TStrom.Create(5, nil, nil)),
                        TStrom.Create(3, TStrom.Create(6, nil, nil),
                                         TStrom.Create(7, nil, nil)));
...

Ďalšie námety:

  • zistite, koľko existuje rôznych binárnych stromov, ktoré sú zložené presne z N vrcholov (môžete predpokladať, že v každom vrchole je hodnota 0)
  • ako by sa zmenilo riešenie predchádzajúcej úlohy, ak by v každom vrchole mohla byť 0 alebo 1?


Základné algoritmy

Začneme algoritmami, ktoré postupne navštívia všetky vrcholy a s každým vrcholom urobia nejakú akciu, napr. vypíšu jeho hodnotu. Vo všeobecnosti pre binárny strom s N vrcholmi existuje N! možných prechodov. Z nich len niektoré sú rozumné. Zoznámime sa s tromi základnými algoritmami na prechádzanie všetkých vrcholov stromu:

  • Preorder - najprv spracujeme informáciu v samotnom vrchole (napr. ju vypíšeme), potom rekurzívne spustíme tento algoritmus pre ľavý podstrom a na záver pre pravý podstrom.
  • Inorder - najprv spracuje ľavý podstrom, potom spracuje informáciu vo vrchole a na záver pravý podstrom.
  • Postorder - najprv spracuje ľavý, potom pravý podstrom a na záver informáciu v samotnom vrchole.

Tieto tri základné algoritmy sú veľmi podobné a líšia sa len poradím spracovávaných vrcholov, t.j. tým, kde v rekurzívnej procedúre sa nachádza spracovanie informácie vo vrchole. Naprogramujeme metódy Preorder, Inorder, Postorder, ktoré budú "vypisovať", t.j. vytvárať znakové reťazce s postupnými hodnotami vo vrcholoch:

function TStrom.Preorder: string;
begin
  Result := Text;
  if L <> nil then
    Result := Result + L.Preorder;
  if P <> nil then
    Result := Result + P.Preorder;
end;
 
function TStrom.Inorder: string;
begin
  Result := '';
  if L <> nil then
    Result := Result + L.Inorder;
  Result := Result + Text;
  if P <> nil then
    Result := Result + P.Inorder;
end;
 
function TStrom.Postorder: string;
begin
  Result := '';
  if L <> nil then
    Result := Result + L.Postorder;
  if P <> nil then
    Result := Result + P.Postorder;
  Result := Result + Text;
end;
 
...
  Memo1.Lines.Append('Preorder  =' + S.Preorder);
  Memo1.Lines.Append('Inorder   =' + S.Inorder);
  Memo1.Lines.Append('Postorder =' + S.Postorder);
...

Vo všeobecnosti by sme schému Preorder zapísali takto:

procedure TStrom.Preorder;
begin
  spracuj Info vo vrchole
  if L <> nil then
    L.Preorder;
  if P <> nil then
    P.Preorder;
end;

alebo ako globálnu procedúru (nie ako metóda triedy TStrom):

procedure Preorder(Vrchol: TStrom);
begin
  spracuj Info vo vrchole Vrchol
  if Vrchol.L <> nil then
    Preorder(Vrchol.L);
  if Vrchol.P <> nil then
    Preorder(Vrchol.P);
end;

alebo ako globálnu procedúru pričom vie spracovať aj prázdny strom:

procedure Preorder(Vrchol: TStrom);
begin
  if Vrchol = nil then
    spracuj prípad prázdny strom
  else
  begin
    spracuj Vrchol.Info
    Preorder(Vrchol.L);
    Preorder(Vrchol.P);
  end;
end;

Ďalšie námety:

  • naučte sa "ručne" vytvoriť postupnosti hodnôt vrcholov podľa všetkých troch algoritmov
  • sú dané dve postupnosti čísel, ktoré reprezentujú, napr. Inorder a Postorder výpis nejakého stromu
  • nakreslite tento strom
  • navrhnite algoritmus, ktorý skonštruuje strom na základe nejakých dvoch postupností čísel

Metóda Kresli nakreslí celý strom do grafickej plochy: koreň zobrazíme v strede hornej časti plochy, pod ním vľavo a vpravo nakreslíme jeho synov tak, aby každý bol v strede svojej polovice a oba boli nižšie ako ich otec, toto rekurzívne spravíme pre všetky vrcholy. Ako parametre do tejto metódy okrem pozície, kde bude umiestnený daný vrchol, zadáme aj šírku tej časti grafickej plochy, kde sa má daný vrchol nakresliť aj celým svojim podstromom:

procedure TStrom.Kresli(C: TCanvas; Sirka, X, Y: Integer);
begin
  if L <> nil then
  begin
    C.MoveTo(X, Y);
    C.LineTo(X - Sirka div 2, Y + 50);
    L.Kresli(C, Sirka div 2, X - Sirka div 2, Y + 50);
  end;
  if P <> nil then
  begin
    C.MoveTo(X, Y);
    C.LineTo(X + Sirka div 2, Y + 50);
    P.Kresli(C, Sirka div 2, X + Sirka div 2, Y + 50);
  end;
  C.Ellipse(X - 15, Y - 15, X + 15, Y + 15);
  C.TextOut(X - 5, Y - 8, Text);
end;
 
...
 
procedure TForm1.Button1Click(Sender: TObject);
begin
  S := TStrom.Create(...);
  ...
  Image1.Canvas.FillRect(Image1.ClientRect);
  S.Kresli(Image1.Canvas, Image1.Width div 2, Image1.Width div 2, 30);
end;

Metóda NahodnePridaj slúži na pridávanie nového vrcholu na náhodné miesto stromu. Môžeme ju využiť pri ladení algoritmov so stromami:

procedure TStrom.NahodnePridaj(I: Integer);
begin
  if Random(2) = 0 then
    if L = nil then
      L := TStrom.Create(I, nil, nil)
    else
      L.NahodnePridaj(I)
  else
    if P = nil then
      P := TStrom.Create(I, nil, nil)
    else
      P.NahodnePridaj(I);
end;
 
...
  S := TStrom.Create(1, nil, nil);
  for I := 2 to 20 do
    S.NahodnePridaj(I);

Uvedomte si, že pridávať vrchol pomocou tohto algoritmu môžeme len vtedy, ak je strom neprázdny - preto sme najprv vytvorili koreň stromu.

Procedurálny parameter v strome

Metóda Vsetky vykoná nejaký príkaz (procedúra Prikaz) s každým vrcholom stromu (algoritmus prechádza strom metódou Preorder):

type
  TStrom = class;
  TPrikaz = procedure(S: TStrom);
  TStrom = class
    ...
    procedure Vsetky(Prikaz: TPrikaz);
  end;
 
procedure TStrom.Vsetky(Prikaz: TPrikaz);
begin
  Prikaz(Self);
  if L <> nil then
    L.Vsetky(@Prikaz);
  if P <> nil then
    P.Vsetky(@Prikaz);
end;

Všimnite si, že sme najprv zadeklarovali triedu TStrom ako class; bez samotnej definície. Toto funguje podobne ako direktíva forward, t.j. sľubujem, že o chvíľu sa objaví deklarácia TStrom. Tu sme to museli použiť preto, lebo v definícii žeTPrikaz sa potrebujeme odvolávať na TStrom a naopak v definícii TStrom sa odvolávame na TPrikaz. Tiež si všimnite, že od typu schémy metódy Vsetky (t.j. či je to Preorder, Inorder alebo Postorder), bude závisieť aj poradie spracovávania vrcholov. Napr. pomocou takto zadefinovanej metóda Vsetky budú aj nasledujúce procedúry spúšťané v poradí Preorder:

procedure Zmen(S: TStrom);
begin
  Inc(S.Info);
end;
 
var
  Retazec: string;
 
procedure Test(S: TStrom);
begin
  Retazec := Retazec + S.Text;
end;
 
var
  X: Integer;
 
procedure Ocisluj(S: TStrom);
begin
  S.Info := X;
  Inc(X);
end;
 
...
 
begin
  if S <> nil then
    S.Vsetky(@Zmen);
  Retazec := 'test =';
  if S <> nil then
    S.Vsetky(@Test);
  Form1.Memo1.Lines.Append(Retazec);
  X := 0;
  if S <> nil then
    S.Vsetky(@Ocisluj);
end;


Ďalšie algoritmy na stromoch

Zistíme počet listov stromu:

function TStrom.PocetListov: Integer;
begin
  if (L = nil) and (P = nil) then
    Result := 1
  else
  begin
    Result := 0;
    if L <> nil then
      Inc(Result, L.PocetListov);
    if P <> nil then
      Inc(Result, P.PocetListov);
  end;
end;

Všimnite si tri rôzne prístupy k riešeniu úloh na stromoch. Napr. zisťujeme súčet hodnôt v strome a funkcia môže byť: rekurzívna metóda, nerekurzívna metóda, rekurzívna globálna funkcia:

// obyčajná rekurzívna metóda
function TStrom.Sucet: Integer;
begin
  Result := Info;
  if L <> nil then
    Inc(Result, L.Sucet);
  if P <> nil then
    Inc(Result, P.Sucet);
end;
 
// nerekurzívna metóda
function TStrom.NRsucet: Integer;
var
  Stack: array [1..100] of TStrom;
  SP: Integer;       // Stack pointer = ukazovateľ na vrch zásobníka
  S: TStrom;
begin
  Result := 0;
  SP := 1;
  Stack[SP] := Self;
  repeat
    if Stack[SP] = nil then
      Dec(SP)
    else
    begin
      S := Stack[SP];
      Inc(Result, S.Info);
      Stack[SP] := S.L;
      Inc(SP);
      Stack[SP] := S.P;
    end;
  until SP = 0;
end;
 
// ako externá funkcia s parametrom TStrom
function Sucet(S: TStrom): Integer;
begin
  if S = nil then
    Result := 0
  else
    Result := S.Info + Sucet(S.L) + Sucet(S.P);
end;

Dve verzie algoritmu na zistenie hĺbky stromu - ako metóda a ako globálna funkcia:

function TStrom.Hlbka: Integer;
begin
  if L <> nil then
    if P <> nil then
      Result := Max(L.Hlbka, P.Hlbka) + 1
    else
      Result := L.Hlbka + 1
  else if P <> nil then
    Result := P.Hlbka + 1
  else
    Result := 0;
end;
 
function Hlbka(S: TStrom): Integer;
begin
  if S = nil then
    Result := -1
  else
    Result := Max(Hlbka(S.L), Hlbka(S.P)) + 1;
end;

Použili sme tu funkciu Max z unitu Math.

Ďalšie námety:

  • nerekurzívne: hĺbka, počet vrcholov, preorder
  • vzdialenosť najbližšieho listu od koreňa (plytčina)



Ďalšie pojmy



  • dva stromy sú podobné, ak majú rovnakú štruktúru (rovnaký tvar)
  • jeden strom je kópiou druhého, ak sú podobné a majú rovnaký obsah všetkých zodpovedajúcich si vrcholov
  • úplný strom úrovne U má vo všetkých úrovniach (0 až U) maximálny počet vrcholov
    • pre úplný strom platí, že všetky jeho listy majú rovnakú vzdialenosť od koreňa
  • šírka stromu je najväčší počet vrcholov na jednej úrovni, t.j. spočítame počty vrcholov v jednotlivých úrovniach a maximum z týchto čísel sa nazýva šírka stromu

Ukážeme veľmi neefektívny algoritmus na zistenie šírky stromu:

function TStrom.Sirka: Integer;
var
  N, Pom: Integer;
begin
  N := 0;
  Result := 0;
  repeat
    Pom := PocetNaUrovni(N);
    if Pom > Result then
      Result := Pom;
    Inc(N);
  until Pom = 0;
end;
 
function TStrom.PocetNaUrovni(N: Integer): Integer;
begin
  if N = 0 then
    Result := 1
  else
  begin
    Result := 0;
    if L <> nil then
      Inc(Result, L.PocetNaUrovni(N-1));
    if P <> nil then
      Inc(Result, P.PocetNaUrovni(N-1));
  end;
end;

Ďalšie námety:

  • navrhnite efektívnejší algoritmus na zistenie šírky stromu

Funkcia Hladaj hľadá prvý výskyt nejakej hodnoty v strome. Keďže nemáme žiadne usporiadanie vrcholov strome podľa hodnôt, nevieme zistiť či sa nejaký vrchol v strome nenachádza, kým neprejdeme všetky vrcholy. Funkcia vráti buď nájdený vrchol, alebo hodnotu nil:

function TStrom.Hladaj(X: Integer): TStrom;
begin
  if X = Info then
    Result := Self
  else
  begin
    Result := nil;
    if L <> nil then
      Result := L.Hladaj(X);
    if (Result = nil) and (P <> nil) then
      Result := P.Hladaj(X);
  end;
end;

Ďalšie námety:

  • vyrobiť podobný strom (k danému), ale s nulovými hodnotami
  • vyrobiť kópiu stromu
  • generovanie úplného stromu
  • očíslujte strom po úrovniach - v jednej úrovni zľava doprava
  • vypíšte vrcholy po úrovniach
  • pridaj vrchol na náhodné miesto (s rovnakou pravdepodobnosťou pre ľubovoľné miesto)
    • všimnite si, že vyššie naprogramovaná metóda NahodnePridaj niekedy nepridáva s rovnakou pravdepodobnosťou na všetky voľné miesta, napr. ak je v ľavom podstrome 100 vrcholov a pravý podstrom je prázdny, tak prvé Random s rovnakou pravdepodobnosťou (0.5) pridá vrchol buď niekde medzi 100 vrcholov v ľavom podstrome, alebo ako pravého syna koreňa

Zapuzdrenie triedy TStrom

Doteraz sme sa k samotnému vrcholu stromu (TStrom) správali, ako by to bol celý strom: keď sme chceli vedieť súčet hodnôt vo všetkých vrcholoch, spýtali sme sa to koreňa, ten sa to rekurzívne spýtal svojich synov a keď mu to títo dvaja odpovedali, tak tieto výsledky spočítal ... Programátrosky elegantnejšie by bolo oddeliť definíciu vrcholu a celého stromu tak, ako sme to robili aj pri spájaných zoznamoch (TVrchol a TZoznam):

type
  TPrvok = Integer;
  TVrchol = class
    Info: TPrvok;
    L, P: TVrchol;
    constructor Create(NoveInfo: TPrvok; NoveL, NoveP: TVrchol);
    function Text: string; virtual;
  end;
 
constructor TVrchol.Create(NoveInfo: TPrvok; NoveL, NoveP: TVrchol);
begin
  Info := NoveInfo;
  L := NoveL;
  P := NoveP;
end;
 
function TVrchol.Text: string;
begin
  Result := ' ' + IntToStr(Info);
end;

Samotná trieda TStrom bude obsahovať smerník na koreň stromu:

type
  TStrom = class
  private
    Koren: TVrchol;
  public
    constructor Create;
    destructor Destroy: override;
    function Text: string;          // napr. preorder
    function Hladaj(X: Integer): TVrchol;
    procedure Kresli(Image: TImage);
    procedure VlozNahodne(X: TPrvok);
    function Pocet: Integer;
    ...
  end;
 
constructor TStrom.Create;
begin
  Koren := nil;         // netreba
end;
 
function TStrom.Text: string;
  function Text1(Vrchol: TVrchol): string;
  begin
    if Vrchol = nil then
       Result := ''
     else
       Result := Vrchol.Text + Text1(Vrchol.L) + Text1(Vrchol.P);
  end;
begin
  Result := Text1(Koren);
end;
 
function TStrom.Hladaj(X: Integer): TVrchol;
  function Hladaj1(Vrchol: TVrchol): TVrchol;
  begin
    if Vrchol = nil then
      Result := nil
    else if X = Vrchol.Info then
      Result := Vrchol
    else
    begin
      Result := Hladaj(Vrchol.L);
      if Result = nil then
        Result := Hladaj(Vrchol.P);
    end;
  end;
begin
  Result := Hladaj1(Koren);
end;
 
procedure TStrom.Kresli(Image: TImage);
var
  C: TCanvas;
  procedure Kresli1(Vrchol: TVrchol; Sirka, X, Y: Integer);
  begin
    if Vrchol.L <> nil then
    begin
      C.MoveTo(X, Y);
      C.LineTo(X - Sirka div 2, Y + 50);
      L.Kresli1(Vrchol.L, Sirka div 2, X - Sirka div 2, Y + 50);
    end;
    if Vrchol.P <> nil then
    begin
      C.MoveTo(X, Y);
      C.LineTo(X + Sirka div 2, Y + 50);
      P.Kresli(Vrchol.P, Sirka div 2, X + Sirka div 2, Y + 50);
    end;
    C.Ellipse(X - 15, Y - 15, X + 15, Y + 15);
    C.TextOut(X - 5, Y - 8, Vrchol.Text);
  end;
begin
  C := Image.Canvas;
  C.FillRect(Image.ClientRect);
  if Koren <> nil then
    Kresli(Koren, Image.Width div 2, Image.Width div 2, 30);
end;

Ďalšie námety:

  • dopracujte aj ďalšie metódy VlozNahodne, Pocet, Hlbka, ..., ktoré by mali fungovať aj pre prázdny strom


späť | ďalej