Harjutus: Kahendpuu
Kirjuta lõpuni järgnevad klassid
Oma lahenduse kontrollimiseks kasuta repos olevaid teste.
Node
package week1.soojendus;
/**
* Klass on mõeldud kahendpuu tipu esitamiseks. Tüübiparameeter T määrab, millist
* tüüpi väärtust saab tipus hoida. Väärtuse küsimiseks on meetod getValue.
*/
public class Node<T> {
public Node(T value, Node<T> leftChild, Node<T> rightChild) {
// TODO: täienda konstruktorit
// Mida võiks siin teha? Kas midagi on äkki kuskil puudu?
}
public T getValue() {
// TODO: kirjuta erindi viskamise asemele enda kood
throw new UnsupportedOperationException();
}
/**
* Tagastab vasaku alampuu. Selle puudumisel tagastab null-i.
*/
public Node<T> getLeftChild() {
// TODO: kirjuta erindi viskamise asemele enda kood
throw new UnsupportedOperationException();
}
public Node<T> getRightChild() {
// TODO: kirjuta erindi viskamise asemele enda kood
throw new UnsupportedOperationException();
};
/**
* Tagastab true tippude korral, millel pole ühtegi alampuud.
*/
public boolean isLeaf() {
// TODO: kirjuta erindi viskamise asemele enda kood
throw new UnsupportedOperationException();
}
/**
* Meetod peab tagastama true või false vastavalt sellele, kas antud (alam)puus
* leidub näidatud väärtus. Võrdlemine toimub meetodi equals alusel.
*/
public boolean contains(T value) {
// TODO: kirjuta erindi viskamise asemele enda kood
throw new UnsupportedOperationException();
}
/**
* toString peab tagastama puu suluesituse.
*
* Formaat:
* Puu iga tipp on esitatud ümarsulgudes antud kolmikuna, kus esimene
* element on tipu väärtus, teine element on vasak alluv ning kolmas on parem alluv.
* Kui alluv puudub, siis on sõnes vastaval kohal allkriips.
*
* Komponentide vahel peab olema koma ja üks tühik.
*
* Näited:
* kui t on ühetipuline puu tüübiga Node<Integer>,
* mille tipu väärtus on 3, siis t.toString() peab tagastama
* "(3, _, _)"
*
*
* Kui t on selline puu:
* 1
* / \
* / \
* 2 -44
* \
* 3
*
* siis t.toString() peab tagastama
*
* "(1, (2, _, (3, _, _)), (-44, _, _))"
*/
@Override
public String toString() {
// TODO: kirjuta super.toString asemele enda kood
return super.toString();
}
}
NodeUtils
package week1.soojendus;
public class NodeUtils {
/**
* Meetod peab tagastama täisarvu, mis näitab mitu korda esineb antud (alam)puus
* näidatud väärtus. NB! Võrdlemiseks kasutada meetodit equals!
*/
public static <T> int count(Node<T> tree, T value) {
// TODO: kirjuta erindi viskamise asemele enda kood
throw new UnsupportedOperationException();
}
/**
* NB! See on raskem ülesanne. Enne selle üritamist lahenda ja esita teised ülesanded ära!
*
*
* See meetod peab võtma suluesituses sõnena antud puu ja tagastama vastava
* puu andmestruktuuri. Tippudes oleva väärtuse tüüp on Integer.
*
* Sõne formaat on sama, nagu kirjeldatud Node.toString juures.
*
* Näited
*
* Kui käivitada
*
* puu = parseIntegerTree("(1, (2, _, (3, _, _)), (3, _, _))");
*
* siis puu.getLeft().getRight().getValue() peab tagastama 3
* ja puu.getRight().isLeaf() peab tagastama true
* ja NodeUtils.count(puu, 3) peab tagastama 2
*
*/
public static Node<Integer> parseIntegerTree(String s) {
// TODO: kirjuta erindi viskamise asemele enda kood
throw new UnsupportedOperationException();
}
}