Inital commitHEADmaster

5 files changed, 480 insertions, 0 deletions

diff --git a/labs/lab10_tree/BinaryNode.java b/labs/lab10_tree/BinaryNode.java
new file mode 100644
index 0000000..d498b8e
--- /dev/null
+++ b/labs/lab10_tree/BinaryNode.java
@@ -0,0 +1,100 @@
+
+public class BinaryNode<T> implements BinaryNodeInterface<T>
+{
+	private T data;
+	private BinaryNode<T> left;
+	private BinaryNode<T> right;
+	
+	public BinaryNode(T dataPortion, BinaryNode<T> leftChild, BinaryNode<T> rightChild)
+	{
+		data = dataPortion;
+		left = leftChild;
+		right = rightChild;
+	}
+	
+	public BinaryNode(T dataPortion)
+	{
+		this(dataPortion, null, null);
+	}
+	
+	public BinaryNode()
+	{
+		this(null);
+	}
+	
+	public T getData()
+	{
+		return data;
+	}
+	
+	public void setData(T newData)
+	{
+		data = newData;
+	}
+	
+	public BinaryNodeInterface<T> getLeftChild()
+	{
+		return left;
+	}
+	
+	public BinaryNodeInterface<T> getRightChild()
+	{
+		return right;
+	}
+	
+	public void setLeftChild(BinaryNodeInterface<T> leftChild)
+	{
+		left = (BinaryNode<T>) leftChild;
+	}
+	
+	public void setRightChild(BinaryNodeInterface<T> rightChild)
+	{
+		right = (BinaryNode<T>) rightChild;
+	}
+	
+	public boolean hasLeftChild()
+	{
+		return left != null;
+	}
+	
+	public boolean hasRightChild()
+	{
+		return right != null;
+	}
+	
+	public boolean isLeaf()
+	{
+		return left == null && right == null;
+	}
+	
+	public int getNumberOfNodes()
+	{
+		int leftNumber = 0;
+		int rightNumber = 0;
+		
+		if(left != null)
+			leftNumber = left.getNumberOfNodes();
+		
+		if(right != null)
+			rightNumber = right.getNumberOfNodes();
+		
+		return 1 + leftNumber + rightNumber;
+	}
+	
+	public int getHeight()
+	{
+		return getHeight(this);
+	}
+	
+	private int getHeight(BinaryNode<T> node)
+	{
+		int height = 0;
+		
+		if(node != null)
+		{
+			height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
+		}
+		
+		return height;
+	}
+}
diff --git a/labs/lab10_tree/BinaryNodeInterface.java b/labs/lab10_tree/BinaryNodeInterface.java
new file mode 100644
index 0000000..f3ac7c1
--- /dev/null
+++ b/labs/lab10_tree/BinaryNodeInterface.java
@@ -0,0 +1,15 @@
+
+public interface BinaryNodeInterface<T>
+{
+	public T getData();
+	public void setData(T newData);
+	public BinaryNodeInterface<T> getLeftChild();
+	public BinaryNodeInterface<T> getRightChild();
+	public void setLeftChild(BinaryNodeInterface<T> leftChild);
+	public void setRightChild(BinaryNodeInterface<T> rightChild);
+	public boolean hasLeftChild();
+	public boolean hasRightChild();
+	public boolean isLeaf();
+	public int getNumberOfNodes();
+	public int getHeight();
+}
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;
+	}
+}
diff --git a/labs/lab10_tree/SimpleQueue.java b/labs/lab10_tree/SimpleQueue.java
new file mode 100644
index 0000000..64d7c11
--- /dev/null
+++ b/labs/lab10_tree/SimpleQueue.java
@@ -0,0 +1,72 @@
+
+public class SimpleQueue<T>
+{
+	private Node firstNode;
+	private Node lastNode;
+	
+	public SimpleQueue()
+	{
+		firstNode = null;
+		lastNode = null;
+	}
+	
+	public void enqueue(T newEntry)
+	{
+		Node newNode = new Node(newEntry);
+		
+		if(firstNode == null)
+		{
+			firstNode = newNode;
+			lastNode = newNode;
+		}
+		else
+		{
+			lastNode.next = newNode;
+			lastNode = newNode;
+		}
+	}
+	
+	public T dequeue()
+	{
+		T result = null;
+		
+		if(firstNode != null)
+		{
+			result = firstNode.data;
+			if(lastNode == firstNode)
+			{
+				lastNode = null;
+			}
+			firstNode = firstNode.next;
+		}
+		
+		return result;
+	}
+	
+	public T getFront()
+	{
+		if(firstNode != null)
+		{
+			return firstNode.data;
+		}
+		
+		return null;
+	}
+	
+	private class Node
+	{
+		private T data;
+		private Node next;
+		
+		public Node(T aData, Node nextNode)
+		{
+			data = aData;
+			next = nextNode;
+		}
+		
+		public Node(T aData)
+		{
+			this(aData, null);
+		}
+	}
+}
diff --git a/labs/lab10_tree/lab10_tree.pdf b/labs/lab10_tree/lab10_tree.pdf
new file mode 100644
index 0000000..06dcb2a
--- /dev/null
+++ b/labs/lab10_tree/lab10_tree.pdf