Lab#7

learning goalsIn this lab you will practice implementing recursive functions where the input is a general Tree, as presented in lecture. You may want to review lecture materials. You should work on these on your own before Thursday, and you are encouraged to then go to your lab where you can get guidance and feedback from your TA . There will be a short quiz during the last 15 minutes of the lab, based on these exercises. set-up Open ?le tree.py and save it under a new sub-directory called lab07. This ?le provides you with a declaration of class Tree, headers and docstrings for the functions you will implement, as well as two utility functions we think you'll ?nd useful: gather lists: There will be cases where you have a list whose elements are sub-lists, and what you'd really like is to concatenate them into a single list. That's what gather lists does. You'll need to save csc148 queue.py in lab07 to make this work. descendants from list: This function makes it less laborious to build a Tree from a list of data. It simply ?lls in the tree, level by level, from a list, until it runs out of elements. Once you have familiarized yourself with the init method for class Tree, you are ready to proceed to the implementation of the functions below. If you have questions, call your TA over. implement list internal This function will list all the values from internal nodes of Tree t. The order of the list is not speci?ed, and there is no need to remove duplicates. Read over the header and docstring for this function in tree.py, but don’t write any implementation until you ?ll in the steps below: 1. One of the examples in our docstring is simple enough not to require recursion. Write out an if... expression that checks for this case, and then returns the correct thing. Include an else... for when the tree is not so easy to deal with. 2. Below is a picture of a larger Tree, with several levels. Consider a function call list internal(t), assuming that t is a reference to the Tree. Are there one or more smaller trees for which it would be helpful to know the list of values that they contain? Which smaller trees are they? Write an example of a function call list internal on one of these smaller trees. You can access these trees through the variable t. Tree(4) Tree(5) Tree(6) ?????? PPPPPP Tree(1...) Tree(7) Tree(8) """ bbb Tree(2...) Tree(3) PPPPPP hhhhhhhhhhhhh Tree(0...) 1 3. Suppose the call in the previous step gives you the correct answer according to the docstring: it returns a list of the values in the tree it is given. How will you combine the solutions for all the smaller instances to get a solution for Tree t itself? Write code to return the correct thing. Hint: You may want gather lists here. Put this code in the else... expression that you created in the ?rst step. Go over these three parts with your TA. After that, ?ll in the implementation in tree.py, and see whether it works. A good approach is to comment-out all the functions you have not yet implemented, so that you will see only doctest results for the one you're working on. arity This function returns the maximum branching factor of this tree. Read over the header and docstring for this function in tree.py, but don’t write any implementation until you ?ll in the steps below: 1. One of the examples in our docstring is simple enough not to require recursion. Write out an if... expression that checks for this case, and then returns the correct thing. Include an else... for when the tree is less easy to deal with. 2. Below is a picture of a larger Tree t, with several levels. Consider a function call that passes t as an argument. Are there one or more smaller trees for which it would be helpful to know the arity (branching factor) of? Which smaller trees are they? Write an example of a function call on one of these smaller trees. You can access these trees through the variable t. Tree(4) Tree(5) Tree(6) ?????? PPPPPP Tree(1) Tree7 Tree8 ??? ZZZ Tree(2) Tree(3) PPPPPP hhhhhhhhhhhh Tree(0) 3. Suppose the call in the previous step gives you the correct answer according to the docstring: it returns the arity of the tree it is given. How will you combine the solutions to all the smaller instances to get a solution for Tree t itself? Write code to return the correct thing. Put this code in the else... expression that you created in the ?rst step. Go over these three parts with your TA. After that, ?ll in the implementation in tree.py, and see whether it works. contains test passer This function returns whether at least one of the values in this tree returns True for the boolean function the user passes in. Read over the header and docstring for this function in tree.py, but don’t write any implementation until you ?ll in the same steps as you did for the last two functions. At the end, review the three steps with your TA before ?lling in the implementation. additional exercises Here are some additional exercises to try out if you ?nish the lab above (they include arity,list internal and contains test passer). As usual, the last 15 minutes of the lab will consist of a 15-minute quiz.