Lab 5: Linked Lists and Trees
Due at 11:59pm on 07/06/2017.
Starter Files
Download lab05.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.
Submission
By the end of this lab, you should have submitted the lab with
python3 ok --submit
. You may submit more than once before the
deadline; only the final submission will be graded.
- To receive credit for this lab, you must complete Questions 1-5 in lab05.py and submit through OK.
- Questions 6-10 are extra practice. They can also be found in the lab05_extra.py file. It is recommended that you complete these problems on your own time.
Topics
Linked Lists
Python has many built-in types of sequences: lists, ranges, and strings, to name a few. In this lab, we instead construct our own type of sequence called a linked list. A linked list is a simple type of sequence that is comprised of multiple links that are connected.
Each link
is a pair where the first
element is an item in the linked list,
and the second
element is another link
.
Constructors:
link(first, rest)
: Construct a linked list withfirst
element and the next linkrest
.empty
: The empty linked list.
Selectors
first(s)
: Returns the first element in the given linked lists
.rest(s)
: Returns the rest of the linked lists
.
Other
is_link(s)
: ReturnsTrue
ifs
is a linked list.print_link(s)
: Prints out the linked lists
.
We can construct the Linked list shown above by using the constructors. The
first
element of this Linked list is 12 while the rest
is another Linked
list that contains 99 and 37:
>>> x = link(12, link(99, link(37)))
>>> first(x)
12
>>> first(rest(x))
99
>>> first(rest(rest(x)))
37
Note: Notice that we can just use
link(37)
insteadlink(37, empty)
. This is because the second argument of thelink
constructor has a default argument ofempty
.
Trees
A tree
is a data structure that represents a hierarchy of information. A file system is a good example of a tree structure. For example, within your cs61a
folder, you have folders separating your projects
, lab
assignments, and homework
. The next level is folders that separate different assignments, hw01
, lab01
, hog
, etc., and inside those are the files themselves, including the starter files and ok
. Below is an incomplete diagram of what your cs61a
directory might look like.
As you can see, unlike trees in nature, the tree abstract data type is drawn with the root at the top and the leaves at the bottom.
Some tree terminology:
- root or root value: the value at the top of the tree, selected by the
root
function - branches: a list of trees directly under the tree's root, selected by the
branches
function - leaf: a tree with zero branches
- node: any location within the tree (e.g., root node, leaf nodes, etc.)
Our tree
abstract data type consists of a root and a list of its
branches
. To create a tree and access its root and branches, use the
following constructor and selectors:
Constructor
tree(root, branches=[])
: creates a tree object with the givenroot
value at its root and list ofbranches
.
Selectors
root(tree)
: returns the value in the root oftree
.branches(tree)
: returns the list of branches of the giventree
.
Convenience function
is_leaf(tree)
: returnsTrue
iftree
's list ofbranches
is empty, andFalse
otherwise.
For example, the tree generated by
t = tree(1,
[tree(2),
tree(3,
[tree(4),
tree(5)]),
tree(6,
[tree(7)])])
would look like this:
1
/ | \
2 3 6
/ \ \
4 5 7
To extract the number 3
from this tree, which is the root of its second branch, we would do this:
root(branches(t)[1])
Required Problems
Linked List Practice
Question 1: Link to List
Write a function link_to_list
that takes a linked list and converts it to a Python list.
Hint: To check if a linked list is empty, you can use
lst == empty
. Also, you can combine two Python lists using+
.
def link_to_list(linked_lst):
"""Return a list that contains the values inside of linked_lst
>>> link_to_list(empty)
[]
>>> lst1 = link(1, link(2, link(3, empty)))
>>> link_to_list(lst1)
[1, 2, 3]
"""
"*** YOUR CODE HERE ***"
if linked_lst == empty:
return []
else:
return [first(linked_lst)] + link_to_list(rest(linked_lst))
# Iterative version
def link_to_list_iterative(linked_lst):
"""
>>> link_to_list_iterative(empty)
[]
>>> lst1 = link(1, link(2, link(3, empty)))
>>> link_to_list_iterative(lst1)
[1, 2, 3]
"""
new_lst = []
while linked_lst != empty:
new_lst += [first(linked_lst)]
linked_lst = rest(linked_lst)
return new_lst
Use OK to test your code:
python3 ok -q link_to_list
WWPD?
Question 2: Tree Structure
As described above, trees are constructed recursively with smaller subtrees using the constructor:
tree(root, branches=[])
Test your understanding of how trees are constructed in Python by examining trees and deciding which of the choices of Python code matches that tree:
python3 ok -q structure -u
PyTunes
Question 3: Create pyTunes
All pyTunes accounts come with the free songs below. Define the function make_pytunes
, which takes in username
and creates this tree:
The doctest below shows the print_tree
representation of a default pyTunes tree.
def make_pytunes(username):
"""Return a pyTunes tree as shown in the diagram with USERNAME as the value
of the root.
>>> pytunes = make_pytunes('i_love_music')
>>> print_tree(pytunes)
i_love_music
pop
justin bieber
single
what do you mean?
2015 pop mashup
trance
darude
sandstorm
"""
"*** YOUR CODE HERE ***"
return tree(username,
[tree('pop',
[tree('justin bieber',
[tree('single',
[tree('what do you mean?')])]),
tree('2015 pop mashup')]),
tree('trance',
[tree('darude',
[tree('sandstorm')])])])
Use OK to test your code:
python3 ok -q make_pytunes
Question 4: Number of Songs
A pyPod can only hold a certain number of songs, and you need to find out
whether or not all the songs in your pyTunes account will fit. Define the
function num_songs
, which takes in a pyTunes tree t
and returns the number
of songs in t
. Recall that there are no empty directories in pyTunes, so all
leaves in t
are songs.
Hint: You can use is_leaf
to check whether a given tree is a leaf.
>>> no_branches = tree(1)
>>> is_leaf(no_branches)
True
>>> is_leaf(tree(5, [tree(3), tree(4)]))
False
def num_songs(t):
"""Return the number of songs in the pyTunes tree, t.
>>> pytunes = make_pytunes('i_love_music')
>>> num_songs(pytunes)
3
"""
"*** YOUR CODE HERE ***"
if is_leaf(t):
return 1
return sum([num_songs(b) for b in branches(t)])
# Alternate solution
def num_songs(t):
if is_leaf(t):
return 1
leaves = 0
for b in branches(t):
leaves += num_songs(b)
return leaves
Use OK to test your code:
python3 ok -q num_songs
Question 5: Ctrl + F
In order to check if your pyTunes account contains a certain song or category, define the function find
. It takes in a pyTunes tree t
and returns True
if t
contains a either a song or a category called target
and False
otherwise.
def find(t, target):
"""Returns True if t contains a node with the value TARGET and False
otherwise.
>>> my_account = tree('kpop_king',
... [tree('korean',
... [tree('gangnam style'),
... tree('wedding dress')]),
... tree('pop',
... [tree('t-swift',
... [tree('blank space')]),
... tree('uptown funk'),
... tree('see you again')])])
>>> find(my_account, 'korean')
True
>>> find(my_account, 'blank space')
True
>>> find(my_account, 'bad blood')
False
"""
"*** YOUR CODE HERE ***"
if root(t) == target:
return True
if is_leaf(t):
return False
return any([find(b, target) for b in branches(t)])
# Alternate solution
def find(t, target):
if root(t) == target:
return True
for b in branches(t):
if find(b, target):
return True
return False
Use OK to test your code:
python3 ok -q find
Extra Problems
Note: The following questions are in lab05_extra.py.
WWPD?
Question 6: Height & Depth
The depth of a node in a tree is defined as the number of edges between that node and the root. The root has depth 0, its branches have depth 1, and so on.
The height of a tree is the depth of the lowest leaf (furthest away from the root).
Test your understanding of depth and height with OK tests using the following command:
python3 ok -q height_depth -u
Coding Practice
Question 7: Interleave
Write interleave(s0, s1)
, which takes two linked lists
and produces a new linked list with elements of s0
and s1
interleaved. In
other words, the resulting list should have the first element of the s0
, the
first element of s1
, the second element of s0
, the second element of s1
,
and so on.
If the two lists are not the same length, then the leftover elements of the longer list should still appear at the end.
def interleave(s0, s1):
"""Interleave linked lists s0 and s1 to produce a new linked
list.
>>> evens = link(2, link(4, link(6, link(8, empty))))
>>> odds = link(1, link(3, empty))
>>> print_link(interleave(odds, evens))
1 2 3 4 6 8
>>> print_link(interleave(evens, odds))
2 1 4 3 6 8
>>> print_link(interleave(odds, odds))
1 1 3 3
"""
"*** YOUR CODE HERE ***"
# Recursive version
if s0 == empty:
return s1
elif s1 == empty:
return s0
return link(first(s0),
link(first(s1),
interleave(rest(s0), rest(s1))))
# Iterative version
def interleave(s0, s1):
interleaved = empty
while s0 != empty and s1 != empty:
interleaved = link(first(s1), link(first(s0), interleaved))
s0, s1 = rest(s0), rest(s1)
remaining = s1 if s0 == empty else s0
while remaining != empty:
interleaved = link(first(remaining), interleaved)
remaining = rest(remaining)
return reverse_iterative(interleaved)
def reverse_iterative(s):
rev_list = empty
while s != empty:
rev_list = link(first(s), rev_list)
s = rest(s)
return rev_list
Use OK to test your code:
python3 ok -q interleave
Question 8: Filter
Implement a filter_list
function that takes a linked list lst
and
returns a new linked list only containing elements from lst
that satisfy
predicate
. Remember, recursion is your friend!
def filter_list(predicate, lst):
"""Returns a link only containing elements in lst that satisfy
predicate.
>>> lst = link(25, link(5, link(50, link(49, link(80, empty)))))
>>> new = filter_list(lambda x : x % 2 == 0, lst)
>>> print_link(new)
50 80
"""
"*** YOUR CODE HERE ***"
if lst == empty:
return lst
elif predicate(first(lst)):
return link(first(lst), filter_list(predicate, rest(lst)))
else:
return filter_list(predicate, rest(lst))
Use OK to test your code:
python3 ok -q filter_list
Question 9: Add Song
Of course, you should be able to add music to your pyTunes. Write add_song
to add song
to the given category
. You should not be able to add a song under a song or to a category that doesn't exist. See the doctests for examples.
def add_song(t, song, category):
"""Returns a new tree with SONG added to CATEGORY. Assume the CATEGORY
already exists.
>>> indie_tunes = tree('indie_tunes',
... [tree('indie',
... [tree('vance joy',
... [tree('riptide')])])])
>>> new_indie = add_song(indie_tunes, 'georgia', 'vance joy')
>>> print_tree(new_indie)
indie_tunes
indie
vance joy
riptide
georgia
"""
"*** YOUR CODE HERE ***"
if root(t) == category:
return tree(root(t), branches(t) + [tree(song)])
kept_branches = []
for b in branches(t):
kept_branches += [add_song(b, song, category)]
return tree(root(t), kept_branches)
# Alternative Solution
def add_song(t, song, category):
if root(t) == category:
return tree(root(t), branches(t) + [tree(song)])
all_branches = [add_song(b, song, category) for b in branches(t)]
return tree(root(t), all_branches)
Use OK to test your code:
python3 ok -q add_song
Question 10: Delete
You also want to be able to delete a song or category from your pyTunes. Define the function delete
, which takes in a pyTunes tree t
and returns a new tree that is the same as t
except with target
deleted. If target
is a genre, artist, or album, delete everything inside of it. It should not be possible to delete the entire account or root
of the tree. Deleting all the songs within a category should not remove that category.
def delete(t, target):
"""Returns the tree that results from deleting TARGET from t. If TARGET is
a category, delete everything inside of it.
>>> my_account = tree('kpop_king',
... [tree('korean',
... [tree('gangnam style'),
... tree('wedding dress')]),
... tree('pop',
... [tree('t-swift',
... [tree('blank space')]),
... tree('uptown funk'),
... tree('see you again')])])
>>> new = delete(my_account, 'pop')
>>> print_tree(new)
kpop_king
korean
gangnam style
wedding dress
"""
"*** YOUR CODE HERE ***"
kept_branches = []
for b in branches(t):
if root(b) != target:
kept_branches += [delete(b, target)]
return tree(root(t), kept_branches)
# Alternate solution
def delete(t, target):
kept_branches = [delete(b, target) for b in branches(t) if root(b) != target]
return tree(root(t), kept_branches)
Use OK to test your code:
python3 ok -q delete