The goal of you is to find node with value 288 and print the path from root.

Task 1: Please use the BFS to find the path.You should implement the method in binaryTree.java class,and test the method in test.java class

Task 2: Please use the DFS to find the path.You should implement the method in binaryTree.java class,and test the method in test.java class

Test.java

package uninformed_search; /* * AI: uninformed search * * */

import java.util.Random;

public class test { public static void main(String[] args) { /* Creating object of BST */ binaryTree bst = new binaryTree(); System.out.println("Binary Search Tree Test "); int flag=0; Random r = new Random(100); while(flag<20) { bst.insert( r.nextInt(500) ); flag++; } BTreePrinter.printNode(bst.root); System.out.println("Hello from CS351: This is the first programming assignment!"); System.out.println("You will practice the uninformed search algorithm"); System.out.println("The goal of you is to find node with value 288 and" + "print the path from root to it"); System.out.println("Warm up your JAVA ^^"); System.out.println("Task 1: Please use the BFS to find the path." + "You should implement the method in binaryTree.java class," + "and test the method in test.java class"); // test your first method here System.out.println("Task 2: Please use the DFS to find the path." + "You should implement the method in binaryTree.java class," + "and test the method in test.java class"); //// test your second method here }

}

BinaryTree.java

package uninformed_search; /* * AI: uninformed search * * */

public class binaryTree { protected btNode root; /* Constructor */ public binaryTree() { root = null; } /* Function to check if tree is empty */ public boolean isEmpty() { return root == null; } /* Functions to insert data */ public void insert(int data) { root = insert(root, data); } /* Function to insert data recursively */ private btNode insert(btNode node, int data) { if (node == null) node = new btNode(data); else { if (data <= node.getData()) node.left = insert(node.left, data); else node.right = insert(node.right, data); } return node; }

///////////////////////////////////////////CODE BY STUDENTS

}

OTHER FILES:

BTreePrinter.java

import java.util.ArrayList; import java.util.Collections; import java.util.List;

public class BTreePrinter { public static void printNodeInternal(List nodes, int level, int maxLevel) { if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes)) return;

int floor = maxLevel - level; int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0))); int firstSpaces = (int) Math.pow(2, (floor)) - 1; int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;

BTreePrinter.printWhitespaces(firstSpaces);

List newNodes = new ArrayList(); for (btNode node : nodes) { if (node != null) { System.out.print(node.data); newNodes.add(node.left); newNodes.add(node.right); } else { newNodes.add(null); newNodes.add(null); System.out.print(" "); }

BTreePrinter.printWhitespaces(betweenSpaces); } System.out.println("");

for (int i = 1; i <= endgeLines; i++) { for (int j = 0; j < nodes.size(); j++) { BTreePrinter.printWhitespaces(firstSpaces - i); if (nodes.get(j) == null) { BTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1); continue; }

if (nodes.get(j).left != null) System.out.print("/"); else BTreePrinter.printWhitespaces(1);

BTreePrinter.printWhitespaces(i + i - 1);

if (nodes.get(j).right != null) System.out.print("\\"); else BTreePrinter.printWhitespaces(1);

BTreePrinter.printWhitespaces(endgeLines + endgeLines - i); }

System.out.println(""); }

printNodeInternal(newNodes, level + 1, maxLevel); }

private static void printWhitespaces(int count) { for (int i = 0; i < count; i++) System.out.print(" "); }

private static > int maxLevel(btNode node) { if (node == null) return 0;

return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1; }

private static boolean isAllElementsNull(List list) { for (Object object : list) { if (object != null) return false; }

return true; } }

btNode.java

public class btNode {

btNode left, right; int data;

/* Constructor */ public btNode() { left = null; right = null; data = 0; } /* Constructor */ public btNode(int n) { left = null; right = null; data = n; } /* Function to set left node */ public void setLeft(btNode n) { left = n; } /* Function to set right node */ public void setRight(btNode n) { right = n; } /* Function to get left node */ public btNode getLeft() { return left; } /* Function to get right node */ public btNode getRight() { return right; } /* Function to set data to node */ public void setData(int d) { data = d; } /* Function to get data from node */ public int getData() { return data; } }