summaryrefslogtreecommitdiff
path: root/labs/lab10_tree
diff options
context:
space:
mode:
Diffstat (limited to 'labs/lab10_tree')
-rw-r--r--labs/lab10_tree/BinaryNode.java100
-rw-r--r--labs/lab10_tree/BinaryNodeInterface.java15
-rw-r--r--labs/lab10_tree/ShowPath.java293
-rw-r--r--labs/lab10_tree/SimpleQueue.java72
-rw-r--r--labs/lab10_tree/lab10_tree.pdfbin0 -> 61048 bytes
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
Binary files differ
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2026-01-18 08:02:47 +0000