COMP1100/1130 [2020 S1]:
PROGRAMMING AS PROBLEM SOLVING Research School of Computer Science
Menu
menu
» Labs » Week 9: Trees
In this lab we cover the concept of trees, how they differ to lists, and how we can write
recursive functions that operate on trees.
Table of Contents
Trees Binary Trees Rose Trees Extensions
Pre-Lab Checklist
You understand the concept of higher order functions and how to apply them. You can write recursive functions over lists and numbers.
You are familiar with pattern matching against abstract data types.
Getting Started
1. Go to the project’s dashboard under the Project tab and click on the Fork button. The gitlab url for this lab is https://gitlab.cecs.anu.edu.au/comp1100/2020s1studentZles/lab09
2. You will be asked where to fork the repository. Click on the user or group to where you’d like to add the forked project. You should see your own name here. Once you have successfully forked a project, you will be redirected to a new webpage where you will notice your name before > project-name. This means you are now the owner of this repository. The url in your browser should re[ect the change: https://gitlab.cecs.anu.edu.au/uXXXXXXX/lab09
3. Finally, clone your forked repository to your computer according to the instructions in the Week 2 Lab.
Trees
So far the only recursive data structure we’ve really seen are lists. Lists are useful for packing many elements of the same type together, but sometimes they can be a hindrance from an e]ciency perspective. When we are trying to Znd the last element in a list, we always have to traverse through all elements, even if we know how long the list is. We will see more about the beneZts of trees in next lab when we cover binary search trees, but for this lab, we consider two kinds of trees, binary and rose.
Binary Trees
There are many different kinds of trees (Rose, AVL, Red-Black, Quad) but we will concentrate on the simplest kind of trees for the moment, Binary Trees. Binary Trees have a recursive deZnition, similar to lists:
A binary tree (containing elements of type a) is either:
An empty, or null tree. (This is the base case for Binary Trees, like the empty list for Lists.)
A node, which contains an element of type a, and two more binary trees, called subtrees. (This is the step case for Binary Trees, like how the step case for a list was an element, attached to another list).
data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
Note how similar this is to the deZnition for a list, except each non-empty list is an element, followed by exactly one other list. We call the two subtrees the left subtree and the right subtree respectively.
How a tree is structured is best seen graphically.
A lot of the terminology relating to trees is borrowed from that of real life trees.
We call the node at the very top of the tree the root node. The nodes down at the bottom that only have empty subtrees beneath them are called leaves.
Unfortunately the same tree doesn’t read as nicely when expressed using our recursive deZnition. Due to the way trees branch (just like their real life counterparts) they are di]cult to display textually.
Written out directly,
This lab contains additional exercises for COMP1130 students. COMP1100 students are encouraged to attempt them once they have completed the compulsory exercises to receive the participation marks for the lab.
Computer scientists, having spent their entire life in front of a computer and never gone outside, have evidentially forgotten that trees are supposed to grow up, not down.
tree1 :: BinaryTree Integer
tree1 = Node (Node (Node Null 2 (Node Null 11 Null)) 4 (Node (Node Null 0 N 1 (Node Null (-3) Null))) 5 (Node (Node (Node Null (-4) Null) 8
(Node Null 7 Null)) 3 Null)
There’s no clear correspondence between how Haskell stores the tree and the graphical picture of the tree. We’ve included some code in DrawTree.hs that Lab09.hs imports, so you can use the function printTree (don’t worry about how it works) which will print the trees graphically. You may Znd useful to play with and to help you visualise the output of functions.
We can pattern match against binary trees in a similar way to pattern matching against lists. Here is a list of useful patterns you might need. Note that there is nothing special about using the variables left or right to pattern match against, but it’s just a bit more readable that way:
Now, with that in mind, we can start to write some functions on trees. We can write recursive functions operating over trees, just the same as we did over lists, using the patterns described above.
Info: For the following exercises, having some pen and paper on hand to graphically draw out test cases before entering them into Haskell
Exercise 1
Recall the function we wrote in Lab 6, lengthList, that would take a list and return the number of elements.
treeSize :: BinaryTree a -> Integer Submission required: Exercise 1 treeSize
Exercise 2
treeDepth :: BinaryTree a -> Integer Submission required: Exercise 2 treeDepth
Note that the same number of nodes can be rearranged into trees of different depth, as demonstrated below.
Exercise 3
flattenTree :: BinaryTree a -> [a] Submission required: Exercise 3 flattenTree
Note that by [attening the tree, we lose some information, namely how the tree itself was structured.
You can sanity check the result by testing for some example trees (or the example trees provided) that
length (flattenTree tree) == treeSize tree
that is, that the number of elements in the [attened list, is the same as the number of
elements originally in the tree.
Exercise 4
leavesTree :: BinaryTree [a] -> [a] Submission required: Exercise 4 leavesTree
Exercise 5
treeMap :: (a -> b) -> (BinaryTree a) -> (BinaryTree b) Submission required: Exercise 5 treeMap
Exercise 6
elemTree :: Integer -> (BinaryTree Integer) -> Bool Submission required: Exercise 6 elemTree
Exercise 7
Submission required: Exercise 7 treeMaximum, treeMinimum Rose Trees
Binary trees are characterised by the property that each node has exactly two children. Rose trees are different, in that each node can have any number of children (including none).
RoseTree a = RoseNode a [RoseTree a]
Note that there is no empty case like there is for our deZnition of a BinaryTree. (What’s
the closest thing we can get to the empty tree under this deZnition?)
Rosetrees can have a different number of children for each node, there’s no constraint on how few (or how many) there must be. We’ve included the following tree things :: RoseTree String as an example for you to use.
Rosetrees can be useful for games (like Chess), as you can draw out all your possible moves, and all of your opponents possible responses, and all of your responses to their responses, and so on.
Exercise 8
Write a function roseSize that counts the number of elements in a rosetree. roseSize :: RoseTree a -> Integer
Submission required: Exercise 8 roseSize
Exercise 9
Write a function roseLeaves that returns a list of all leaves of the rosetree. roseLeaves :: RoseTree a -> [a]
You can test your function by counting the number of leaves in the rose tree things.
Submission required: Exercise 9 roseLeaves
Exercise 10
Write a function roseFlatten that returns a list of all elements in the rosetree. roseFlatten :: RoseTree a -> [a]
Submission required: Exercise 10 roseFlatten
Exercise 11
roseMap :: (a -> b) -> RoseTree a -> RoseTree b
Submission required: Exercise 11 roseMap
Test the result by mapping the function allCaps to the rosetree things. All the elements
should now be written in uppercase.
Exercise 12
Write a function binaryTreeToRose that converts a binary tree to a rosetree. The new rosetree should have the same structure as the binary tree.
binaryTreeToRose :: BinaryTree a -> RoseTree a Submission required: Exercise 12 binaryTreeToRose
Extensions [COMP1100 Optional, COMP1130 Compulsory]
Extension 1
isBalanced :: BinaryTree a -> Bool Submission required: Extension 1 isBalanced
For example, given the elements {1, 2, 3, 4, 5}, a balanced tree containing those elements is shown below. Note that a tree of depth 2 can hold at most 3 elements (why?) so we had to use a depth 3 tree. (Note that this is not the only way to arrange these elements into a tree. Can you Znd another?)
(Hint: How can we related the number of elements in a tree to it’s depth, and what do these quantities tell us about the tree being balanced or not?)
ull
>printTree tree1
5
|
+- 3
||
| +- Null
||
| `- 8
||
| +-7 |||
| |+-Null |||
| |`-Null ||
| `–4 ||
| +- Null ||
| `- Null |
`- 4
|
+- 1
||
| +- -3 |||
| | +- Null |||
| | `- Null ||
| `- 0 ||
| +- Null ||
| `- Null |
`- 2
|
+- 11
||
| +- Null ||
| `- Null |
`- Null
Pattern
Description
Example
Null
The (unique) empty tree
Null
Node left x right
A non-empty tree
Anything that isn’t Null.
Node Null x Null
A tree with no subtrees (called a leaf)
Node Null 3 Null,
Node Null “hello” Null
Node Null x right
A non-empty tree, with no left subtree
Node Null 3 (Node Null 4 Null),
Node Null 10 Null
Node left 8 right
A non-empty tree with 8 as the element
Node (Node Null 4 Null) 8 Null,
Node Null 8 (Node Null 5 Null)
Write the treeSize function, that takes a tree, and counts the number of elements in the tree.
Write a function treeDepth that computes the depth of a tree, which is deZned as the length of the longest path from the root node down to any leaf.
>treeDepth Null
0
>treeDepth (Node Null 3 Null)
1
>treeDepth (Node (Node Null 1 Null) 2 (Node Null 3 Null)) 2
>treeDepth (Node Null 1 (Node Null 2 (Node Null 3 Null))) 3
You might like to contemplate if the size and depth of a tree are related in anyway. (Given you know the size of a tree, what possible values of the depth can there be?)
Write a function flattenTree that takes a tree, and returns a list containing all the elements from that tree. We call such an operation “[attening” a tree.
>flattenTree Null
[]
>flattenTree (Node Null 3 Null)
[3]
>flattenTree (Node (Node Null 1 Null) 2 (Node Null 3 Null)) [1,2,3]
>flattenTree (Node Null 1 (Node Null 2 (Node Null 3 Null))) [1,2,3]
Write a function leavesTree that takes a tree, and returns a list containing only the elements in leaf nodes.
>leavesTree Null
[]
>leavesTree (Node Null 3 Null)
[3]
>leavesTree (Node (Node Null 1 Null) 2 (Node Null 3 Null)) [1,3]
>leavesTree (Node Null 1 (Node Null 2 (Node Null 3 Null))) [3]
Write a function treeMap that works analogously to map, by applying a function to each node in a tree.
>treeMap (*2) (Node Null 3 (Node Null 5 Null)) Node Null 6 (Node Null 10 Null)
Write a function elemTree that takes an Integer, and checks if it is present inside a tree of Integer’s.
>elemTree 2 Null
False
>elemTree 3 (Node Null 4 (Node Null 3 Null)) True
Write two functions, treeMaximum and treeMinimum, to Znd the minimum and maximum element in a tree of type Integer.
treeMaximum :: BinaryTree Integer -> Integer treeMinimum :: BinaryTree Integer -> Integer
>roseSize things 27
> length (roseLeaves things) 16
>roseLeaves things
[“cat”, “dog”, “steel”, “bronze”, “gold”, …]
>roseFlatten things
[“thing”, “animal”, “cat”, “dog”, “metal”, “alloy”, “steel”, …]
> length (roseFlatten things) 27
Write a function roseMap that takes a function, and applies it to every element of a rosetree.
>binaryTreeToRose (Node (Node Null 1 Null) 2 (Node Null 3 Null)) RoseNode 2 [RoseNode 1 [],RoseNode 3 []]
You are required to submit your attempts at the exercises above in order to receive full participation marks for this lab. You have until the start of your next lab to do this. You should submit by committing and pushing all your changes to your Gitlab repository.
Write a function isBalanced that veriZes if a tree is “balanced”, that is, there is no other way to restructure the tree such that it has smaller depth.
Consider: Why might it be advantageous to have a balanced binary tree? Chat with your peers and tutor if you are unsure. We will investigate the beneZts of enforcing a certain structure on complex data types in future labs (and courses!).
Updated: 06 Jun 2020
Responsible O]cer: Director, RSCS
Page Contact:
Course Convenor
Contact ANU
Copyright
Disclaimer
Privacy
Freedom of Information
+61 2 6125 5111
The Australian National University, Canberra CRICOS Provider : 00120C ABN : 52 234 063 906