Laboratory Exercise

Introduction to Trees

Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004

Purpose

Prerequisites

Background

In lectures, we discussed a way of using binary trees to explicitly represent decision trees in which every decision has two possible outcomes. Your task in this lab is to code that representation of decision trees, and to analyze some of its properties.

To represent a decision tree, let every node in a binary tree contain a string. For non-leaf nodes, this string will be a question with a yes-or-no answer. The node's left subtree will contain questions to ask if the answer to the question is "yes", the right subtree will contain questions to ask if the answer is "no." For leaf nodes, the string is a decision.

To make a decision using such a decision tree, you work your way down it from the root. For each non-leaf you come to, print the question in that node, read an answer from the user, and recursively make a decision using either the left subtree (if the answer was "yes") or the right subtree (if the answer was "no"). When you finally reach a leaf, simply print the string it contains as the decision that was reached.

To add decisions to a decision tree, follow the algorithm for making a decision, except that when you reach a leaf, allow the user to enter a new yes-no question that will distinguish between the leaf and the new decision the user wants to add. Replace the leaf with a new node containing this question; the original leaf is either the left or right child of this new node (depending on whether the original decision corresponds to a "yes" or "no" answer to the new question), and the new decision is the new node's other child.

Exercise

Define a DecisionTree subclass of OrderedTree that implements the above decision-making and tree-growing algorithms.