CS 1101: Lab 4

Lab Motivation and Goals

By the end of this lab, you should be able to:

Write data definitions and templates for trees of any fixed-width
Write programs over fixed-width trees

In class this week, we've been working with binary trees and binary search trees. They're called binary trees because they allow for two branches from each node of the tree. There's nothing to stop us from defining a tree with a different (fixed) number of branches, however...a ternary tree allows three branches from each node, for example. In this lab you'll design data definitions, templates, and functions for ternary trees.

Problem Description

An organization maintains an emergency call tree. The person at the root of the tree calls three people to notify them of the emergency. Those three people each call three people, etc. until everyone in the organization has been notified of the emergency.

Each person in the call tree is represented by the following information (in addition to the branches to their three callees): the person's name, list of telephone numbers (cell phone, home phone, work phone, etc.), and position in the organization (for example, vice-president, supervisor, engineer, etc.).

Write a data definition for an emergency call tree, where each node in the tree consists of a person. Provide an example of a call tree that contains at least 5 people.
Provide a template for a call tree.
Develop a function count-supervisors which consumes a call tree and produces the number of people in the tree whose position is supervisor.
Develop a function in-tree? which consumes a call tree and the name of a person and returns true if the named person exists in the tree.
(Problem removed)
Develop a function add-number which consumes a call tree, the name of a person, and a telephone number. The function produces a call tree the same as the original, except that a new telephone number has been added to the end of the named person's list of phone numbers.

Make sure you sign the attendance sheet, and use turnin to turn in the exercises you've completed by the end of the lab period. See you next week!