Warning
This page is located in archive.

Třetí domácí úkol

Instance třídy Node reprezentuje kořen binárního stromu obsahujícího celá čísla. Vaším úkolem je naprogramovat metody inorderIterator(), preorderIterator(), postorderIterator(), které vrátí iterátory vracející prvky daného stromu v pořadí inorder, preorder resp. postorder. Jedna instance iterátoru smí v paměti alokovat maximálně konstantní prostor, tzn. paměťové nároky iterátoru nesmí růst s počtem uzlů v daném stromu. Specificky: nesmíte iterátory implementovat tak, že “přesypete” všechny prvky do již existující kolekce a vrátíte její iterátor. Samozřejmě také nesmíte modifikovat iterovaný strom.

Odevzdávaný kód (tzn. třídu Node a třídy iterátorů) uložte do svého repozitáře do adresáře homeworks/Homework3.java.

Průchod stromem typu preorder, inorder a postorder si nastudujte na http://datastructuresnotes.blogspot.cz/2009/02/binary-tree-traversal-preorder-inorder.html , případně http://cs.wikipedia.org/wiki/Strom_(datov%C3%A1_struktura)#Metody_proch.C3.A1zen.C3.AD_stromu

interface CustomIterator {
    boolean hasNext();
    int next();
}
 
class Node {
    final int contents;
    final Node left, right;
    Node parent;
 
    Node(int contents, Node left, Node right) {
        this.contents = contents;
        this.left = left;
        if (left != null) left.parent = this;
        this.right = right;
        if (right != null) right.parent = this;
    }
 
    CustomIterator preorderIterator() { ... }
    CustomIterator inorderIterator() { ... }
    CustomIterator postorderIterator() { ... }
}

~~DISCUSSION:off~~

courses/a7b36omo/en/hw/04/start.txt · Last modified: 2017/11/02 16:55 by sebekji1