SUNY Geneseo Department of Computer Science

Problem Set 14 -- Trees in Arrays

CSci 240, Spring 2007

Prof. Doug Baldwin

Due Wednesday, April 25

Purpose

The purpose of this exercise is to consolidate your understanding of how trees can be mapped into arrays.

Background

This exercise deals with the mapping of trees into arrays that is described in section 14.2.4 of our textbook. This mapping was also discussed in the lecture of April 23.

Exercise

Answer the following questions. For all questions, assume that array indices start at 1 -- i.e., that element 0 of a Java-style array is simply ignored, or that arrays don't have an element 0 at all.

Question 1

Here is a linked representation of a tree. Show the corresponding tree as an array.

[A Tree Containing A, F, G, H, K, and M]

Question 2

Here is an array representation of a tree. Show the corresponding linked representation.

Index	Value
1	N
2	G
3	S
4	E
5	J
6	Q
7	W
8	C
9	F

Question 3

A hypothetical array-based tree class represents trees, using an array to hold the items in the tree. This class also provides a notion of a "cursor," i.e., an index that at any given time selects a particular node in the tree; clients can move the cursor to the parent, left child, or right child of the currently selected node. In near-Java pseudocode, the class might be defined, in part, thus:

    class ArrayBasedTree<E> {
        private E[] items;
        private int cursor;
        public void toParent() {
            // change "cursor" so that it indexes the parent of the node it now indexes
        }
        public void toLeft() {
            // Change "cursor" so that it indexes the left child of the node it now indexes
        }
        public void toRight() {
            // Change "cursor" so that it indexes the right child of the node it now indexes
        }
        ...
    }

Show pseudocode for the bodies of toParent, toLeft, and toRight.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Make an appointment to meet with me at some time convenient for you, as long as that time is before the end of the due date above. Meetings only need to be 15 minutes long. You can make an appointment by signing up on the copy of my schedule on the bulletin board outside my office.