►Introduction to Programming (Fall 2011)
▼2 Meetings
►2.15 Trees and Hierarchy
On this page:
2.15.1 Objectives
2.15.2 Exercises (due 2011/  11/  09 08:  45:  00)
2.15.3 Optional Exercises (due 2011/  11/  14 08:  45:  00)
2.15.4 Notes
    ← prev  up  next → 

2.15 Trees and Hierarchy

An n-ary tree can

get a little hairy sometimes:

Just follow the steps

2.15.1 Objectives

At the end of this class, you should know:

At the end of this class, you should be able:

2.15.2 Exercises (due 2011/11/09 08:45:00)

Note: Functions over descendant family trees must work correctly on both the tree part AND the list part.

Recall that INFINITY is a double that represents infinity. It requires #include <math.h> to appear at the top of the program.

1. Develop the function howFarRemoved. It determines how far a blue-eyed descendant, if one exists, is removed from the given parent. If the given parent has blue eyes, the distance is 0; if eyes is not blue but at least one its children’s eyes are, the distance is 1; and so on. If no descendant of the given parent has blue eyes, the function returns infinity when it is applied to the corresponding family tree.

2. Develop the function countProperDescendents which consumes a parent and produces the number of descendents, not including the parent.

3. Develop the function generationDescendents which consumes a parent and a generation number and produces a list of all information about descendents in that generation.

4. Develop the function truncate which consumes a parent and a generation number and produces a parent that does not have any descendents in that generation (and thus, obviously, subsequent generations.)

2.15.3 Optional Exercises (due 2011/11/14 08:45:00)

5. Write a function countGenerations which counts the number of generations in a descendant family tree.

6. Generalize howFarRemoved so it takes an eye color argument and does not always check for blue-eye descendents.

2.15.4 Notes

These notes are primarily for my sake, but I don’t see any reason to hide them from you.

family trees were ancestor based

 

hard to learn about children

 

let's switch the arrows

 

but now, people can have multiple children...

 

parent is info, list of children

 

count-blue-eyed : parent -> number

 

has-old-and-blue? : parent number -> boolean [has a blue eyed descedent born before a given data]

 

count-descendents : parent -> number

 

descendents : parent -> ListOfInfo

 

averageAge : parent -> number

 

truncateTree : parent number -> parent [removes everyone after a generation]

 

advanced-ages : parent -> parent [update ages by 1]

    ← prev  up  next →