Merge pull request TheAlgorithms#737 from abircb/Development

yanglbme · web-flow · commit af6daf7af697 · 2019-05-11T09:42:32.000+08:00
Added DepthFirstSearch.java and DepthFirstTestSearch.java
diff --git a/src/main/java/com/search/DepthFirstSearch.java b/src/main/java/com/search/DepthFirstSearch.java
@@ -0,0 +1,123 @@
+package src.main.java.com.search;
+
+/**
+ * Searching is faster in sorted structures. Binary search is O(log n).
+ * However, the cost of sorting is O(n · log n).
+ * What to do when adding or removing elements? Sort again? No.
+ * Create efficient data structures to maintain sorted sequences, and search in them
+ * Key example: binary sorted tree, allowing O(log N) insert, remove and lookup.
+   
+   In comes, depth-first search
+ * Worst-case performance	O(n)
+ * Best-case performance	O(1)
+ * Average performance	   	O(n)
+ * 
+ */
+
+public class DepthFirstSearch {
+	
+    /**
+     * Depth-first search method
+     *
+     * @param tree- Binary tree to be searched
+     * @param value- Key being searched for
+     * @return Location of the key
+     */
+
+	public static <T extends Comparable<T>> T find(T key, BinaryTree<T> tree) {
+        	return tree.get(key);
+	}
+	
+}
+
+/**
+ * The BinaryTree class defines the structure of a binary tree
+ * Also contains a static nested class called TreeNode
+ * @param <T>
+ */
+class BinaryTree<T extends Comparable<T>> {
+	
+	private TreeNode<T> root;
+	
+	/**
+	 * @param <P> 
+	 * This class defines what a node in a binary tree looks like
+	 */
+	private static class TreeNode<P extends Comparable<P>>  {
+		
+		P key, value;
+		TreeNode<P> left, right;
+		
+		private TreeNode(P key, P value) {
+			this.key = key;
+			this.value = value;
+			this.left = null;
+			this.right = null;
+		}
+		
+		/**
+		 * @param node
+		 * adds the specified node
+		 */
+		private void add(TreeNode<P> node) {
+			if (node.key.compareTo(this.key) < 0) {
+				if(this.left == null) {
+					this.left = node;
+				}
+				else {
+					this.left.add(node);
+				}
+			}
+			
+			else {
+				if(this.right == null) {
+					this.right = node;
+				}
+				else {
+					this.right.add(node);
+				}
+			}
+		}
+		
+		/**
+		 * @param key
+		 * @return the tree node corresponding to the key
+		 */
+		private TreeNode<P> find(P key) {
+			if (key.compareTo(this.key) == 0) return this;
+
+			else if(key.compareTo(this.key) < 0) {
+				if (this.left == null) return null;
+				else return this.left.find(key);
+			}
+			
+			else {
+				if(this.right == null) return null;
+				else return this.right.find(key);
+			}
+		}
+		
+	}
+	
+	public BinaryTree() {
+		this.root = null;
+	}
+	
+	public void add(T key, T value) {
+		TreeNode<T> node = new TreeNode<T>(key, value);
+		if(this.root == null) {
+			this.root = node;
+		}
+		else {
+			this.root.add(node);
+		}
+	}
+	
+	public T get(T key) {
+		if(this.root == null) return null;
+		
+		TreeNode<T> node = this.root.find(key);
+		if(node == null) return null;
+		return node.value;
+	}
+}
diff --git a/src/test/java/com/search/DepthFirstSearchTest.java b/src/test/java/com/search/DepthFirstSearchTest.java
@@ -0,0 +1,36 @@
+package src.test.java.com.search;
+
+import org.junit.Assert;
+import org.junit.Test;
+import src.main.java.com.search.DepthFirstSearch;
+import src.main.java.com.search.BinaryTree;
+
+public class DepthFirstSearchTest {
+    @Test
+    public void testDepthFirstSearch() {
+
+        BinaryTree<Integer> tree1 = new BinaryTree<Integer>();
+        tree1.add(1,1);
+        tree1.add(2,2);
+        tree1.add(3,3);
+        tree1.add(4,4);
+        Assert.assertEquals("Incorrect index", 3, DepthFirstSearch.find(3, tree1));
+        Assert.assertEquals("Incorrect index", 1, DepthFirstSearch.find(1, tree1));
+        Assert.assertEquals("Incorrect index", null, DepthFirstSearch.find(0, tree1));
+        Assert.assertEquals("Incorrect index", null, DepthFirstSearch.find(8, tree1));
+        Assert.assertEquals("Incorrect index", null, DepthFirstSearch.find(-2, tree1));
+
+        BinaryTree<String> tree2 = new BinaryTree<String>();
+        tree2.add("1","A");
+        tree2.add("2","B");
+        tree2.add("3","C");
+        tree2.add("4","D");
+        
+        Assert.assertEquals("Incorrect index", "C", LinearSearch.findIndex(tree2,"3"));
+        Assert.assertEquals("Incorrect index", "B", LinearSearch.findIndex(tree2,"2"));
+        Assert.assertEquals("Incorrect index", null, LinearSearch.findIndex(tree2,"F"));
+
+        BinaryTree<String> tree3 = new BinaryTree<String>();
+        Assert.assertEquals("Incorrect index", null, LinearSearch.findIndex(tree3, ""));
+    }
+}
