August 27, 2024
P64 - Layout a binary tree (1).
As a preparation for drawing a tree, a layout algorithm is required to determine the position of each node in a rectangular grid. Several layout methods are conceivable, one of them is shown in the illustration below. This tree can be constructed with "nkmcahgeupsq".toList().toTree().
In this layout strategy, the position of a node v is obtained by the following two rules:
- x(v) is equal to the position of the node v in the in-order sequence
- y(v) is equal to the depth of the node v in the tree In order to store the position of the nodes, we add a new data classes with the additional information.
data class Point(val x: Int, val y: Int)
data class Positioned<out T>(val value: T, val point: Point) {
constructor (value: T, x: Int, y: Int) : this(value, Point(x, y))
override fun toString(): String =
"[" + point.x.toString() + "," + point.y.toString() + "] " + value.toString()
}Write a method layout that turns a tree of normal Nodes into a tree with positions Tree<Positioned<T>>.
> Node("a", Node("b", End, Node("c")), Node("d")).layout()
T([3,1] a T([1,2] b . T([2,3] c)) T([4,2] d))kotlin
package org.kotlin99.binarytrees
import com.natpryce.hamkrest.assertion.assertThat
import com.natpryce.hamkrest.equalTo
import org.junit.Test
import org.kotlin99.binarytrees.Tree.End
import org.kotlin99.binarytrees.Tree.Node
data class Point(val x: Int, val y: Int)
data class Positioned<out T>(val value: T, val point: Point) {
constructor (value: T, x: Int, y: Int): this(value, Point(x, y))
override fun toString(): String =
"[" + point.x.toString() + "," + point.y.toString() + "] " + value.toString()
}
/**
* Assigned coordinates to tree nodes where:
* - X is determined by the position of parent node and the amount of current node left children
* - Y is depth of current node (root node has depth 1)
*/
fun <T> Tree<T>.layout(xShift: Int = 0, y: Int = 1): Tree<Positioned<T>> =
when (this) {
End -> End
is Node<T> -> {
val x = xShift + left.nodeCount() + 1
Node(value = Positioned(value, Point(x, y)),
left = left.layout(xShift, y + 1),
right = right.layout(x, y + 1))
}
}
class P64Test {
@Test fun `positioned nodes pretty print`() {
assertThat(
Node(Positioned("a", 1, 1)).toPrettyString(),
equalTo("""
| 012
|0···
|1·a·
|2···
""".trimMargin()))
assertThat(
Node(Positioned("a", 2, 1),
Node(Positioned("b", 1, 2)),
Node(Positioned("c", 3, 2))).toPrettyString(),
equalTo("""
| 01234
|0·····
|1··a··
|2·b·c·
|3·····
""".trimMargin()))
}
@Test fun `layout binary tree (1)`() {
assertThat(
Node("a").layout().toPrettyString(),
equalTo("""
| 012
|0···
|1·a·
|2···
""".trimMargin()))
assertThat(
Node("a", Node("b")).layout().toPrettyString(),
equalTo("""
| 0123
|0····
|1··a·
|2·b··
|3····
""".trimMargin()))
assertThat(
Node("a", Node("b", Node("c"))).layout().toPrettyString(),
equalTo("""
| 01234
|0·····
|1···a·
|2··b··
|3·c···
|4·····
""".trimMargin()))
assertThat(
Node("a", Node("b"), Node("c")).layout().toPrettyString(),
equalTo("""
| 01234
|0·····
|1··a··
|2·b·c·
|3·····
""".trimMargin()))
assertThat(
Node("a", Node("b", End, Node("c")), Node("d")).layout().toPrettyString(),
equalTo("""
| 012345
|0······
|1···a··
|2·b··d·
|3··c···
|4······
""".trimMargin()))
assertThat(
Node("a", Node("b", Node("d"), Node("e")), Node("c", Node("f"), Node("g"))).layout().toPrettyString(),
equalTo("""
| 012345678
|0·········
|1····a····
|2··b···c··
|3·d·e·f·g·
|4·········
""".trimMargin()))
}
@Test fun `P64 illustration example`() {
assertThat(
"nkmcahgeupsq".toList().toTree().layout().toPrettyString(),
equalTo("""
| 01234567890123
|0··············
|1········n·····
|2······k·····u·
|3··c····m·p····
|4·a···h·····s··
|5····g·····q···
|6···e··········
|7··············
""".trimMargin()))
}
companion object {
fun Tree<Positioned<*>>.toPrettyString(xPadding: Int = 1, yPadding: Int = 1): String {
return when (this) {
End -> ""
is Node -> {
val nodes = nodes()
val xs = nodes.map { it.value.point.x }
val ys = nodes.map { it.value.point.y }
val xRange = (xs.minOrNull()!! - xPadding)..(xs.maxOrNull()!! + xPadding)
val yRange = (ys.minOrNull()!! - yPadding)..(ys.maxOrNull()!! + yPadding)
val nodeByPoint = nodes.groupBy { it.value.point }
val xHeader = " " + xRange.map { it.toString().last() }.joinToString("") + "\n"
val body = yRange.map { y ->
val line = xRange.map { x -> nodeByPoint[Point(x, y)]?.first()?.value?.value ?: "·" }
y.toString().last() + line.joinToString("")
}
xHeader + body.joinToString("\n")
}
}
}
}
}
Be first to comment