2.14 Trees

← prev up next →

2.14 Trees

A tree is a train
(No other brother could deny)
But with two big butts

2.14.1 Objectives

At the end of this class, you should know:

that the data definition for an ancestor family tree (a fixed-width tree) requires a self-referential compound data structure inside a compound data structure.

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

write the data definition for an ancestor family tree.
write functions over ancestor family trees.

2.14.2 Exercises (due 2011/11/04 08:45:00)

1. Add a blood type attribute to family trees and write a function countType that consumes a bloodtype and a family tree and produces the number of people in the family tree who have the given bloodtype.

2. Write the function properBlueEyedAncestor that consumes a family tree and returns true only if an actual ancestor of the person given has blue eyes. (For example, I have blue eyes, but none of my ancestors do, so this function would return false on my family tree.)

3. Develop a data definition for a binary search tree. A binary search tree is either empty or a node that is a number (the "key"), a string (the "value"), and two binary search trees—"left" and "right". In the left tree, every node’s key is less than its parent. In the right tree, every node’s key is greater than its parent. This means the same key cannot appear in the tree multiple times. You do not need to enforce this property, but you must make use of it.

Develop a function, searchBst, that takes a binary search tree, a key, and a missing string. It should produce the value associated with the key if the key is in the tree or the missing string.

4. Develop the function, inorder, that takes a binary search tree and produces a list of all strings in the tree in the key order. You must make use of the BST property.

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

5. Develop the function, mothers, that takes a family tree and produces a list of the names of all the mothers in the tree.

6. Develop the function, oldest, that takes a family tree and produces the info of the person with the largest age.

2.14.4 Practice Exercises

7. Add a age attribute to family trees and write a function, averageAge, that takes a family tree and returns the average age of everyone in the tree.

8. Develop the function, oldestMatriarch, that takes a family tree and produces the info about the woman furthest back on the matriarchal line.

9. Develop the function, allInfo, that takes a family tree and produces a list of the infos of all the people in the tree.

2.14.5 Notes

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

Family trees

A child is a father, mother, name, blood type, eyes

This is useless, because we can't construct finite family trees

Person is either a child or unknown

blueEyedAncestorHuh : tree -> boolean

countPersons : tree -> int

eyeColors : tree -> ListOfString [use append]

-- Separate tree into info and left/right

allInfos : tree -> ListOfInfo

oldestMatriach : tree -> Info

← prev up next →

1	Introduction
2	Meetings
3	Help
4	Course Software
5	How to Solve Your Problems
6	Assignments and Turn In Policy
7	Exams
8	Your Final Grade
9	Glossary
10	Miscellany

2.1	Introduction to Programming and C+ +
2.2	Expressions and Functions
2.3	Function Composition and Conditionals
2.4	Conditionals and Strings
2.5	Objects
2.6	Objects and Nested Objects
2.7	Methods
2.8	Mixed Data
2.9	Introduction to Lists
2.10	More on Lists
2.11	Producing Lists; Sorting
2.12	Lists of Objects
2.13	More Lists of Objects
2.14	Trees
2.15	Trees and Hierarchy
2.16	More on Hierarchies
2.17	Introduction to Mutation
2.18	Program Design with Mutation
2.19	Changing Structure Contents
2.20	More on Mutation with Structures
2.21	Deep Dark Secrets of C+ +

2.14.1	Objectives
2.14.2	Exercises (due 2011/ 11/ 04 08: 45: 00)
2.14.3	Optional Exercises (due 2011/ 11/ 09 08: 45: 00)
2.14.4	Practice Exercises
2.14.5	Notes