From 89cdf3efb49335e7c07a68a5a64657eeec2288a6 Mon Sep 17 00:00:00 2001 From: Alexander Pickering Date: Mon, 6 Feb 2017 11:41:36 -0500 Subject: Inital commit --- labs/lab10_tree/ShowPath.java | 293 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 293 insertions(+) create mode 100644 labs/lab10_tree/ShowPath.java (limited to 'labs/lab10_tree/ShowPath.java') diff --git a/labs/lab10_tree/ShowPath.java b/labs/lab10_tree/ShowPath.java new file mode 100644 index 0000000..d7ad05f --- /dev/null +++ b/labs/lab10_tree/ShowPath.java @@ -0,0 +1,293 @@ +/*Alexander Pickering + *Doctor Tan + *4-10-15 +*/ + +import java.util.Random; + + +public class ShowPath +{ + public static void main(String[] args) + { + int point = 0; + BinaryNodeInterface root = generateTree(); + + System.out.println("Your string returned from the method getAllPaths() is as follows:"); + String str = getAllPaths(root); + System.out.println(str); + + System.out.println("Your result of using the method getPathTo() for every character is as follows:"); + for(int i = 0; i < 52; i++) + { + if(i < 26) + { + System.out.println("Path to " + (char) ('a' + i) + " " + getPathTo(root, (char) ('a' + i))); + } + else + { + System.out.println("Path to " + (char) ('A' + (i - 26)) + " " + getPathTo(root, (char) ('A' + (i - 26)))); + } + } + + System.out.println(); + + if(!checkGetAllPaths(root, str)) + { + point = point + 5; + } + + System.out.println("Your current point is " + point + "."); + + if(!checkGetPathTo(root)) + { + point = point + 5; + } + + System.out.println("Your total point is " + point + "."); + } + + private static String getAllPaths(final BinaryNodeInterface root) + { + return getAllPathsHelper(root,""); + } + private static String getAllPathsHelper(final BinaryNodeInterface root,String pre) + { + String output = "\n"; + if(root != null) + { + output += root.getData() + " " + pre; + } + if(root.hasLeftChild()) + { + output += getAllPathsHelper(root.getLeftChild(),pre+"0"); + } + if(root.hasRightChild()) + { + output += getAllPathsHelper(root.getRightChild(),pre+"1"); + } + return output; + } + + private static String getPathTo(final BinaryNodeInterface root, char c) + { + return getPathToHelper(root,c,""); + } + private static String getPathToHelper(final BinaryNodeInterface root, char c,String cur) + { + String output = ""; + if(root != null) + { + if(root.getData() == c) + { + return cur; + } + } + if(root.hasLeftChild()) + { + output = getPathToHelper(root.getLeftChild(),c,cur+"0"); + if(output != "") + { + return output; + } + } + if(root.hasRightChild()) + { + output = getPathToHelper(root.getRightChild(),c,cur+"1"); + if(output != "") + { + return output; + } + } + return output; + } + + private static boolean checkGetAllPaths(BinaryNodeInterface root, String str) + { + boolean error = false; + String[] list = str.split("\n"); + + // check for duplicate characters and number of character + + for(int i = 0; i < list.length; i++) + { + if(!list[i].equals("")) + { + char c = list[i].charAt(0); + + for(int j = i + 1; j < list.length; j++) + { + if(!list[j].equals("")) + { + if(c == list[j].charAt(0)) + { + System.out.println("There are more than one character '" + c + "' in your output string."); + error = true; + } + } + } + } + } + + // Check paths + + for(int i = 0; i < list.length; i++) + { + String temp = list[i]; + + if(!temp.equals("")) + { + char c = temp.charAt(0); + String path = temp.substring(2); + BinaryNodeInterface currentNode = root; + + for(int j = 0; j < path.length(); j++) + { + if(path.charAt(j) == '0') + { + currentNode = currentNode.getLeftChild(); + } + else + { + currentNode = currentNode.getRightChild(); + } + } + + char nodeCharacter = currentNode.getData(); + + if(c != nodeCharacter) + { + System.out.println("The line \"" + list[i] + "\" says the path to the character " + c + " is " + path + "."); + System.out.println("But the path " + path + " goes to the node containing the character " + nodeCharacter + "."); + error = true; + } + } + } + + System.out.print("Testing the method getAllPath(): "); + + if(!error) + { + System.out.println("PASS"); + } + else + { + System.out.println("FAIL"); + } + + return error; + } + + private static boolean checkGetPathTo(BinaryNodeInterface root) + { + boolean error = false; + + for(int i = 0; i < 52; i++) + { + char c; + + if(i < 26) + { + c = (char) ('a' + i); + } + else + { + c = (char) ('A' + (i - 26)); + } + + String path = getPathTo(root, c); + BinaryNodeInterface currentNode = root; + + for(int j = 0; j < path.length(); j++) + { + if(path.charAt(j) == '0') + { + currentNode = currentNode.getLeftChild(); + } + else + { + currentNode = currentNode.getRightChild(); + } + } + + char nodeCharacter = currentNode.getData(); + + if(c != nodeCharacter) + { + System.out.println("Your method getPathTo() says the path to the character " + c + " is " + path + "."); + System.out.println("But the path " + path + " goes to the node containing the character " + nodeCharacter + "."); + error = true; + } + } + + System.out.print("Testing the method getPathTo(): "); + + if(!error) + { + System.out.println("PASS"); + } + else + { + System.out.println("FAIL"); + } + + return error; + } + + private static BinaryNodeInterface generateTree() + { + char[] charList = new char[52]; + + for(int i = 0; i < 52; i++) + { + if(i < 26) + { + charList[i] = (char) ('a' + i); + } + else + { + charList[i] = (char) ('A' + (i - 26)); + } + } + + Random rand = new Random(); + rand.setSeed(System.currentTimeMillis()); + + for(int i = 0; i < 1000; i++) + { + int index1 = rand.nextInt(52); + int index2 = rand.nextInt(52); + char temp = charList[index1]; + charList[index1] = charList[index2]; + charList[index2] = temp; + } + + BinaryNodeInterface root = new BinaryNode(charList[0]); + SimpleQueue> queue = new SimpleQueue>(); + queue.enqueue(root); + + for(int i = 1; i < 52; i++) + { + BinaryNodeInterface currentNode = queue.getFront(); + BinaryNodeInterface newNode = new BinaryNode(charList[i]); + + if(!currentNode.hasLeftChild()) + { + currentNode.setLeftChild(newNode); + } + else if(!currentNode.hasRightChild()) + { + currentNode.setRightChild(newNode); + } + else + { + queue.dequeue(); + currentNode = queue.getFront(); + currentNode.setLeftChild(newNode); + } + queue.enqueue(newNode); + } + + return root; + } +} -- cgit v1.2.3-70-g09d2