August 27, 2024
P63 - Construct a complete binary tree.
A complete binary tree with height H is defined as follows: The levels 1,2,3,...,H-1 contain the maximum number of nodes, i.e 2(i-1) nodes at the level i (note that we start counting the levels from 1 at the root). At level H, which may contain less than the maximum possible number of nodes, all the nodes are "left-adjusted".
This means that in a level-order tree traversal all internal nodes come first, the leaves come second, and empty successors (the Ends which are not really nodes) come last. Particularly, complete binary trees are used as data structures (or addressing schemes) for heaps.
We can assign an address number to each node in a complete binary tree by enumerating the nodes in level order, starting at the root with number 1.
In doing so, we realize that for every node X with address A the following property holds: The address of X's left and right children are 2*A and 2*A+1 (assuming the children exist). This fact can be used to elegantly construct a complete binary tree structure.
Write a method completeBinaryTree that takes as parameters the number of nodes and the value to put in each node.
> completeBinaryTree(6, "x")
T(x T(x T(x) T(x)) T(x T(x) .))kotlin
package org.kotlin99.binarytrees
import com.natpryce.hamkrest.assertion.assertThat
import org.junit.Test
import org.kotlin99.binarytrees.P57Test.Companion.equalToTree
import org.kotlin99.binarytrees.Tree.End
import org.kotlin99.binarytrees.Tree.Node
fun <T> completeBinaryTree(nodeAmount: Int, value: T): Tree<T> {
fun generate(nodeAddress: Int): Tree<T> =
if (nodeAddress > nodeAmount) End
else Node(value, generate(nodeAddress * 2), generate(nodeAddress * 2 + 1))
return generate(1)
}
class P63Test {
@Test fun `construct complete binary tree`() {
assertThat(completeBinaryTree(1, "x"), equalToTree(
Node("x")
))
assertThat(completeBinaryTree(2, "x"), equalToTree(
Node("x", Node("x"))
))
assertThat(completeBinaryTree(3, "x"), equalToTree(
Node("x", Node("x"), Node("x"))
))
assertThat(completeBinaryTree(6, "x"), equalToTree(
Node("x",
Node("x", Node("x"), Node("x")),
Node("x", Node("x"), End))
))
}
}