JAVA

Do not edit Tree.java or Node.java. All your code will be done in BinaryTree.java

The task of this lab is to complete six methods to allow for printing off, searching and getting the min and max of a binary tree. The first three are to output the trees nodes in Preorder , Postorder and Inorder. Each of these methods will print the order in which the nodes are visited. The fourth method to implement will search the tree for a node with a specific key. The last 2 methods are to get the min and max of the tree. The search method will print off which branch the algorithm goes down either left or right during each step of the search.

You need to complete

Preorder (Node t)

Postorder(Node t)

Inorder(Node t)

treeSearch(Node t, int key)

treeMin(Node t)

treeMax(Node t)

All code must be commented. The comments must state what each block/method is doing in summary

Node.java

public class Node{

private Node parent;

private Node left;

private Node right;

private int key;

Node(){

parent = null;

right = null;

left = null;

}

Node(int k){

parent = null;

left = null;

right = null;

key = k;

}

public int getKey(){

return key;

}

public void setKey(int k){

key = k;

}

public Node getParent(){

return parent;

}

public void setParent(Node n){

parent = n;

}

public Node getRight(){

return right;

}

public void setRight(Node n){

right = n;

}

public Node getLeft(){

return left;

}

public void setLeft(Node n){

left = n;

}

}

-----------------------------------------------------------------------------------

Tree.java

public class Tree{

private Node root;

Tree(){

root = null;

}

public Node getRoot(){

return root;

}

public void setRoot(Node r){

root = r;

}

public void insert(int key){

Node n = new Node(key);

Node y = null;

Node x = root;

while (x != null){

y = x;

if (n.getKey() <= x.getKey())

{

x = x.getLeft();

}

else{

x = x.getRight();

}

}

n.setParent(y);

if (y == null)

{

setRoot(n);

}

else

{

if (n.getKey() <= y.getKey())

{

y.setLeft(n);

//System.out.println("setting left" + n.getKey());

}

else

{

y.setRight(n);

//System.out.println("setting right" + n.getKey());

}

}

}

}

----------------------------------------------------------------------------------------

BinaryTree.java

* Complete the following

*

* Preorder (Tree t) // This method should output each node it visits

*

* Postorder(Tree t) // This method should output each node it visits

*

* Inorder(Tree t) // This method should output each node it visits

*

* Tree-Search(Tree t,int key) // The search should output the route it took to find the key

*

* treeMin(Tree t) // This method should output the minimum of the tree

*

* treeMax(Tree t) // This method should output the maximum of the tree

*

* Once complete, run the main method and your methods should print the results to the

* screen. I have not included any printing in the skeleton code so you must do so.

*

* When complete you should have the following result.

*/

/* Loading Nodes into Tree First

* Searching Right -> Searching Left -> Searching Right -> Found key ,your search works ;-)

* Post Order

* 6 35 32 14 11 8 5 2 1 49 44 65 42 73 71 65 111 90 40

* Pre Order

* 40 1 2 5 8 6 11 14 32 35 90 65 42 65 44 49 71 73 111

* In Order

* 1 2 5 6 8 11 14 32 35 40 42 44 49 65 65 71 73 90 111

*

* To get top marks you must match the result above.

*/

public class BinaryTree {

public static void Preorder (Node t) {

// fill in

}

public static void Postorder(Node t) {

// fill in

}

public static void Inorder(Node t) {

// fill in

}

public static Node treeSearch(Node t, int key) {

// fill in

return t;

}

public static Node treeMin(Node t) {

// fill in

return t;

}

public static Node treeMax(Node t) {

// fill in

return t;

}

/**

* DO not edit any code below this point

*/

public static void main(String[] args) {

// TODO, add your application code

System.out.println("Loading Nodes into Tree First");

assignmentTree = new Tree();

assignmentTree.insert(40);

assignmentTree.insert(1);

assignmentTree.insert(2);

assignmentTree.insert(5);

assignmentTree.insert(8);

assignmentTree.insert(11);

assignmentTree.insert(14);

assignmentTree.insert(6);

assignmentTree.insert(90);

assignmentTree.insert(65);

assignmentTree.insert(32);

assignmentTree.insert(71);

assignmentTree.insert(35);

assignmentTree.insert(42);

assignmentTree.insert(111);

assignmentTree.insert(65);

assignmentTree.insert(44);

assignmentTree.insert(73);

assignmentTree.insert(49);

Node root = assignmentTree.getRoot();

if(treeSearch(root,71).getKey()==71) {

System.out.println("Found key ,your search works ;-)");

}else {

System.out.println("!!!Warning: Can't find key ,your search does not work yet");

}

if(treeMin(root).getKey()==1) {

System.out.println("Minimum working correctly");

}else {

System.out.println("!!!Warning: treeMin method does not work correctly");

}

if(treeMax(root).getKey()==111) {

System.out.println("Maximum working correctly");

}else {

System.out.println("!!!Warning: treeMax method does not work correctly");

}

System.out.println("Post Order");

Postorder(root);

System.out.print(" ");

System.out.println("Pre Order");

Preorder(root);

System.out.print(" ");

System.out.println("In Order");

Inorder(root);

}

static Tree assignmentTree;

}