Automata, Languages and Compilers 2017/18 spring

Harjutus: Kahendpuu

1. Kirjuta lõpuni järgnevad klassid:

Node.java

package praks1;
/**
 * 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
	}

	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();
	}

	/**
	 * Soovi korral implementeeri ka meetodid equals ja hashCode
	 */
}

NodeUtils.java

package praks1;

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 = makeIntegerTree("(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();
	}
}

2. Lae oma lahendus Moodle'isse

Selle ülesande jaoks on olemas ka automaatkontrollid. Leiad need siit.