Skip to content

Instantly share code, notes, and snippets.

@nikolasburk
Created May 30, 2015 19:26
Show Gist options
  • Save nikolasburk/3f9c10d38a37a57295b5 to your computer and use it in GitHub Desktop.
Save nikolasburk/3f9c10d38a37a57295b5 to your computer and use it in GitHub Desktop.
Implementation of depth first search on a tree data structure (breadth first search yet to come)
public class DepthFirstSearch {
private Tree tree;
private Node result;
public DepthFirstSearch(Tree tree) {
this.tree = tree;
}
public Node depthFirstSearch(String name) {
result = null;
depthFirstSearch(tree.getRoot(), name);
if (result != null) {
System.out.println("found node with name " + result.getName());
}
else {
System.out.println("did not find node " + name);
}
return result;
}
private void depthFirstSearch(Node currentNode, String name) {
if (currentNode.getName().equals(name)) {
result = currentNode;
return;
}
for (Node child: currentNode.getChildren()) {
if (result != null) return;
depthFirstSearch(child, name);
}
}
public static void main(String[] args) {
Tree tree = new Tree();
DepthFirstSearch dfs = new DepthFirstSearch(tree);
dfs.depthFirstSearch("d");
dfs.depthFirstSearch("z");
dfs.depthFirstSearch("h");
dfs.depthFirstSearch("x");
dfs.depthFirstSearch("a");
dfs.depthFirstSearch("p");
dfs.depthFirstSearch("g");
}
}
import java.util.ArrayList;
public class Node {
private final String name;
private ArrayList<Node> children;
public Node(String name) {
this.name = name;
this.children = new ArrayList<Node>();
}
public void addChild(String name) {
Node child = new Node(name);
this.children.add(child);
}
public void addChild(Node child) {
this.children.add(child);
}
public String getName() {
return name;
}
public ArrayList<Node> getChildren() {
return children;
}
}
import java.util.LinkedList;
public class Tree {
private Node root;
public Tree() {
root = sampleTree();
}
public Node getRoot() {
return root;
}
private void printLevelOrder() {
LinkedList<Node> queue = new LinkedList<Node>();
queue.addFirst(root);
while(queue.size() > 0) {
Node currentNode = queue.removeLast();
System.out.println(currentNode.getName());
for (Node child: currentNode.getChildren()) {
queue.addFirst(child);
}
}
}
private Node sampleTree() {
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");
c.addChild(g);
Node h = new Node("h");
g.addChild(h);
return a;
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.printLevelOrder();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment