# Exercise
1. Construct a binary tree on paper with the following data: Chris, Ann, Charlotte, Steve, Rob, Tori, Fiona, Justine, Michael, Dave
2. Implement the simple binary tree example below in eclipse
3. Replace the data in the binary tree with the names from question 1
4. Implement a pre order and post order traversal method for your tree.
5. Implement the Identify Animal tree. See if you can understand how the game works.
# Simple Binary Tree Example
## Main Class
```java
package stree;
public class STree {
public static void main(String[] args) {
Node root = new Node("Maisie");
root.insert(root, "Kevin");
root.insert(root, "Norma");
root.insert(root, "Jackie");
root.insert(root, "Zak");
root.inOrder(root);
}
}
```
## Node
```java
package stree;
public class Node {
private String data;
private Node left;
private Node right;
Node(String s)
{
this.data = s;
}
public void insert(String s)
{
insert(this, s);
}
public Node insert(Node node, String s)
{
if (node == null)
{
node = new Node(s);
}
else
{
if (s.compareTo(node.data)<0)
{
node.left = insert(node.left, s);
}
else
{
node.right = insert(node.right, s);
}
}
return node;
}
public void inOrder(Node node)
{
if(node.left != null)
{
inOrder(node.left);
}
System.out.println(node.data);
if(node.right != null)
{
inOrder(node.right);
}
}
}
```
# Binary Tree Example: Identify Animal
## Main Class
```java
package identifyanimal;
import java.util.Scanner;
public class IdentifyAnimal {
Scanner scan = new Scanner(System.in);
IdentifyAnimal()
{
Node<String> root = setUpTree();
do{
Node<String> current = root;
while(!current.isLeaf())
{
if (isYes(current.getData()))
{
current = current.getIsYes();
}
else
{
current = current.getIsNo();
}
}
if (isYes(current.getData()+"?"))
{
System.out.println("I was right!");
}
else
{
addAnimal(current);
}
}while(isYes("Play again?"));
}
public void addAnimal(Node<String> current)
{
String guessed = current.getData();
System.out.println("What animal were you thinking of?");
String answer = scan.nextLine();
System.out.println("Give a yes/no question to distinguish a " + guessed + " from a " + answer);
String question = scan.nextLine();
current.setData(question);
if(isYes(answer + ": " + question))
{
current.setIsYes(new Node<String>(answer));
current.setIsNo(new Node<String>(guessed));
}
else
{
current.setIsNo(new Node<String>(answer));
current.setIsYes(new Node<String>(guessed));
}
}
public Node<String> setUpTree()
{
Node root, yes, no;
root = new Node<String>();
root.setData("Is it a Mammal?");
yes = new Node<String>();
yes.setData("Monkey");
no = new Node<String>();
no.setData("Octopus");
root.setIsYes(yes);
root.setIsNo(no);
return root;
}
public boolean isYes(String prompt)
{
String answer;
do{
System.out.println(prompt + " [y or n]");
answer = scan.nextLine().toLowerCase();
}while(!answer.startsWith("y") && !answer.startsWith("n"));
return answer.startsWith("y");
}
public static void main(String[] args) {
// TODO code application logic here
new IdentifyAnimal();
}
}
```
## Tree Node
```java
package identifyanimal;
public class Node <E> {
private E data;
private Node<E> isYes;
private Node<E> isNo;
/**
* @return the data
*/
Node()
{
}
Node(E data)
{
this.data = data;
}
public boolean isLeaf()
{
return (isYes == null) && (isNo == null);
}
public E getData() {
return data;
}
/**
* @param data the data to set
*/
public void setData(E data) {
this.data = data;
}
/**
* @return the left
*/
public Node<E> getIsYes() {
return isYes;
}
/**
* @param isYes the left to set
*/
public void setIsYes(Node<E> isYes) {
this.isYes = isYes;
}
/**
* @return the right
*/
public Node<E> getIsNo() {
return isNo;
}
/**
* @param isNo the right to set
*/
public void setIsNo(Node<E> isNo) {
this.isNo = isNo;
}
}
```