Fri Oct 19
Here is an implementation of a tree that stores values only at the interior branches; the leaves are empty.
Here is a link to lots of sample trees, with diagrams, built using these constructors.
You should instantiate the
Functor type class for
ITree, so we can do this:
ghci> fmap square t1 IBranch 9 (IBranch 16 ILeaf (IBranch 25 (IBranch 49 ILeaf ILeaf) ILeaf)) (IBranch 81 ILeaf ILeaf) ghci> fmap show t1 IBranch "3" (IBranch "4" ILeaf (IBranch "5" (IBranch "7" ILeaf ILeaf) ILeaf)) (IBranch "9" ILeaf ILeaf)
That means using the
instance keyword and defining the function
fmap for the
ITree type. There are two examples of
Functor instantiations in the notes from 8 Oct.
Define the function
flipTree that swaps the left and right branches throughout the entire tree.
Below is a figure of a tree and its flipped counterpart:
This function converts a tree to a list.
The elements of the list should be ordered according to a pre-order traversal. That means for a branch, the element at that branch comes first, then the elements of the left sub-tree, then the right sub-tree.
So the pre-order traversal of
ghci> preOrderList t1 [3,4,5,7,9] ghci> preOrderList $ flipTree t1 [3,9,4,5,7]
A tree is balanced if at every branch, the difference in height between the left and right sub-trees is at most one. We’re going to determine whether a tree is balanced by returning a
Maybe Int. If the result is
Nothing then the tree is not balanced. A
Just result indicates it is balanced, with the specified height.
ghci> balancedHeight t1 Nothing ghci> balancedHeight t7 Just 4
(You can see pictures of these sample trees,
t7, on this page.)
The way to approach
balancedHeight for a branch is to recursively compute the height of the left and right sub-trees. If either of those produces
Nothing, then we also return
Nothing. If those produce
Just n1 for the left and
Just n2 for the right, then we check the absolute value of the difference. If that difference is larger than 1, return
Nothing. Otherwise use
Just with the usual height formula: one more than the maximum height of left and right!
If we just want a Boolean to indicate balanced or not, we can compose with
isJust from the
Finally, we’d like to be able to take a list of elements and build a balanced tree. That means splitting the list in half (you can use
Make sure that the list corresponds to a preorder traversal of the tree. That is, for any tree
t, we should have:
Also for any list
xs we should have:
This is here just in case we need a