added Tree data structure

2 files changed, 207 insertions, 0 deletions

diff --git a/Tree.java b/Tree.java
new file mode 100644
index 0000000..c71051c
--- /dev/null
+++ b/Tree.java
@@ -0,0 +1,144 @@
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Queue;
+import java.util.Stack;
+import java.util.LinkedList;
+import java.util.Iterator;
+
+public abstract class Tree<T extends Comparable<T>> {
+    
+    TreeNode<T> root;
+
+    public void findAllLevels() {
+        throw new UnsupportedOperationException();
+    }
+
+    // how to add to a tree? it normally depends on the context...
+    abstract public boolean add(T element);
+
+    abstract public boolean remove(T element);
+
+    //How to search?? Use BFS or DFS
+    public boolean contains(T element) {
+        return iterativeBreadthFirstContains(element);
+    }
+
+    public boolean iterativeBreadthFirstContains(T element) {
+        if (root == null) {
+            return false;
+        }
+        Queue<TreeNode<T>> q = new LinkedList<TreeNode<T>>();
+        q.add(root);
+        while (q.isEmpty() == false) {
+            TreeNode<T> temp = q.remove();
+            if (temp.obj.compareTo(element) == 0) {
+                return true;
+            }
+            for (TreeNode<T> child : temp.getAllChildren()) {
+                q.add(child);
+            }
+        }
+        return false;
+    }
+
+    public boolean iterativeDepthFirstContains(T element) {
+        if (root == null) {
+            return false;
+        }
+        Stack<TreeNode<T>> stack = new Stack<>();
+        HashSet<TreeNode<T>> seen = new HashSet<>();
+        stack.push(root);
+        while (stack.isEmpty() == false) {
+            TreeNode<T> temp = stack.peek();
+            if (temp.obj.compareTo(element) == 0) {
+                return true;
+            }
+            seen.add(temp);
+            boolean found = false;
+            Iterator<TreeNode<T>> iterator = temp.getAllChildren().iterator();
+            TreeNode<T> next = null;
+            while (!found && iterator.hasNext()) {
+                next = iterator.next();
+                if (!seen.contains(next)) {
+                    found = true;
+                }
+            }
+            if (!found) {
+                stack.pop();
+            } else {
+                stack.push(next);
+            }
+        }
+        return false;
+    }
+
+    public boolean recursiveDepthFirstContains(T element) {
+        return depthFirstRecurse(element, root);
+    }
+
+    private boolean depthFirstRecurse(T e, TreeNode<T> n) {
+        if (n == null) {
+            return false;
+        }
+        if (n.obj.compareTo(e) == 0) {
+            return true;
+        }
+        for (TreeNode<T> child : n.getAllChildren()) {
+            if (depthFirstRecurse(e, child)) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    public static class TreeNode<T> {
+        T obj;
+        ArrayList<TreeNode<T>> children;
+
+        TreeNode(T o) {
+            obj = o;
+            children = new ArrayList<>();
+        }
+
+        boolean add(TreeNode<T> tr) {
+            return children.add(tr);
+        }
+
+        ArrayList<TreeNode<T>> getAllChildren() {
+            return children;
+        }
+
+        public int height() {
+            throw new UnsupportedOperationException();
+        }
+    }
+
+    public class BreadthFirstIterator implements Iterator<T>, Iterable<T> {
+
+        Queue<TreeNode<T>> q = new LinkedList<TreeNode<T>>();
+        
+        BreadthFirstIterator() {
+            q.add(root);
+        }
+
+        @Override
+        public boolean hasNext() {
+            if (root == null) {
+                return false;
+            }
+            return !q.isEmpty();
+        }
+
+        public T next() {
+            TreeNode<T> temp = q.remove();
+            for (TreeNode<T> child : temp.getAllChildren()) {
+                q.add(child);
+            }
+            return temp.obj;
+        }
+
+        public Iterator<T> iterator() {
+            return new BreadthFirstIterator();
+        }
+    }
+}
\ No newline at end of file
diff --git a/TreeExample.java b/TreeExample.java
new file mode 100644
index 0000000..ab6eebe
--- /dev/null
+++ b/TreeExample.java
@@ -0,0 +1,63 @@
+
+
+public class TreeExample<T extends Comparable<T>> extends Tree<T> {
+    
+    // for real implementations this would be much more complicated
+    public boolean add(T o) {
+        root.add(new TreeNode<T>(o));
+        return true;
+    }
+
+    public boolean remove(T o) {
+        throw new UnsupportedOperationException();
+    }
+
+    public static void main(String[] args) {
+        Tree<String> t = new TreeExample<>();
+        t.root=new Tree.TreeNode<String>("ARSENAL");
+
+        t.root.add(new Tree.TreeNode<String>("Forty"));
+        t.root.add(new Tree.TreeNode<String>("Nine"));
+        t.root.add(new Tree.TreeNode<String>("Undefeated"));
+
+        t.root.children.get(0).add(new Tree.TreeNode<String>("I"));
+        t.root.children.get(0).add(new Tree.TreeNode<String>("Bet"));
+        t.root.children.get(1).add(new Tree.TreeNode<String>("You"));
+        t.root.children.get(2).add(new Tree.TreeNode<String>("Are"));
+        t.root.children.get(2).add(new Tree.TreeNode<String>("Sick"));
+        t.root.children.get(2).add(new Tree.TreeNode<String>("Of"));
+        t.root.children.get(2).add(new Tree.TreeNode<String>("Arsenal"));
+        t.root.children.get(2).children.get(1).add(new Tree.TreeNode<String>("Examples"));
+
+        String[] testy={"Arsenal","Totts"};
+        System.out.println("iterative breadth first search:");
+        for (String s : testy) {
+            if (t.iterativeBreadthFirstContains(s)) {
+                System.out.println("Tree contains " + s);
+            } else {
+                System.out.println("Tree doesn't contain " + s);
+            }
+        }
+        System.out.println("recursive depth first search:");
+        for (String s : testy) {
+            if (t.recursiveDepthFirstContains(s)) {
+                System.out.println("Tree contains " + s);
+            } else {
+                System.out.println("Tree doesn't contain " + s);
+            }
+        }
+        System.out.println("iterative breadth first search:");
+        for (String s : testy) {
+            if (t.iterativeDepthFirstContains(s)) {
+                System.out.println("Tree contains " + s);
+            } else {
+                System.out.println("Tree doesn't contain " + s);
+            }
+        }
+
+        System.out.println("\nbreadth first iteration");
+        for (String s : t.new BreadthFirstIterator()) {
+            System.out.println(s);
+        }
+    }
+}