Search
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.
Node
inorderIterator()
preorderIterator()
postorderIterator()
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.
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~~