čo sme sa doteraz naučili

• binárne stromy
• binárny vyhľadávací strom

čo sa budeme dnes učiť

• ďalšie typy stromov: aritmetický strom, všeobecný strom, všeobecný zoznam, lexikografický strom
• komponent TTreeView

Aritmetické stromy

• binárny strom
• vo vnútorných vrcholoch sú binárne operácie (+, -, /, *)
• v listoch sú operandy (napr. čísla alebo identifikátory premenných)
• dôležitá vlastnosť: každý vrchol má 0 alebo 2 synov (nemôže mať iba 1)

• každému aritmetickému výrazu (úplne uzátvorkovanému) zodpovedá práve jeden aritmetický strom a naopak, napr. dan7 strom má takýto úplne uzátvorkovaný infixový zápis:  (( 5 - 2 ) * ( 1 + 3 ))
• ak sa strom vypíše pre-order -> vznikne pre-fix zápis, napr. * - 5 2 + 1 3
• ak sa strom vypíše post-order -> vznikne post-fix zápis, napr. 5 2 - 1 3 + *

type
  TPrvok = integer;
  TAStrom = class
    function hodnota:TPrvok; virtual; abstract;
    function prefix:string; virtual; abstract;
  end;

  TAOperacia = class(TAStrom)
    op:char;
    l,p:TAStrom;
    constructor Create(z:char; ll,pp:TAStrom);
    function hodnota:TPrvok; override;
    function prefix:string; override;
  end;

  TAOperand = class(TAStrom)
    hod:TPrvok;
    constructor Create(h:TPrvok);
    function hodnota:TPrvok; override;
    function prefix:string; override;
  end;

constructor TAOperacia.Create(z:char; ll,pp:TAStrom);
begin
  op:=z; l:=ll; p:=pp;
end;

function TAOperacia.hodnota:TPrvok;
begin
  case op of
    '+': Result:=l.hodnota+p.hodnota;
    '-': Result:=l.hodnota-p.hodnota;
    '*': Result:=l.hodnota*p.hodnota;
    '/': Result:=l.hodnota div p.hodnota;
    else raise Exception.Create('nerozumiem '+op);
  end;
end;

function TAOperacia.prefix:string;
begin
  Result:=' '+op+l.prefix+p.prefix;
end;

constructor TAOperand.Create(h:TPrvok);
begin
  hod:=h;
end;

function TAOperand.hodnota:TPrvok;
begin
  Result:=hod;
end;

function TAOperand.prefix:string;
begin
  Result:=' '+IntToStr(hod)
end;

procedure TForm1.FormCreate(Sender: TObject);
var
  a:TAStrom;
begin
  a:=TAOperacia.Create('-',
        TAOperacia.Create('*',
           TAOperand.Create(7),
           TAOperand.Create(3)),
        TAOperacia.Create('/',
           TAOperand.Create(15),
           TAOperand.Create(3)));
  Memo1.Lines.Add('prefix ='+a.prefix);
  Memo1.Lines.Add('hodnota ='+inttostr(a.hodnota));
end;

Pozn.

• direktíva abstract
• zabezpečí, že bázová trieda definuje virtuálne metódy
• tieto metódy sa nesmú volať priamo - spôsobí to chybovú správu - môžu sa volať len jej prekryté (override) metódy
• vďaka tomuto môžeme definovať abstraktnú bazovú triedu
• napr. aj TStream má niektoré metódy abstract: read, write a seek
• príkaz raise Exception.Create('text chyby'); spôsobí prerušenie výpočtu s danou chybovou správou

NDÚ:

• zrealizujte postfixový a úplne uzátvorkovaný infixový výpis aritmetického stromu
• skonštruujte aritmetický strom z prefixového (postfixového, úplne uzátvorkovaného) zápisu
• navrhnite tretí typ vrcholu - premenná:
• výpis (napr. prefix) vypíše identifikátor,
• hodnota vráti hodnotu premennej z tabuľky (tabuľka je dvojstĺpcové pole: identifikátor premennej a hodnota premennej)
• aritmetický strom sa dá reprezentovať jediným typom vrcholu, ktorý obsahuje zlúčené stavové premenné zo všetkých typov vrcholov a tiež stavovú premennú, ktorá vyjadruje typ vrcholu (napr. operand, operátor, ...) - naprogramujte metódy pre takúto reprezentáciu

type
  TAStrom = class
    typ:(operand,operacia);
    hod:integer;
    op:char;
    l,p:TAStrom;
    constructor CreateOperand(h:integer);
    constructor CreateOperaciu(z:char; ll,pp:TAstrom);
    ...
  end;

Všeobecné stromy

• každý vrchol má ľubovoľný počet synov

type
  TStrom = class
    info:TPrvok;
    syn:array[1..N] of TStrom;
  end;

type
  TStrom = class
    info:TPrvok;
    syn:array of TStrom;
  end;

Často sa v praxi používa aj iná reprezentácia - vychádza z binárneho stromu (budeme ju volať syn-brat):

• v každom vrchole - informácia
• 1. smerník - prvý (najľavejší, najstarší, prvorodený) syn
• 2. smerník - brat, t.j. nasledujúci vrchol so spoločným otcom
• reťaz vrcholov spojených smerníkom brat tvorí jednosmerný spájaný zoznam synov nejakého vrcholu

strom vľavo je reprezentovaný pomocou syn-brat vpravo

type
  TStrom = class
    info:TPrvok;
    syn,brat:TStrom;
  end;

Pozn.: koreň väčšinou nemá bratov - ak by mal, voláme túto štruktúru "les"

NDÚ:

(vo všetkých troch reprezentáciách):

• hĺbka, šírka, súčet hodnôt,  ...
• výpis ako reťazec alebo nakreslenie do Canvasu
• zistiť, či je strom binárny, počet listov
• prekódovať binárny strom do tejto reprezentácie - treba si uvedomiť, ža sa stratí informácia o tom, že napr. ľavý syn neexistuje ale pravý áno
• pridaj(i,j,prvok) - pridať nového syna í-temu vrcholu v úrovni j
• vytvoriť alebo načítať textový súbor popisujúci strom - každý riadok jeden vrchol, počet medzier na začiatku riadka označuje úroveň vnorenia (koreň - prvý riadok začína v 1. stĺpci, jeho synovia začínajú na druhých stĺpcoch ...)

Všeobecné zoznamy

Zatiaľ sme poznali lineárny zoznam - postupnosť (aj prázdna) atómov, napr. (a b c d)

Všeobecný zoznam je

• atóm - napr. string, číslo, ...
• postupnosť atómov a zoznamov (aj prázdna) uzavretá v okrúhlych zátvorkách
• napr. (), (a b), (a b c d e f), (a () b), ((a b) c (d) ()), ...

Použijeme podobnú reprezentáciu ako pre aritmetické stromy (abstraktná bázová trieda a od nej odvodené dva typy vrcholov), pričom štruktúra sa podobá všeobecnému stromu typu syn-brat, napr.

type
  TPrvok = string;
  TVseobZoznam = class
    function vypis:string; virtual; abstract;
    function prvy:TVseobZoznam; virtual;
  end;

  TAtom = class(TVseobZoznam)
    hodn:TPrvok;
    constructor Create(h:TPrvok);
    function vypis:string; override;
  end;

  TZoznam = class(TVseobZoznam)
    syn:TVseobZoznam;
    dalsi:TZoznam;
    function vypis:string; override;
    function prvy:TVseobZoznam; override;
  end;

Príklad ilustruje čítanie dobrého všeobecného zoznamu do zadanej dátovej štruktúry a jeho výpis v rovnakom tvare:

type
  TPrvok = string;

var
  lex:(kon,lz,pz,at);   // urobíme si skener, ktorý bude rozpoznávať
  hodnota:TPrvok;       // v globálnej premennej hodnota čakáme hodnotu atómu
  z:char;
  vstup:string;         // vstupný - analyzovaný reťazec

procedure skener;         // štandardný skener
var
  ok:boolean;

  procedure znak;
  begin
    if vstup='' then z:=#0
    else begin z:=vstup[1]; delete(vstup,1,1) end;
  end;

begin
  repeat
    ok:=true;
    case z of
      #0:
        lex:=kon;
      '(':
        begin lex:=lz; znak end;
      ')':
        begin lex:=pz; znak end;
      'a'..'z','A'..'Z','0'..'9': begin
        hodnota:='';
        while z in ['a'..'z','A'..'Z','0'..'9'] do begin
          hodnota:=hodnota+z; znak;
        end;
        lex:=at;
      end;
      else
        begin znak; ok:=false end;
    end;
  until ok;
end;
 
type
  TVseobZoznam = class
    function vypis:string; virtual; abstract;
    function prvy:TVseobZoznam; virtual;
  end;

  TAtom = class(TVseobZoznam)
    hodn:TPrvok;
    constructor Create(h:TPrvok);
    function vypis:string; override;
  end;

  TZoznam = class(TVseobZoznam)
    syn:TVseobZoznam;
    dalsi:TZoznam;
    function vypis:string; override;
    function prvy:TVseobZoznam; override;
  end;

constructor TAtom.Create(h:TPrvok);
begin
  hodn:=h;
end;

function TAtom.vypis:string;
begin
  Result:=hodn+' ';
end;

function TZoznam.vypis:string;
var
  s:TZoznam;
begin
  Result:='( '; s:=self;
  repeat
    if s.syn<>nil then Result:=Result+s.syn.vypis;
    s:=s.dalsi;
  until s=nil;
  Result:=Result+') ';
end;

function TVseobZoznam.prvy:TVseobZoznam;
begin
  raise Exception.Create('nedá sa urobiť PRVY');  // mohlo byť aj abstract
end;

function TZoznam.prvy:TVseobZoznam;
begin
  Result:=syn;
  if Result=nil then
    raise Exception.Create('nedá sa urobiť PRVY z prázdneho zoznamu');
end;

function citaj:TVseobZoznam;

  function citajchvost:TZoznam;
  begin
    if lex=pz then begin
      Result:=nil; skener;
    end
    else if lex=kon then Result:=nil
    else begin
      Result:=TZoznam.Create;
      TZoznam(Result).syn:=citaj;
      TZoznam(Result).dalsi:=citajchvost;
    end;
  end;

begin
  if lex=at then begin
    Result:=TAtom.Create(hodnota);
    skener;
  end
  else if lex=lz then begin
    skener;
    Result:=TZoznam.Create;
    TZoznam(Result).syn:=citaj;
    TZoznam(Result).dalsi:=citajchvost;
  end
  else Result:=nil;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  s:TVseobZoznam;
begin
  vstup:=Edit1.Text; z:=' '; skener; s:=citaj;
  if s=nil then
    Memo1.Lines.Add('prázdny zoznam - nil')
  else
    Memo1.Lines.Add(s.vypis);
end;

NDÚ:

testovací program neobsahuje uvoľňovanie pamäti - metóda Destroy, doprogramujte ju

• funkcie, ktoré vrátia: í-ty, posledný prvok zoznamu, zoznam bez prvého prvku, bez posledného, bez í-teho prvku
• kópia všeobecného zoznamu, počet atómov, počet výskytov ...,
• porovnanie dvoch zoznamov
• konštruktor CreateFromStream(t:TStream) - z jedného riadka textového súboru
• metódy: vlozprvy(prvok:TVseobZoznam), vlozposledny(prvok:TVseobZoznam),
• prevrat, pripoj(z:TVseobZoznam)
• zmeňte reprezentáciu všeobecného zoznamu tak, že vrchol je buď atóm alebo obsahuje dynamické pole svojich prvkov
• realizujte načítanie, výpis a aj ostatné metódy

Lexikografické stromy

• v binárnom strome každá cesta od koreňa do ľubovoľného vrcholu jednoznačne reprezentuje tento vrchol, napr. LLPLLLPPL označuje vrchol s.l.l.p.l.l.l.p.p.l; podobne sa dá označovať ľubovoľný vrchol aj v N-árnom strome - použijeme N-písmen abecedy, napr. 'a'..'k'
• túto vlastnosť môžeme využiť na reprezentáciu (evidovanie) slov z nejakej N-prvkovej abecedy
• lexikografické stromy sú N-árne stromy
• každý vrchol reprezentuje prvých K znakov zo slova (K je vzdialenosť od koreňa)
• koreň reprezentuje prázdne slovo
• synovia koreňa reprezentujú jednoznakové slová, atď.
• v info položke môžeme reprezentovať informáciu rôzneho typu, napr. počet výskytov daného slova; reťazec reprezentujúci preklad; kód prekladu v encyklopédii

Príklad

• Zistite frekvenčnú tabuľku slov na vstupe z abecedy {a,b}.
• najprv vytvoríme lexikografický strom - do info počet výskytov
• vypíšeme cestu k nenulovým vrcholom aj s hodnotou

type
  TLexStrom = class
    pocet:integer;
    p:array['a'..'b'] of TLexStrom;
    constructor Create;
    procedure pridaj(const s:string);
    procedure vypis(t:TStrings; const s:string);
  end;

constructor TLexStrom.Create;
begin
  pocet:=0; p['a']:=nil; p['b']:=nil;
end;

procedure TLexStrom.pridaj(const s:string);
begin
  if s='' then inc(pocet)
  else if s[1] in ['a','b'] then begin
    if p[s[1]]=nil then p[s[1]]:=TLexStrom.Create;
    p[s[1]].pridaj(copy(s,2,maxint));
  end
  else
    pridaj(copy(s,2,maxint));   // raise Exception.Create('chybný znak: '+s[1]);
end;

procedure TLexStrom.vypis(t:TStrings; const s:string);
begin
  if pocet<>0 then t.Add(IntToStr(pocet)+' '''+s+'''');
  if p['a']<>nil then p['a'].vypis(t,s+'a');
  if p['b']<>nil then p['b'].vypis(t,s+'b');
end;

procedure TForm1.FormCreate(Sender: TObject);
var
  l:TLexStrom;
begin
  l:=TLexStrom.Create;
  l.pridaj('abaa');
  l.pridaj('bb');
  l.pridaj('');
  l.pridaj('aaaaaaaaaaaaaaaaaaaaaaaaaaaa');
  l.pridaj('abaabba');
  l.pridaj('abaabab');
  l.pridaj('aabb');
  l.pridaj('abab');
  l.pridaj('aabb');
  l.pridaj('abaa');

  l.vypis(Memo1.Lines,'');
end;

Pozn.

• použili sme preddefinovanú triedu TStrings - postupnosť reťazcov - napr. Memo1.Lines je typu TStrings
• už máme skúsenosti, že pre TStrings existujú metódy Clear a Add, ale sú definované aj metódy Delete, Insert, LoadFromStream, LoadFromFile, ...
• užitočné vlastnosti (property) triedy: Count, Strings[index], Text

NDÚ:

• pridaj aj vypis sú rekurzívne => môže pretiecť zásobník - prerobte bez rekurzie
• v testovacom programe vypíšte aj počet vrcholov stromu, hĺbku stromu, počet rôznych slov dĺžky 1, 2, 3, ...
• metóda hladaj - nájde vrchol v strome pre dané slovo - realizujte rekurzívne aj nerekurzívne
• dorobiť pre N-prvkovú abecedu
• napr. 'a'..'j' - 10-árny strom
• napr. len písmená 'a','e','i','o','u','y' - 6-árny strom
• metódy triedy, ktoré nájdu
• slová danej dĺžky
• najkratšie, najdlhšie slová
• najkratšie slovo začínajúce daným reťazcom
• dĺžka najdlhšieho slova = hĺbka stromu
• navrhnite metódy na rušenie slova alebo všetkých slov, ktoré začínajú nejakým reťazcom
• lexikografický strom vytvárať v binárnom súbore (namiesto smerníkov budú seek-adresy viet, nil=napr.0)
• pomocou lexikálneho stromu reprezentujte množiny slov nad nejakou abecedou (namiesto stavovej premennej pocet bude informácia o tom, či patrí do množiny) => zrealizujte operácie zjednotenia, prieniku

Komponent TTreeView

Tento Delphi komponent umožňuje zobraziť údaje, ktoré majú stromovú štruktúru, vo vizuálnej forme, napr.

Komponent TTreeView je dosť komplexný - tu popíšeme len niekoľko stavových premenných a metód:

• vrcholmi stromu sú inštancie triedy TTreeNode
• Items[i] vráti í-ty vrchol
• Items.Count - počet synov
• Items.Add(vrchol,reťazec) - vrcholu pridá nového brata s daným textom - reťazcom
• Items.AddFirst(...) - ako Add - pridá nového brata, ktorý sa stane prvým synom ich otca
• Items.AddChild(vrchol,reťazec) - vrcholu pridá nového syna s daným textom - reťazcom (podobne aj AddChildFirst)
• LoadFromFile(meno_súboru) - z textového súboru načíta kompletný strom - každý riadok popisuje jeden vrchol stromu, počet medzier, resp. tabulátorov na začiatku riadka vyjadruje "vnorenie" vrcholu
• SaveToFile(meno_súboru) - vytvorí textový súbor, ktorý popisuje kompletný strom
• Items.Delete(vrchol) - vyhodí vrchol zo stromu
• GetNodeAt(X,Y) - vráti vrchol (ak existuje), ktorý je zobrazený na súradniciach (X,Y)

Toto boli metódy a vlastnosti (property) triedy TTreeView, aj samotný vrchol - TTreeNode má dôležité stavové premenné - vlastnosti (property), napr.

• Count - počet synov
• Item[i] - smerník na í-teho syna
• Parent - smerník na otca
• Selected - či je/má byť označený - označený môže byť maximálne jeden vrchol v celom strome
• Index - koľký je to syn svojho otca
• Level - v akej úrovni stromu je tento vrchol
• Text - textový reťazec v danom vrchole

a niektoré dôležité metódy, napr.

• Delete - zruší vrchol
• DeleteChildren - zruší všetky deti
• GetNextSibling - nasledujúci brat
• GetPrevSibling - predchádzajúci brat
• GetFirstChild - prvý syn

var
  k,v1,v2:TTreeNode;
begin
  k:=TreeView1.Items.Add(nil,'koreň stromu');
  v1:=TreeView1.Items.AddChild(k,'druhý vrchol');
  v2:=TreeView1.Items.Add(v1,'tretí vrchol');
//  v2:=TreeView1.Items.AddChild(k,'tretí vrchol');
             // to je to isté ako predchádzajúci riadok

Malý testovací projekt

• na formulár položte komponenty:
• TTreeView z palety Win32
• TEdit
• 2 TButton s popismi "Pridaj" a "Pridaj syna"
• TCheckBox s popisom "Pridávaj na začiatok"

procedure TForm1.Button1Click(Sender: TObject);
var
  sel,novy:TTreeNode;
begin
  if Edit1.Text='' then exit;
  sel:=TreeView1.Selected;
  if CheckBox1.Checked then
    novy:=TreeView1.Items.AddFirst(sel,Edit1.Text)
  else
    novy:=TreeView1.Items.Add(sel,Edit1.Text);
  novy.Selected:=true;
  SetFocus;
  Edit1.Text:='';
end;

procedure TForm1.Button2Click(Sender: TObject);
var
  sel,novy:TTreeNode;
begin
  if Edit1.Text='' then exit;
  sel:=TreeView1.Selected;
  if CheckBox1.Checked then
    novy:=TreeView1.Items.AddChildFirst(sel,Edit1.Text)
  else
    novy:=TreeView1.Items.AddChild(sel,Edit1.Text);
  novy.Selected:=true;
  TreeView1.SetFocus;
  Edit1.Text:='';
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  if FileExists('strom.txt') then
    TreeView1.LoadFromFile('strom.txt');
end;

procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);
begin
  TreeView1.SaveToFile('strom.txt');
end;

NDÚ:

• vytvorte TreeView zo štruktúry adresárov