Created
April 26, 2017 12:39
-
-
Save milovtim/fff9712e7c4543a843406d3095e80c16 to your computer and use it in GitHub Desktop.
Simple implementation and example of tree traversal strategies: deepth-first and breath-first
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.panbet.tree | |
import groovy.transform.ToString | |
import spock.lang.Shared | |
import spock.lang.Specification | |
/** | |
* Simple example of deep-first and breath-first tree traversal | |
* Sample tree | |
* <pre> | |
(1) | |
/ \ | |
(2) (3) | |
/ / \ | |
(4) (5) (6) | |
/ | \ | \ \ | |
(7) (8) (9) (10) (11) (12) | |
</pre> | |
* | |
*/ | |
class TreeVisitorTest extends Specification { | |
@Shared | |
def data = [ | |
node(1, 0), | |
node(2, 1), | |
node(3, 1), | |
node(4, 2), | |
node(5, 3), | |
node(6, 3), | |
node(7, 4), | |
node(8, 4), | |
node(9, 4), | |
node(10, 5), | |
node(11, 5), | |
node(12, 6), | |
] | |
Tree tree | |
void setup() { | |
tree = new Tree(data[0], data) | |
} | |
def "Check tree structure"() { | |
expect: | |
tree.getById(3).parent == 1 | |
tree.getChildren(1).size() == 2 | |
tree.getChildren(1).first().id == 2 | |
tree.getChildren(1).last().id == 3 | |
tree.getChildren(2).size() == 1 | |
tree.getChildren(3).size() == 2 | |
} | |
def "Traverse strategies: breath and depths"() { | |
when: | |
def counter = 0 | |
Visitor v1 = { Node n -> | |
counter++ | |
println n | |
} | |
Visitor v2 = { Node n -> | |
counter-- | |
println n | |
} | |
println "${'='*10} Depth first ${'='*10}" | |
tree.visitDepth(v1) | |
println "${'='*10} Breath first ${'='*10}" | |
tree.visitBreath(v2) | |
then: | |
counter == 0 | |
} | |
static Node node(id, parent) { new Node(id: id, parent: parent) } | |
} | |
class Tree { | |
Tree(Node root, List<Node> dataIn) { | |
this.root = root | |
this.data = dataIn.collectEntries { [it.id, it] } | |
} | |
Node root | |
private Map<Integer, Node> data | |
Node getById(int id) { | |
data[id] | |
} | |
List<Node> getChildren(int parent) { | |
data.findAll { k, v -> v.parent == parent }.values() as List | |
} | |
void visitDepth(Visitor v) { | |
iterate(v, true) | |
} | |
void visitBreath(Visitor v) { | |
iterate(v, false) | |
} | |
/** | |
* For depth-first iteration call to <code>reverse()</code> method of collection is auxiliary (for pretty-print). | |
* Differences between deep-first and breath-first iteration is | |
*/ | |
private void iterate(Visitor v, boolean depthFirst) { | |
Queue<Node> state = new LinkedList<>() | |
state.add(root) | |
while (!state.isEmpty()) { | |
def current = depthFirst? state.pop(): state.remove() | |
getChildren(current.id).with { depthFirst? it.reverse(): it }.each(state.&add) | |
v.accept(current) | |
} | |
} | |
} | |
interface Visitor { | |
void accept(Node node) | |
} | |
@ToString(excludes = ['children']) | |
class Node { | |
int id | |
int parent | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment