Skip to content

Instantly share code, notes, and snippets.

@mgrzeszczak
Last active June 23, 2019 07:02
Show Gist options
  • Save mgrzeszczak/32036180a1bdd09a6fbdd1689a4213c7 to your computer and use it in GitHub Desktop.
Save mgrzeszczak/32036180a1bdd09a6fbdd1689a4213c7 to your computer and use it in GitHub Desktop.
Tree Algebraic Data Structure with different traverse orders implemented in Kotlin
import java.util.*
inline fun <T, R> T.ifNotNull(callback: T.() -> R): R? {
return this?.callback()
}
sealed class Tree<T> {
abstract val value: T;
}
class Node<T>(val left: Tree<T>?, val right: Tree<T>?, override val value: T) : Tree<T>() {
}
class Leaf<T>(override val value: T) : Tree<T>() {
}
enum class TraverseOrder {
PRE {
override fun <T> visitNode(t: Node<T>, body: T.() -> Unit) {
t.value.body()
traverse(t.left, body)
traverse(t.right, body)
}
},
POST {
override fun <T> visitNode(t: Node<T>, body: T.() -> Unit) {
traverse(t.left, body)
traverse(t.right, body)
t.value.body()
}
},
IN {
override fun <T> visitNode(t: Node<T>, body: T.() -> Unit) {
traverse(t.left, body)
t.value.body()
traverse(t.right, body)
}
},
LEVEL {
override fun <T> visitNode(t: Node<T>, body: T.() -> Unit) {
throw NotImplementedError()
}
override fun <T> traverse(t: Tree<T>?, body: T.() -> Unit) {
val queue: Queue<Tree<T>> = LinkedList(listOf(t))
while (queue.isNotEmpty()) {
val v = queue.poll()
v.value.body()
if (v is Node) {
v.left.ifNotNull(queue::add)
v.right.ifNotNull(queue::add)
}
}
}
};
protected abstract fun <T> visitNode(t: Node<T>, body: T.() -> Unit);
open fun <T> traverse(t: Tree<T>?, body: T.() -> Unit) {
when (t) {
is Node -> visitNode(t, body)
is Leaf -> t.value.body()
}
}
}
fun main() {
val tree: Tree<Int> = Node(
Node(
Leaf(5),
null,
1
),
Node(
Leaf(3),
Leaf(4),
2
),
0
)
println("IN")
TraverseOrder.IN.traverse(tree) {
println(this)
}
println()
println("PRE")
TraverseOrder.PRE.traverse(tree) {
println(this)
}
println()
println("POST")
TraverseOrder.POST.traverse(tree) {
println(this)
}
println()
println("LEVEL")
TraverseOrder.LEVEL.traverse(tree) {
println(this)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment