August 27, 2024
P70A - Count the nodes of a multiway tree.
A multiway tree is composed of a root element and a (possibly empty) set of successors which are multiway trees themselves. A multiway tree is never empty. The set of successor trees is sometimes called a forest.
The code to represent multiway-trees is somewhat simpler than the code for binary trees, partly because we don't separate classes for nodes and terminators, and partly because we don't need the restriction for the value type to be ordered.
data class MTree<out T>(val value: T, val children: List<MTree<T>> = emptyList()) {
constructor(value: T, vararg children: MTree<T>): this(value, children.toList())
override fun toString(): String =
if (children.isEmpty()) value.toString()
else value.toString() + " {" + children.joinToString(", "){ it.toString() } + "}"
} The example tree is, thus:
MTree("a",
MTree("f",
MTree("g")),
MTree("c"),
MTree("b",
MTree("d"), MTree("e"))
))
The starting code for this section is in MTree.kt.
Write a method nodeCount which counts the nodes of a given multiway tree.
> MTree("a", MTree("f")).nodeCount()
2kotlin
package org.kotlin99.multiwaytrees
import com.natpryce.hamkrest.assertion.assertThat
import com.natpryce.hamkrest.equalTo
import org.junit.Test
fun MTree<*>.nodeCount(): Int = 1 + children.sumOf { it.nodeCount() }
class P70ATest {
@Test fun `count nodes`() {
assertThat(MTree("a").nodeCount(), equalTo(1))
assertThat(MTree("a", MTree("f")).nodeCount(), equalTo(2))
assertThat(
MTree("a",
MTree("f", MTree("g")),
MTree("c"),
MTree("b", MTree("d"), MTree("e"))
).nodeCount(), equalTo(7))
}
}
Be first to comment