## Tutorial 7: Trees and Mutually Recursive Data (October 24-26, 2007)Today's tutorial covers topics from lecutre module 7 on trees and mutually recursive data definitions. One area we're not touching today is binary search trees --- these should be pretty well covered by your assignment, but the general techniques we use here will apply for those structures as well. As usual, the starter code (t7-starter.scm) is, well, a good place to start. - Family Trees
- Drawing the tree
- Counting
- Mothers' Names
- We don't mean radioactive...
- Respect your elders!
- Food, Glorious Food
- Template
- Contains?
- Vegeterian check
- Ingredient weight
- Almost vegetarian
The data definition for family trees ( The code given below (also in the starter code) defines a simple family tree that will later be useful for testing our functions. First, draw the family three represented below with box-and-arrows notation. Which node is the 'root'? (define patrick1 (make-child empty empty 'Patrick 1928 'brown)) (define emma (make-child empty empty 'Emma 1933 'brown)) (define patrick2 (make-child patrick1 emma 'Patrick 1956 'brown)) (define mary (make-child empty empty 'Mary 1908 'green)) (define doris (make-child empty mary 'Doris 1935 'blue)) (define bob (make-child empty empty 'Bob 1930 'blue)) (define susan (make-child bob doris 'Susan 1956 'blue)) (define emily (make-child patrick2 susan 'Emily 1987 'green)) Write a function Write a function Some sociologists use the term 'nuclear family' to refer to a family with some children and exactly two parents. For our purposes, we'll say a family tree represents a nuclear family iff all children in the tree have exactly two or zero parents. Write a predicate function Note that each `child` node corresponding to the oldest ancestor in the tree. If there is a tie, return any one of the oldest.This half of the tutorial will make use of a new mutually-recursive data definition, which is in the starter code and repeated here for convenience: An expression of type An ingredients-list (or 'il') is either Write a template for a function that consumes an expression of type Write a function Notice that each food has a field which indicates whether it is vegetarian. But suppose we want to be really sure that a food contains no non-vegetarian products. To accomplish this, write a function Write a function If one per cent or less of a food is not vegetarian, then probably no one can tell. In this case, we'll call the food 'almost vegetarian'. Write a function |

This file generated Monday, December 17th, 2007 using PLT Scheme and WebIt!