Skip to content

Instantly share code, notes, and snippets.

@iowaguy
Created January 14, 2015 04:49
Show Gist options
  • Save iowaguy/11410019d7b426642dae to your computer and use it in GitHub Desktop.
Save iowaguy/11410019d7b426642dae to your computer and use it in GitHub Desktop.
A depth first search implementation with some testing features
import java.util.LinkedList;
public class Node {
public String name;
public LinkedList<Node> children = new LinkedList<Node>();
public Node(String name) {
this.name = name;
}
public void addChild(Node child) {
this.children.add(child);
}
}
import java.util.LinkedList;
import java.util.Deque;
public class TreeSearch {
public static Node search(String name, Node root) {
Deque<Node> stack = new LinkedList<Node>();
stack.push(root);
while (stack.size() != 0) {
Node current = stack.pop();
System.out.println(current.name);
if (current.name.equals(name)) return current;
for (Node child: current.children) {
stack.push(child);
}
}
return null;
}
}
public class TreeSearchTest {
public static void main(String args[]) {
if (args.length == 0) {
System.err.println("Enter node name to search for: java TreeSearch <name>");
return;
}
Node root = createTestTree();
Node result = TreeSearch.search(args[0], root);
if (result != null) {
System.out.println("Result: " + result.name);
} else {
System.out.println("Not in tree");
}
}
public static Node createTestTree() {
Node a = new Node("a");
Node b = new Node("b");
Node c = new Node("c");
a.addChild(b);
a.addChild(c);
Node d = new Node("d");
Node e = new Node("e");
Node f = new Node("f");
b.addChild(d);
b.addChild(e);
b.addChild(f);
Node g = new Node("g");
Node h = new Node("h");
c.addChild(g);
g.addChild(h);
return a;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment