29.Prednaska/Cvicenie

Z Pascal
Prejsť na: navigácia, hľadanie

29. Cvičenie


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



Cvičenie

  • BVS (binárny vyvážený strom)
type
  TBVS = class
    Koren: TVrchol;
  end;
  • ručne vytvoriť, ak postupne pridávame:
6, 2, 4, 7, 3, 9, 5, 8, 1
  • pridať
6.5, 1.5, 5.5
  • vytvoriť uvedený strom v aplikácii z prednášky
  • funkcia TBVS.Min: TVrchol, ktorá nájde minimálny vrchol stromu
  • všimnite si, že počet krokov while cyklu bude maximálne hĺbka stromu
  • na vykreslenie minima treba mať v aplikácii z prednášky (TForm1.Kresli) podporu
  • verzia Vloz s dynamickým poľom ako parametrom
function TVBStrom.Vloz(Hodnota: array of Integer);
  • nakresliť dostatočne košatý strom a ručne vyhadzovať vrchol zo stromu
  • ak má dvoch synov, minimum pravého podstromu sa presťahuje do vrcholu + potrebné upratovanie


  • aritmetické stromy
  • nakresliť strom aritmetického výrazu
5+7/(4-2*5)
  • preorder aritmetického výrazu
(4*5)+(7-9)

výsledok

'+ * 4 5 - 7 9'
a('+', a('*', b(4), b(5)), a('-', b(7), b(9)))
  • programujeme v prefixe, myslíme v infixe
  • postfix najrozumnejší z pohľadu vyhodnocovania


  • lexikografické stromy
  • písmená samozrejme nepíšeme do vrcholov, ale na hrany
  • nakresliť strom obsahujúci
aab
cbb
cab
bba
bbb



Ďalšie námety


  • vzorová úloha na teste: počet listov, hĺbka lexikografického stromu pre
mama
ma
emu
a
ema
ma
mamu



Domáca úloha

  • konštruktor, ktorý ako parameter dostáva string so zápisom aritmetického stromu v prefixe oddelený medzerami a vytvorí BVS
'+ * 4 5000 - 712 94'
zrejme budeme musieť použiť rekurziu
čísla môžu byť aj viacciferné
AStrom := v('+', v('*', c(4), c(5)), v('-', c(7), c(9)));
//Astrom := Vytvor('+ * 4 5 - 7 9');
Memo1.Lines.Add('Prefix = ' + AStrom.Prefix);
Memo1.Lines.Add('Infix = ' + AStrom.Infix);
Memo1.Lines.Add('Hodnota = ' + AStrom.Hodnota);