1. void ff(int x) { if (x > 0) ff(x–1) ; abc(x); if (x > 0) ff(x–1) ; } Daná funkce ff je volána s parametrem 2: ff(2);. Funkce abc(x) je tedy celkem volána a) 1 krát b) 3 krát c) 5 krát d) 7 krát e) 8 krát Jedno volání funkce reprezentujeme uzlem ve stromu rekurzivního volání, hodnotou uzlu bude hodnota parametru funkce v daném volání. Protože p i každém volání funkce ff se zavolá funkce abc() práv jednou, je po et volání funkce abc() práv 7. Platí varianta d).
2. void ff(int x) { if (x >= 0) ff(x-2) ; abc(x); if (x >= 0) ff(x-2) ; } Daná funkce ff je volána s parametrem 2: ff(2);. Funkce abc(x) je tedy celkem volána a) 1 krát b) 3 krát c) 5 krát d) 7 krát e) 8 krát Jedno volání funkce reprezentujeme uzlem ve stromu rekurzivního volání, hodnotou uzlu bude hodnota parametru funkce v daném volání. Protože p i každém volání funkce ff se zavolá funkce abc() práv jednou, je po et volání funkce abc() práv 7. Platí varianta d).
3. Funkce int ff(int x, int y) { if (x > 0) return ff(x-1,y)+y; return 0; } a) s ítá dv libovolná p irozená ísla b) násobí dv libovolná p irozená ísla c) násobí dv p irozená ísla, pokud je první nezáporné d) vrací nulu za všech okolností e) vrací nulu nebo y podle toho, zda x je kladné nebo ne (Zde došlo k p eklepu, místo slova „p irozená“ má být všude slovo „celá“, nicemén respondenti takto zamaskovanou správnou odpov p esto odhalili.) P i každém návratu z funkce (krom prvního s nulou) je vrácena hodnota p edchozího volání zv tšená o hodnotu y, která se b hem jednotlivých volání nem ní. Celkem je tedy vrácen vícenásobný sou et hodnoty y, takže se jedná o násobení. Jediná podmínka ve funkci zárove také ur uje, že násobení prob hne pouze p i nezáporném prvním parametru, takže správná je varianta c). 4. Funkce int ff(int x, int y) { if (x > 0) return ff(x-1, y)-1; return y; } a) b) c) d) e)
pro kladná x vrací 0, jinak vrací y ode te x od y, pokud x je nezáporné ode te y od x, pokud x je nezáporné vrací –y pro kladné x, jinak vrací y spo te zbytek po celo íselném d lení y%x
První návrat z volání funkce vrátí hodnotu y, která se b hem všech volání nem ní. Každý další návrat ode te od výsledku jedni ku, po et vno ených volání je roven hodnot x. Tudíž výsledkem bude hodnota y–x. Celé to nastane ovšem pouze tehdy, když po áte ní hodnota x bude nezáporná. Tomuto popisu vyhovuje práv varianta b). 5. Funkce int ff(int x, int y) { if (x < y) return ff(x+1,y); return x; } a) bu hned vrátí první parametr nebo jen „do nekone na“ volá sama sebe b) vrátí maximální hodnotu z obou parametr c) vrátí sou et svých parametr
d) vrátí x+1 e) neprovede ani jednu z p edchozích možností Když je x v tším (nebo stejným) z obou parametr , jeho hodnota je vrácena ihned. V opa ném p ípad se v rekurzivním volání jeho hodnota zv tšuje tak dlouho, dokud nedosáhne hodnoty y tedy p vodn v tšího z obou parametr . P i návratu z rekurze již k žádným zm nám nedochází, op t je tedy vrácena hodnota v tšího z obou parametr . Platí možnost b). 6. Funkce int ff(int x, int y) { if (y>0) return ff(x, y-1)+1; return x; } a) b) c) d) e)
se te x a y, je-li y nezáporné pro kladná y vrátí y, jinak vrátí x spo te rozdíl x–y, je-li y nezáporné spo te rozdíl y–x, je-li y nezáporné vrátí hodnotu svého v tšího parametru
Pro y záporné nebo nulové vrátí fukce hodnotu x, Pro kladné y volá sama sebe. Po et volání je roven hodnot y (nebo tento parametr se p i každém volání o jedni ku zmenší) a p i návratu z rekurze se návratová hodnota z v tšuje pkaždé o 1. Po et volání je y, nejvnit n jší volání vrátí hodnotu x, takže návrat z rekurze p i te k x ješt hodnotu y. Správná odpov je a). 7. P i volání rekurzivní funkce f(n) vznikne binární pravidelný ideáln vyvážený strom rekurzivního volání s hloubkou log2(n). Asymptotická složitost funkce f(n) je tedy a) b) c) d) e)
Θ(log2(n)) Θ(n·log2(n)) Ο(n) Ο(log2(n)) Ω(n)
Celkem je známo, že hloubka vyváženého stromu s n uzly je zhruba log2(n). To je i p ípad stromu z našeho zadání. Funkce f p i své rekurzivní innosti navštíví každý uzel tohoto stromu, takže vykoná alespo konst ·n operací. Možná, že má práce v každém uzlu (= p i každém svém volání) ješt více, takže celková doba její innosti je bu úm rná n, nebo je asymptoticky ješt v tší. Práv to je vyjád eno pátou možností e). T etí možnost nep ipouští, že by práce v každém jednom uzlu mohlo být mnoho, zbylé možnosti jsou v bec nesmysl, vata, vycpávka.
8. P i volání rekurzivní funkce f(n) vznikne binární pravidelný ideáln vyvážený strom rekurzivního volání s hloubkou n. Asymptotická složitost funkce f(n) je tedy a) b) c) d) e)
Θ(n) Ο(n) Θ(log2(n)) Ω(2n) Ο(n!)
Když má doty ný strom nap . m uzl , jeho hloubka je úm rná log2(m). Tudíž, když má hloubku n, jeho po et uzl je úm rný 2n. Symbolicky: n ≈ log2(m) 2n ≈ m. Nevíme ovšem, co p i každém rekurzivním volání (= v uzlu stromu rekurze) funkce d lá, t eba tam eší n co složitého, takže celkem její složitost m že být i v tší než Θ(2n). Jiná možnost než d) prost není, všechny ostatní jsou jsou pouhé „k oví“ bez jakéhokoli nároku (a úmyslu!) na podobnost s realitou. 9. Vypo t te, kolik celkem asu zabere jedno zavolání funkce rekur(4); za p edpokladu, že provedení p ikazu xyz(); trvá vždy jednu milisekundu a že dobu trvání všech ostatních akcí zanedbáme. void rekur(int x) { if (x < 1) return; rekur(x-1); xyz(); rekur(x-1); }
Strom rekurzivního volání funkce rekur je binární vyvážený strom. p i volání rekur(4) bude mít tento strom hloubku 5, uzly posledního (=nejhlubšího) „patra“ však budou odpovídat pouze provedení ádku if (x < 1) return; a p íkaz xyz() se tu neprovede. V každém uzlu stromu rekurzivního volání do hloubky 4 bude tedy jednou proveden p íkaz xyz(). Po et t chto uzl je 1 + 2 + 4 + 8 = 15. Stejn krát bude proveden i p íkaz
xyz().
10. Ur ete, jakou hodnotu vypíše program po vykonání p íkazu print(rekur(4));, když rekurzivní funkce rekur() je definována takto: int rekur(int x) { if (x < 1) return 2; return (rekur(x-1)+rekur(x-1)); }
Nedokážete-li výsledek p ímo zapsat jako p irozené íslo, sta í jednoduchý výraz pro jeho výpo et.
Rekurzivní volání rekur(x-1)+rekur(x-1) m žeme zapsat jako 2*rekur(x-1) a potom máme:
rekur(4) = 2*rekur(3) = 2*2*rekur(2) = 2*2*2*rekur(1) = = 2*2*2*2*rekur(0) = 2*2*2*2*2 = 32.
11. Obecný binární strom a) b) c) d) e)
má vždy více list než vnit ních uzl má vždy více list než vnit ních uzl , jen pokud je pravidelný má vždy mén list než vnit ních uzl m že mít více ko en m že mít mnoho list a žádné vnit ní uzly
Má-li strom alespo dva uzly, má i ko en, který je v takovém p ípad vnit ním uzlem. Když má strom jen jeden uzel, je to ko en, a i kdybychom jej deklarovali jako list, byl by to list jediný, což lze jen t žko ozna it jako „mnoho list “, takže možnst e) nep ichází v úvahu. Možnost d) je z ejmý nesmysl. Obecný binární strom m že mít jen list jediný a mnoho vnit ních uzl (= jedna „holá v tev“), odpadá možnost a). Vyvážený strom se t emi uzly vyvrací možnost c), takže zbývá jediná korektní možnost b). V pravidelném binárním stromu (s alespo 3 uzly) platí, že po et list je o 1 v tší než po et vnit ních uzl . 12. Binární strom má n uzl . Ší ka jednoho „patra“ (tj. po et uzl se stejnou hloubkou) je tedy a) b) c) d) e)
nejvýše log(n) nejvýše n/2 alespo log(n) alespo n/2 nejvýše n
Binární strom nemusí být nutn pravidelný, m že to být jen jediná „dlouhá v tev“, takže nejmenší možná ší e je 1, možnost t etí a tvrtá odpadají. „Co nejširší patro“ odpovídá stromu „co nejvíce do ší ky roztaženému“, na což se zdá být ideáln vyvážený pravidelný strom alespo kandidátem. V n m je nejspodn jší „patro“ list . P i n uzlech ve stromu je v onom „pat e“ (n+1)/2 uzl , možnost první a druhá odpadají také. 13. Daný binární strom má t i listy. Tudíž a) má nejvýše dva vnit ní uzly b) po et vnit ních uzl není omezen
c) všechny listy mají stejnou hloubku d) všechny listy nemohou mít stejnou hloubku e) strom je pravidelný Binární strom nemusí být nutn pravidelný, m že mít dlouhatánské „lineární“ nev tvící se v tve (nev tvící se v tve, hmm...) s jediným uzlem na konci. Sta í tady t i takové v tve (jedan doprava z ko ene a dv z jeho levého potomka) a jejich délka m že být zcela libovolná. Takový strom není pravidelný (ne paté možnosti), jeho t i listy mohou a nemusí ležet stejn hluboko (ne t etí a tvrté možnosti) a zbytek již byl e en. 14. Binární strom má hloubku 2 (hloubka ko ene je 0). Po et list je a) b) c) d)
minimáln minimáln minimáln minimáln
0 a maximáln 1 a maximáln 1 a maximáln 2 a maximáln
2 3 4 4
Minimální a maximální po et list je vyzna en na obrázku s nazna enými hloubkami, platí varianta c).
15. Binární strom má 2 vnit ní uzly. Má tedy e) f) g) h)
minimáln minimáln minimáln minimáln
0 a maximáln 1 a maximáln 1 a maximáln 2 a maximáln
2 listy 3 listy 4 listy 4 listy
Minimální a maximální po et list je vyzna en na obrázku, platí varianta b).
16. Algoritmus A provádí pr chod v po adí inorder binárním vyváženým stromem s n uzly a v každém uzlu provádí navíc další (nám neznámou) akci, jejíž složitost je Θ(n2). Celková asymptotická složitost algoritmu A je tedy a) b) c) d) e)
Θ(n) Θ(n2) Θ(n3) Θ(n2+log2(n)) Θ(n2 · log2(n))
P i pr chodu stromem v po adí pre/in/postorder má režie na p íchod a odchod do/z uzlu složitost úm rnou konstant . V každém uzlu – jichž je n – se navíc podle zadání provedou operace, jejichž po et je úm rný n2. Celkem je tedy na zpracování úkolu zapot ebí as úm rný výrazu n · (konstanta + n2) = n · konstanta + n3 ∈ Θ(n3). Platí varianta c). 17. Algoritmus A provede jeden pr chod binárním stromem s hloubkou n. P i zpracování celého k-tého „patra“ (=všech uzl s hloubkou k) provede k+n operací. Opera ní (=asymptotická) složitost algoritmu A je tedy a) b) c) d) e)
Θ(k+n) Θ( (k+n)·n ) Θ(k2+n) Θ(n2) Θ(n3)
Celkem je provedený po et operací p i zpracování všech uzl roven (1+n) + (2+n) + (3+n) + ... + (n+n) = n · ((1+n) + (n+n))/2 = n · (1+3n)/2 = 3n2/2 +n/2 ∈ Θ(n2) Povážíme-li navíc ješt režii na p esun od jednoho „patra“ stromu k následujícímu patru, která m že mít složitost nanejvýš Θ(n), p ipošteme k výsledku ješt len Θ(konst·n·n), který ovšem na složitosti Θ(n2) nic nem ní. Platí varianta d). 18. Obsah uzl daného stromu vypíšeme v po adí postorder. Vznikne posloupnost a) b) c) d)
GFEDCBA FCGDBEA GCFAEBD DEBFGCA
P ímo z definice po adí postorder plyne, že je nutno volit odpov
d).
19. Obsah uzl daného stromu vypíšeme v po adí preorder. Vznikne posloupnost a) b) c) d)
ABCDEFGH DBEAFCG ABDECFG DEFGBCA
P ímo z definice po adí postorder plyne, že je nutno volit odpov
c).
20. Výpis prvk binárního stromu v po adí postorder provede následující: a) vypíše prvky v opa ném po adí, než v jakém byly do stromu vloženy b) pro každý podstrom vypíše nejprve ko en, pak obsah jeho levého a pak pravého podstromu c) pro každý podstrom vypíše nejprve obsah levého podstromu ko ene, pak obsah pravého podstromu a pak ko en d) pro každý podstrom vypíše nejprve obsah pravého podstromu ko ene, pak obsah levého podstromu a pak ko en e) vypíše prvky stromu v uspo ádání zprava doleva Definice praví, že se jedná o variantu c). 21. Výpis prvk binárního stromu v po adí preorder provede následující: a) vypíše prvky stromu ve stejném po adí, v jakém byly do stromu vloženy b) vypíše prvky stromu v uspo ádání zleva doprava c) pro každý podstrom vypíše nejprve ko en, pak obsah jeho levého a pak pravého podstromu d) pro každý podstrom vypíše nejprve obsah levého podstromu ko ene, pak obsah pravého podstromu a pak ko en e) vypíše prvky stromu se azené vzestupn podle velikosti Definice praví, že se jedná o variantu c). 22. Navrhn te algoritmus, který spojí dva BVS: A a B. Spojení prob hne tak, že všechny uzly z B budou p esunuty do A na pat i né místo, p i emž se nebudou vytvá et žádné nové uzly ani se nebudou žádné uzly mazat. P esun prob hne jen manipulací s ukazateli. P edpokládejte, že v každém uzlu v A i v B je k dispozici ukazatel na rodi ovský uzel. Budeme procházet stromem B a ukazatel na každý uzel X, který najdeme, p edáme funkci moveToA(node RootA, node X). Volání funkce moveToA(rootA, X) ud lá následující: -- najde místo ve stromu A pro uzel X (stejn jako to d lá std. operace Insert), tj. najde v A uzel R, který bude rodi em X v A. -- p esune uzel X ze stromu B do stromu A pod uzel R pouze manipulací s ukazateli. P esunutím uzlu X z B do A ovšem ztratí strom B veškerou referenci na tento uzel a tím také na jeho p ípadné potomky v B. Aby tedy nedošlo ke ztrát informace, musíme uzel X vybírat vždy tak, aby sám nem l žádné potomky. To lze našt stí zajistit snadno, protože procházení stromu v po adí postorder má práv tu vlastnost, že zpracovává strom po ínaje listy. Zpracování list v naší úloze ale znamená odstran ní list . Máme tedy po adím postorder zaru eno (malujte si obrázek!),
že kdykoli p i procházení stromu B v tomto po adí za neme zpracovávat uzel, nebude mít již tento uzel žádné potomky. Celý algoritmus pak vypadá nap íklad takto: void presunVse(node rootA, node nodeB) { // nodeB je aktuální uzel v B // presunVse má vlastnosti procházení postorder: if (nodeB == NULL) return; presunVse(rootA, nodeB.left); presunVse(rootA, nodeB.right); moveToA(rootA, nodeB); } node moveToA(node rootA, node X); { /* 1. najdi místo ve stromu A pro klí uzel s hodnotou klí e rootB.key stejn jako v operaci Insert. Rodi em nového uzlu a je uzel R. 2. prove p esun uzlu X z B do A: */ // p idej X do A if (R.key < X.key) R.right = X; else R.left = X. // vyjmi X z B if (X.rodic.left == X) X.rodic.left = NULL; else X.rodic.right = NULL; // a nastav správn X.parent = R;
rodi e X
} Uvedené ešení nepo ítá s možností, že by strom A byl na za átku prázdný, vhodné dopln ní algoritmu ponechávám zájemc m jako jednoduché cvi ení. 23. Projd te binárním stromem a vypište obsah jeho uzl v po adí preorder bez použití rekurze, zato s využitím vlastního zásobníku. Po adí preorder znamená, že nejprve zpracujeme aktuální uzel a potom jeho levý a pravý podstrom. Budeme tedy v cyklu zpracovávat vždy aktuální vrchol, referenci na n jž vždy odebereme z vrcholu zásobníku (-- odkud jinud také!) a hned poté si do zásobníku uložíme informaci o tom, co je ješt t eba zpracovat, tedy ukazatele na levého a pravého potomka aktuálního uzlu. Celý základní cyklus tedy bude vypadat takto:
while (stack.empty == false) { currNode = stack.pop(); print(currNode.key); if (currNode.left != null) stack.push(currNode.right); if (currNode.right != null) stack.push(currNode.left); } P edtím, než tento cyklus spustíme, musíme ovšem inicializovat zásobník a a vložit do n j ko en stromu: If (ko enStromu == null) return; stack.init(); stack.push(ko en.Stromu); základní cyklus uvedený výše; To je celé, vstupem algoritmu je ukazatel na ko en stromu, výstupem hledaná posloupnost, pro zásobník je nutno pro jistotu alokovat tolik místa, kolik m že nejvíc mít strom uzl . 24. Aritmetický výraz obsahující celá ísla, závorky a operace +,−,*,/ (celo íselné d lení) m že být reprezentován jako pravidelný binární strom. Popište, jak takový strom obecn vypadá, navrhn te implementaci uzlu a napište funkci, jejímž vstupem bude ukazatel na ko en stromu a výstupem hodnota odpovídajícího aritmetického výrazu. (Body = 1 popis + 1 uzel + 3 funkce) Vnit ní uzly stromu budou p edstavovat operace, listy pak jednotlivá ísla. Nap íklad výraz 6+(4-3+5)*(9-7) lze reprezentovat následujícím stromem:
(Obrázek je bitmapa, nejprve olíznutá z obrazovky s powerpointem, v n mž byl obrázek vytvo en, pak upravena v paintShopu a posleze vložená do wordu jako rastrový obrázek. Produkty firmy mikro**t si totiž neumí mezi sebou navzájem p edávat svou vektorovou grafiku, hm…)
Hodnotou každého listu je íslo v listu uložené, hodnotou vnit ního uzlu je
.
Hodnota ko ene pak p edstavuje hodnotu celého výrazu. Na dalším obrázku jsou hodnoty u jednotlivých uzl p ipsány:
V implementaci uzlu tedy po ebujeme -- typ - složka, která udává, zda jde o vnit ní uzel nebo list -- op - složka udávající operaci (nap . znak) -- val - složka pro íslo, je-li uzel listem, jinak hodnota uzlu -- left a right – potomci uzlu (též je možno první složku vypustit a indikovat nap . prázdným znakem ve druhé složce, že jde o list, apod…)
Celá vyhodnocovací funkce (p edpokládající, že strom je neprázdný) pak m že vypadat takto: int hodnota(node n) { if (n.typ == list) return n.val; switch (n.typ) { case ‘+’: return (hodnota(n.left) case ‘-’: return (hodnota(n.left) case ‘*’: return (hodnota(n.left) case ‘/’: return (hodnota(n.left) } }
+ * /
hodnota(n.right)); hodnota(n.right)); hodnota(n.right)); hodnota(n.right));
break; break; break; break;
(mimochodem, tím že kompilátor zajistí, že se ve výrazu hodnota(n.left) + hodnota(n.right) a dalších nejprve spo tou hodnoty funkcí a pak teprve se provede s ítání (od ítání,.. atd.), zajistí vlastn také pr chod oním stromem v po adí postorder...)
25. Deklarujte uzel binárního stromu, který bude obsahovat celo íselné složky výška a hloubka. Ve složce hloubka bude uložena hloubka daného uzlu ve stromu, ve složce výška jeho výška. Výška uzlu X je definována jako vzdálenost od jeho nejvzdálen jšího potomka (= po et hran mezi uzlem X a jeho nejvzdálen jším potomkem). Napište funkci, která každému uzlu ve stromu p i adí korektn hodnotu jeho hloubky a výšky. --------------------
P i po ítaní hloubky sta í každému potomku uzlu X p i adit o 1 v tší hloubku než má uzel X. Sama rekurzivní procedura mluví za dlouhé výklady: void setHloubka(node x, int depth) { if (x == null) return; x.hloubka = depth; setHloubka(x.left, depth+1); setHloubka(x.right,depth+1); } P i azení hloubky každému uzlu ve stromu pak provedeme p íkazem setHloubka(ourTree.root, 0); Všimn te si, že hloubky se uzl m p i azují – celkem logicky – v po adí preorder. P i p i azování výšky uzlu X musíme naopak znát výšku jeho potomk , takže se nabízí zpracování v po adí postorder: void setVyska(node x) { int vyskaL = -1; // nejprve pripad, ze uzel nema L potomky. int vyskaR = -1; // dtto if (x.left != null) { setVyska(x.left); vyskaL = x.left.vyska; } if (x.right != null) { setVyska(x.right); vyskaR = x.right.vyska; } x.vyska = max(vyskaL, vyskaR) + 1;
} P i azení výšky každému uzlu ve stromu pak provedeme p íkazem if (ourTree.root != null) setVyska(ourTree.root); Celý proces s výškou lze zachytit ješt úsporn ji: int setVyska(node x) { if (x == null) return -1; x.vyska = 1+ max(setVyska(x.left), setVyska(x.right)); return x.vyska; } P i azení výšky každému uzlu ve stromu pak provedeme nap . p íkazem zbytecnaProm = setVyska(ourTee.root); 26. Uzel binárního binárního vyhledávacího stromu obsahuje t i složky: Klí a ukazatele na pravého a levého potomka. Navrhn te rekurzívní funkci (vracející bool), která porovná, zda má dvojice strom stejnou strukturu. Dva stromy považujeme za strukturn stejné, pokud se dají nakreslit tak, že po položení na sebe pozorovateli splývají.
Z uvedeného popisu by m l být z ejmý následující rekurzvní vztah: Dva binární stromy (ani nemusí být vyhledávací) A a B jsou strukturn stejné, pokud a) jsou bu oba prázdné b) levý podstrom ko ene A je strukturn stejný jako levý podstrom ko ene B a zárove také pravý podstrom ko ene A je strukturn stejný jako pravý podstrom ko ene B. Toto zjišt ní již snadno p epíšeme do programovacího jazyka (zde jen pseudokódu): boolean stejnaStruktura(node root1, node root2) { if ((root1 == null) && (root2 == null)) return true; if ((root1 == null) || (root2 == null)) return false; return (stejnaStruktura(root1.left, root2.left) && stejnaStruktura(root1.right, root2.right)); }
27. Napište funkci, která vytvo í kopii obecného ko enového stromu. Ten je reprezentován takto: Uzel X stromu obsahuje dv složky: hodnota a potomci. Složka potomci je ukazatel na z et zený seznam obsahující jednotlivé ukazatele na potomky uzlu X. Nemá-li uzel X žádné potomky, složka potomci ukazuje na null. Každý prvek seznamu potomk obsahuje jen ukazatel na potomka X a ukazatel na další prvek v seznamu potomk . Strom je obecný, potomci libovolného uzlu nejsou nijak uspo ádáni podle svých hodnot.
Uzel X:
hodnota Hodnota potomci
12
...
Seznam potomk X:
Potomci uzlu X:
88
13
...
42
...
...
Jen tak cvi n si nap ed ekn me, jak by probíhalo kopírování binárního stromu. Nejprve bychom vytvo ili kopii ko ene, potom kopii levého a pravého podstromu ko ene a pak bychom tyto kopie podstrom p ipojili ke kopii ko ene. Kopie podstrom bychom ovšem vyrobili stejnou rekurzivní procedurou. Zachyceno pseudokódem: node kopieBinStromu (node root) { if (root == null) return null; new root2 = kopieUzlu(root);
}
root2.left = kopieBinStromu(root.left); root2.right = kopieBinStromu(root.right); return root2;
V p ípad obecného ko enového stromu je situace zcela obdobná. Jediný rozdíl je v tom, že nemáme v uzlu pevnou strukturu pro levého a pravého následníka ale jen ukazatel na seznam obsahující ukazatele na potomky. A jeho struktura uzlu nap . takováto { int hodnota; seznamPotomku potomci; } A struktura prvku seznamu ukazatel na potomky: { seznamPotomku next; node potomek} Zachyceno pseudokódem: node kopieBinStromu (node root) { if (root == null) return null; new rootKopie = kopieUzlu(root); potomky
// kopírujme pouze uzel, // nikoli seznam ukazatel
na
// p ipravme si seznam zkopírovaných potomk , // který nakonec p ipojíme k root2 seznamPotomku potomciRootKopie = null; seznamPotomku potomciRoot = root.potomci while (potomciRoot != null) { node kopiePodstromu = kopieBinStromu(potomciRoot.potomek); // rekurze seznamPotomku kopieUkazatele = new(seznamPotomku); kopieUkazatele.potomek = kopiePodstromu; zaradNaKonecSeznamu(PotomciRootKopie, kopieUkazatele); potomciRoot = potomciRoot.next; } // te seznam ukazatel na zkopírované podstromy p ipojíme k rootKopie rootKopie.potomci = potomciRootKopie; }
return root2; // je hotovo
28. Uzel binárního vyhledávacího stromu obsahuje ty i složky: Klí , celo íselnou hodnotu count a ukazatele na pravého a levého potomka. Navrhn te nerekurzívní proceduru, která naplní zadané pole hist[0,maxInt] po tem výskyt hodnot v prom nné count (histogram hodnot uložených v count).
Není v zásad zapot ebí nic jiného, než projít stromem a v každém uzlu provést operaci: hist[aktUzel.count]++; Pr chod stromem zvolíme v po adí preorder, protože to se nejsnáze implementuje nerekurzivn . Na zásobník sta í po zpracování aktuálního uzlu ukládat pouze pravého a levého potomka (pokud existují). Celý pseudokód by pak mohl vypadat asi takto: void histogram(node root, int [ ] hist) { NaplnPoleNulami(hist); if (root == null) return; stack.init; stack.push(root); while (stack.empty() == false) { aktUzel = stack.pop(); hist[aktUzel.count]++; if (aktUzel.right != null) stack.push(aktUzel.right); if (aktUzel.left != null) stack.push(aktUzel.left); } } 29. Je dána struktura popisující uzel binárního vyhledávacího stromu takto Struct node { valType val; node * left, right; int count; } navrhn te nerekurzívní proceduru, která do prom nné count v každém uzlu zapíše po et vnit ních uzl v podstromu, jehož ko enem je tento uzel (v etn tohoto uzlu, pokud sám není listem). Musíme volit pr chod v po adí postorder, protože po et vnit ních uzl v daném stromu zjistíme tak, že se teme po et vnit ních uzl v levém podstromu a pravém podstromu ko ene a nakonec p i teme jedni ku za samotný ko en. Nepot ebujeme tedy nic jiného než procházet stromem a p ed definitivním opušt ním uzlu se íst po et vnit ních uzl v jeho levém a pravém podstromu, pokud existují. Pokud neexistuje ani jeden, pak je uzel listem a registrujeme v n m nulu. Na zásobník budeme s každým uzlem, který ješt budeme zpracovávat, ukládat také po et návšt v, které jsme již v n m vykonali. Po t etí návšt ve již uzel ze zásobníku definitivn vyjmeme – v implementaci to znamená, že již jej zp t do zásobníku nevložíme. void pocetVnitrUzlu(node root) { if root == null return stack.init(); stack.push(root, 0); while (stack.empty() == false) { (aktUzel, navstev) = stack.pop(); // pokud je uzel listem:
if (aktUzel.left == null) && (aktUzel.right == null)) aktUzel.count = 0; // pokud uzel neni listem: else { if(navstev == 0) { stack.push(aktUzel, 1); // uz jsme v akt uzlu byli jednou if (aktUzel.left != null) stack.push(aktUzel.left, 0); } if(navstev == 1) { stack.push(aktUzel, 2); // uz jsme v akt uzlu byli dvakrat if (aktUzel.right != null) stack.push(aktUzel.right, 0); } if(navstev == 2) { // ted jsme v akt uzlu potreti aktUzel.count = 1; // akt uzel je vnitrnim uzlem stromu if (aktUzel.left != null) aktUzel.count += aktUzel.left.count; if (aktUzel.right != null) aktUzel.count += aktUzel.right.count; } } } // end of while } 30. Je dána struktura popisující uzel binárního vyhledávacího stromu takto Struct node { valType val; node * left, right; int count; } navrhn te nerekurzívní proceduru, která do prom nné count v každém uzlu zapíše po et list v podstromu, jehož ko enem je tento uzel (v etn tohoto uzlu, je-li sám listem). Musíme volit pr chod v po adí postorder, protože po et list v daném stromu zjistíme tak, že se teme po et list v levém podstromu a pravém podstromu ko ene. Nepot ebujeme tedy nic jiného než procházet stromem a p ed definitivním opušt ním uzlu se íst po et list v jeho levém a pravém podstromu, pokud existují. Pokud neexistuje ani jeden, pak je uzel listem a registrujeme v n m jedni ku. Na zásobník budeme s každým uzlem, který ješt budeme zpracovávat, ukládat také po et návšt v, které jsme již v n m vykonali. Po t etí návšt ve již uzel ze zásobníku definitivn vyjmeme – v implementaci to znamená, že již jej zp t do zásobníku nevložíme. void pocetListu(node root) { if root == null return stack.init();
stack.push(root, 0); while (stack.empty() == false) { (aktUzel, navstev) = stack.pop(); // pokud je uzel listem: if (aktUzel.left == null) && (aktUzel.right == null)) aktUzel.count = 1; // pokud uzel neni listem: else { if(navstev == 0) { stack.push(aktUzel, 1); // uz jsme v akt uzlu byli jednou if (aktUzel.left != null) stack.push(aktUzel.left, 0); } if(navstev == 1) { stack.push(aktUzel, 2); // uz jsme v akt uzlu byli dvakrat if (aktUzel.right != null) stack.push(aktUzel.right, 0); } if(navstev == 2) { // ted jsme v akt uzlu potreti aktUzel.count = 0; if (aktUzel.left != null) aktUzel.count += aktUzel.left.count; if (aktUzel.right != null) aktUzel.count += aktUzel.right.count; } } } // end of while } 31. Napište rekurzívn a nerekurzívn funkci, která projde n-ární strom (každý uzel m že mít až n podstrom . Odkazy na podstromy jsou uloženy v každém uzlu v poli délky n). Datová struktura uzlu (1 bod). Rekurzívní verze (2b), nerekurzívní (3b.) uzel obsahuje dv složky { /*napr.*/ int value; potomci [n]; } // rekurzivne ve variante "preorder": void projdi(node root) { if (root == null) return; nejakaAkce(root); // tady by se provedla patricna akce for (i = 0; i < n; i++) projdi(potomci[i]); // nerekurzivne
// pouzijeme opet postup "preorder" protoze se pri nem nemusime na zasobnik // ukladat zadne dodatecne informace o navstevach uzlu void projdiNonRec(node root) { if (root== null) return; stack.init(); stack.push(root); while (stack.empty() == false) { aktUzel = stack.pop(); // aktualni uzel definitivne ze zasbniku mizi nejakaAkce(aktUzel); // tady by se provedla patricna akce // na zasobnik se ulozi potomci for (i = 0; i < n; i++) stack.push(aktUzel.potomci[i]); } }
