Inital commitHEADmaster

1 files changed, 293 insertions, 0 deletions

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<Character> 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<Character> root)
+	{
+		return getAllPathsHelper(root,"");
+	}
+	private static String getAllPathsHelper(final BinaryNodeInterface<Character> 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<Character> root, char c)
+	{
+		return getPathToHelper(root,c,"");
+	}
+	private static String getPathToHelper(final BinaryNodeInterface<Character> 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<Character> 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<Character> 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<Character> 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<Character> 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<Character> 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<Character> root = new BinaryNode<Character>(charList[0]);
+		SimpleQueue<BinaryNodeInterface<Character>> queue = new SimpleQueue<BinaryNodeInterface<Character>>();
+		queue.enqueue(root);
+		
+		for(int i = 1; i < 52; i++)
+		{
+			BinaryNodeInterface<Character> currentNode = queue.getFront();
+			BinaryNodeInterface<Character> newNode = new BinaryNode<Character>(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;
+	}
+}