28.Prednaska/Cvicenie

28. Cvičenie

---

< 28.Prednáška | riešené úlohy

Cvičenie

• z daného binárneho stromu ručne vyrobiť preorder, inorder a postorder

• tento strom má postupne po úrovniach zapísané písmená slova 'programovanie'

preorder  = prgmonroaviea
inorder   = mgnorrpiveaao
postorder = mnogrrievaaop

• trieda TStrom zo StromUnit.pas

type
  TStrom = class
    Info: Char;
    L, P: TStrom;
    constructor Create(Z: Char);
    constructor Create(Z: Char; LL, PP: TStrom);
    function Text: string;
  end;
 
constructor TStrom.Create(Z: Char);
begin
  Info := Z;
end;
 
constructor TStrom.Create(Z: Char; LL, PP: TStrom);
begin
  Info := Z;
  L := LL;
  P := PP;
end;

• zadefinovať strom pomocou vnorených konštruktorov

• pre podstromy vyskytujúce sa viackrát definovať podstrom S1 a vložiť na správne miesta

• metóda PreOrder - podobne bude vyzerať väčšina stromových podprogramov

procedure TStrom.PreOrder;
begin
  Write(Text);
  if L <> nil then
    L.PreOrder;
  if P <> nil then
    P.PreOrder;
end;

• PreOrder ako globálna procedúra

procedure PreOrder(S: TStrom);

• metóda PreOrder ale ako stringová funkcia

function TStrom.PreOrder: string;

• metódy InOrder a PostOrder

procedure TStrom.InOrder;
begin
  if L <> nil then
    L.InOrder;
  Write(Text);
  if P <> nil then
    P.InOrder;
end;
 
procedure TStrom.PostOrder;
begin
  if L <> nil then
    L.PostOrder;
  if P <> nil then
    P.PostOrder;
  Write(Text);
end;

• metóda VypisListov - vypíše len všetky listy stromu (je jedno, či používame pre- in- alebo post-order schému)

• metóda PocetListov

• metódy Pocet a PocetVnutornych - budú počítať počet všetkých a počet vnútorných vrcholov stromu(tj. majú aspoň jedného syna)

• takisto si môžeme niektorú z týchto funkcií zapísať ako globálnu funkciu s parametrom TStrom

• nakresliť na tabuľu prázdny strom rovnakého tvaru ako predchádzajúci

• zapísať do vrcholov písmena zo slova 'programovanie' tak, aby výsledkom preorder bolo 'programovanie'

• aby sa jednoduchšie definoval strom pomocou volaní TStrom.Create(...), môžeme zadefinovať pomocnú funkciu:

function v(Z: char; LL: TStrom = nil; PP: TStrom = nil): TStrom;
begin
  Result := TStrom.Create(Z, LL, PP);
end;

• potom pôvodný strom zapíšeme

S := v('p', v('r', v('g', v('m'), v('o', v('n'), nil)), v('r')), v('o', v('a', v('v', v('i'), v('e')), v('a')), nil));

• ak si všimneme poradie znakov v tomto zápise - je to preorder - ľahko sa vyrobí strom, ktorého preorder je 'programovanie':

S := v('p', v('r', v('o', v('g'), v('r', v('a'), nil)), v('m')), v('o', v('v', v('a', v('n'), v('i')), v('e')), nil));

• takýto zápis môžeme vytvoriť aj upraveným výpisom PreOrder:

procedure TStrom.PreOrderCreate: string;

• opačná úloha: máme preorder a inorder, treba zistiť, ako vyzerá strom, a tiež postorder

o preorderi vieme, že prvý znak je koreň stromu

v inorderi zase, že koreň je medzi zápismi ľavého a pravého podstromu

preorder: ABCEFGD
inorder: ACFEGBD

výsledný strom

S := v('A', nil, v('B', v('C', nil, v('E', v('F'), v('G'))), v('D')));

• postorder tohto stromu je

postorder = FGECDBA

• metóda Pokaz(Z: Char) - prejde celým stromom a do každého vrchola zapíše znak Z

• metóda Naprav(S: string) - prejde celým stromom a do vrcholov zapíše písmena daného stringu tak, aby postorder bol rovnaký ako zadaný string, napr. volanie S.Naprav('programovanie')

procedure TStrom.Naprav(S: string);
begin
  Info := S[1];
  Delete(S, 1, 1);              // vyhodí prvý znak
  if L <> nil then
  begin
    L.Naprav(S);
    Delete(S, 1, L.Pocet);      // vyhodí toľko znakov, koľko je ich v ľavom podstrome
  end;
  if P <> nil then
    P.Naprav(S);
end;

• efektívnejšie, ak parameter bude typu var

procedure TStrom.Naprav(var S: string);
begin
  Info := S[1];
  Delete(S, 1, 1);              // vyhodí prvý znak
  if L <> nil then
    L.Naprav(S);
  if P <> nil then
    P.Naprav(S);
end;

Ďalšie námety

---

• metóda TStrom.VypisNaUrovni(K: Integer) vypíše všetky vrcholy na úrovni K
• metóda funkcia TStrom.PocetNaUrovni(K: Integer): Integer zistí počet vrcholov na úrovni K
• metóda TStrom.VypisPoUrovniach vypíše všetky vrcholy po úrovniach, napr. 0. úroveň (koreň), potom do druhého riadku vrcholy na 1. úrovni, ...
• metóda TStrom.PriradPoUrovniach(S: string) postupne zapíše do vrcholov znaky z reťazca po úrovniach

Domáca úloha

1. vygenerovať a nakresliť náhodný strom s číslami vo vrcholoch od 1 do 20

• klikanie myšou na ľubovoľný vrchol zvýši číslo v tomto vrchole o 1 (a prekreslí vrchol alebo celý strom)

2. konštruktor TStrom.Create(Preorder, Inorder: string) skonštruuje celý strom (vo vrcholoch sú znaky), ktorého parameter Preorder je preorderovský výstup a Inorder je inorderovský výstup