CS 1101 - Aterm 07
Homework 9 - Ancestor Trees
Due: Friday, September 21 at 11:59pm
Read the expectations on homework.
Also, read Section 14.2 in the text.
Assignment Goals
- To make sure you can write programs over ancestor trees, specifically,
binary search trees.
The Assignment
An important variant of the ancestor tree is the binary search tree
(section 14.2). In a binary search tree, the tree is organized such that
the key value in a given node of the tree meets the condition that all
key values in the node's left subtree are less than the key value in the given
node, and all the key values in the node's right subtree are greater than
the key value in the given node. This organization makes the task of
searching the tree much more efficient (in terms of the number of comparisons
needed to find a given value) than would be the case for a regular
ancestor tree.
- Write a data definition for a binary search tree that models student
final grade records. Each node in the tree
contains a unique student id number (key value), the student's name, and the
student's final grade (a letter grade such as A, B, C, or NR).
- Provide an example of binary search tree containing at least 4 student
records.
- Write the template for the data definition in Problem 1.
- Write a function
student-in-tree? which consumes a binary search tree and a student id
number and returns a boolean. The function returns true if the given id
exists in the tree, and returns false otherwise. Your function should be
written efficiently, such that it performs as few comparisons as is
necessary.
- Write a function
count-As. The function consumes a
binary search tree and returns the number of students in the tree whose final
grade is A.
- Write a function
list-ids-in-order. The function consumes a
binary search tree and produces a list of the ids of students in the tree,
such that the list of ids is in ascending numeric order.
What to Turn In
Using web-based turnin,
turn in a single file hw9.scm containing
all code and documentation for this assignment. Make sure both partners' names and wpi login names appear in a comment at the top of the file.