We define a left-justified, complete binary tree with height H as a tree where:
- levels 1,...,H-1 contain the maximum number of nodes,
- and in level H all the nodes are "left-justified", that is, as far to the left is possible.
Construct such a complete tree of unknown height, with
n nodes containing
v as label.
completeTree 'x' 4 == Node 'x' (Node 'x' (Node 'x' Empty Empty) Empty) (Node 'x' Empty Empty)
import Html import List type Tree a = Empty | Node a (Tree a) (Tree a) completeTree : a -> Int -> Tree a completeTree v n = -- your implementation here Empty main = Html.text (if (test) then "Your implementation passed all tests." else "Your implementation failed at least one test." ) test : Bool test = List.all ((==) True) [ completeTree 'x' 0 == Empty , completeTree 'x' 1 == Node 'x' Empty Empty , completeTree 'x' 3 == (Node 'x' (Node 'x' Empty Empty) (Node 'x' Empty Empty)) , completeTree 'x' 5 == (Node 'x' (Node 'x' (Node 'x' Empty Empty) (Node 'x' Empty Empty)) (Node 'x' Empty Empty)) ]
Heaps commonly use complete binary trees as data structures or addressing schemes. We can assign an address to each node in a complete binary tree by enumerating the nodes in level-order starting at the root with number 1. For every node
X with address
A the following holds: The address of
X's left and right successors are
2*A+1, respectively, if they exist. This fact can be used to elegantly construct a complete binary tree structure.