Programovanie (2) v Jave
1-INF-166, LS 2016/17

Úvod · Pravidlá · Prednášky · Projekt · Netbeans · Odovzdávanie · Test a skúška
· Vyučujúcich môžete kontaktovať pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· Predvádzanie projektov bude v pondelok 5.6. od 9:00 do 12:00 a v utorok 6.6 od 12:00 do 13:30 (po skúške), oboje v miestnosti M217. Na termín sa prihláste v AIS. Ak robíte vo dvojici, prihlási sa iba jeden člen dvojice.
· Body zo záverečného testu sú na testovači. Poradie príkladov: P1: do šírky, P2: topologické, P3: výnimky, P4: iterátor, P5: testy, P6: strom. Bolo potrebné získať aspoň 20 bodov zo 40.
· Opravný test bude 19.6.2017 od 9:00 v miestnosti M-I. Na termín sa prihláste v AISe.
· Zapisovanie známok a osobné stretnutia ku skúške budú v utorok 13.6. 13:30-14:30 v M163 a v stredu 14.6. 14:00-14:30 v M163.


Cvičenia 21

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

Na týchto cvičeniach sa vrátime k stromom a rekurzii, ale pripomenieme si aj Collections a výnimky. Nižšie nájdete triedu Node reprezentujúcu vrchol binárneho stromu, ktorý obsahuje okrem referencií na ľavý a pravý podstrom aj dátovú premennú typu int. Všimnite si, že po vytvorení vrchola ho už nie je možné existujúcimi metódami meniť.

Úloha 1

Napíšte metódu static Node generate(int n), ktorá vygeneruje najväčší možný strom s týmito vlastnosťami:

  • V koreni má uložené číslo 0.
  • Ak má nejaký vrchol ľavého syna, v tomto synovi je uložené číslo 1.
  • Ak má nejaký vrchol pravého syna, v tomto synovi je uložené číslo 2.
  • Súčet čísel vo vrcholoch na každej ceste z koreňa do niektorého listu je n.

Jednotlivé cesty z koreňa do listov teda zodpovedajú všetkým spôsobom, ako zapísať číslo n ako súčet jednotiek a dvojok, pričom záleží na poradí. Napr. pre n=2 bude strom vyzerať takto:

    0
   / \
  1   2
 /
1

Návod: použite rekurziu, možno budete potrebovať pomocnú rekurzívnu metódu s ďalšími parametrami.

Úloha 2

Napíšte triedu PreorderTreeIterator, ktorá bude implementovať rozhranie Iterator<Node>. Metóda next by mala postupne vracať všetky vrcholy stromu v prefixovom poradí a metóda hasNext by mala testovať, či je ešte nejaký nenavštívený vrchol. Konštruktor triedy dostane koreň stromu. Metódy remove a forEachRemaining nemusíte implementovať.

Návod: V iterátore si vytvorte zásobník vrcholov, ktoré ešte treba spracovať. Použite na to generickú triedu LinkedList, ktorá má metódy push a pop.

Overte, že nasledujúci kód vypíše to isté ako volanie metódy tree.outPrefix():

PreorderTreeIterator it = new PreorderTreeIterator(tree);
while (it.hasNext()) {
    System.out.print(" " + it.next().getData());
} 

Úloha 3

Aj keď trieda Node reprezentuje vrchol stromu, nie je zaručené, že ide skutočne o strom. Napríklad nasledujúcimi dvoma príkazmi môžeme spraviť strom t1, v ktorom je vrchol t0 použitý dvakrát, ako ľavé aj pravé dieťa t1:

Node t0 = new Node(0, null, null);
Node t1 = new Node(1, t0, t0);

Napíšte metódu static boolean uniqueNodes(Node tree), ktorá vráti true, ak v danom strome nie je žiaden vrchol použitý viackrát.

Návod: prejdite strom (rekurzívne alebo iterátorom) a ukladajte si navštívené vrcholy napr. do HashSet. Nakoľko sme v triede Node nepreťažili metódu hashCode, vrcholy budú porovnávané len podľa adresy v pamäti, čo je v tomto prípade žiadané správanie.

Úloha 4

Zmeňte triedu Node tak, aby nebolo možné jeden vrchol použiť ako dieťa viacerých vrcholov, čím sa zabráni prípadom ako v predchádzajúcej úlohe. Pri volaní konštruktoru, ktoré by k takejto situácii viedlo, konštruktor vyhodí výnimku.

Návod: vrchol si pamätá svojho otca, na vhodných miestach sa táto informácia kontroluje a mení.

Trieda Node

class Node {

    private int data;
    private Node left, right;

    public Node(int data_, Node left_, Node right_) {
        data = data_;
        left = left_;
        right = right_;
    }

    public int getData() {
        return data;
    }

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }

    /** Vypise v prefixovom poradi */
    public void outPrefix() {
        if (this != null) {
            System.out.print(" " + data);
            if (this.left != null) {
                left.outPrefix();
            }
            if (this.right != null) {
                right.outPrefix();
            }
        }
    }
}