CS230 Data Structures, Wellesley College, Fall 1999

Problem Set 5

Due any time Saturday, October 30

[CS230 Home Page] [Assignments] [Documentation] [Software Installation] [FAQ] [CS Dept.] [CWIS]


In this assigment you will practice writing programs that manipulate trees, both binary trees of integers and Rose trees of strings. To remind you of the contracts for these data structures, they are included in Appendix A and Appendix B of this assignment. Appendix C contains the contract for TokenEnumeration, which you will need to solve Problem 2c.

All code for this assignment can be found in the Trees folder within the CS230 download folder.


Problem 1: IntTree Methods

In this problem, you will define methods that manipulate integer trees. Skeletons for these methods appear in the file PS5IntTreeOps.java.

For this problem, it is helpful to know a number of definitions. The sample tree T below will be used as an example in many of the definitions:

The height of a tree is the longest number of edges from the root to a leaf. The height of T is 3.

A tree is balanced if for every node the height of its two subtrees differ by no more than one.

The level of a tree node is the number of nodes on a path from the node to the root of the tree. For example, in the sample tree T, node A is at level 1, nodes B and C are at level 2, and nodes D, E, F, G are at level 3.

A tree is full if every leaf is at the same level and every non leaf has two non-empty subtrees. The sample tree T is a full tree. The subtree of T consisting of A, B, and C is also full, as is the subtree consisting of just A. However, the subtree consisting of A, B, C, D, and E would not be full, nor would the subtree consisting of A, B, C, D, E, and G.

The binary address of a tree node is defined as follows.

For example, binary addresses of the nodes in T are: A=1, B=2, C=3, D=4, E=5, F=6, G=7.

A tree with n nodes is complete if the set of the binary addresses of all its nodes is the set of the numbers from 1 to n. The sample tree T is complete; in fact, any full tree is complete. The subtree of T consisting of A, B, C, and D is complete, as is A, B, C, D, E and A, B, C, D, E, F. However, the subtree consisting of A, B, C, E is not complete, nor is A, B, C, D, F, or A, B, C, E, F.

The pre-order address of a tree node is an integer (starting at 1) that indicates the order in which that node would be visited in a pre-order traversal of the tree. The pre-order addresses of the nodes in T are: A=1, B=2, D=3, E=4, C=5, F=6, G=7.

Based on the above definitions, write definitions of the following IntTree functions within the class PS5IntTreeOps.

public static boolean isBalanced (IntTree t)
Returns true if t is balanced and false otherwise. You may find it helpful to use the absolute value function Math.abs() in your solution.

public static boolean isFull (IntTree t)
Returns true if t is full and false otherwise. Hint: Do not try to directly use the definition of full given above. Instead, develop a recursive definition of full and use that instead. You may find it helpful to use IntTreeOps.height() to determine the height of a tree. (As noted below, you can invoke this by just writing height() in your code.)

public static boolean isComplete (IntTree t)
Returns true if t is complete and false otherwise. Hint: Do not try to directly use the definition of complete given above. Instead, develop a recursive definition of complete and use that instead. You may find it helpful to use IntTreeOps,height() to determine the height of a tree, and PS5IntTreeOpsAnswers.isFull() to determine whether or not a tree is full (this will decouple your solution for isComplete() from your solution to isFull().)

public static IntTree addBinaryAddress (IntTree t)
Returns a new tree that has the same structure as t where the value at every node has been incremented by the binary address of the node. Hint: define addBinaryAddress in terms of an auxiliary recursive method that takes two arguments -- a tree and a binary address -- and returns a tree.

public static IntTree addPreorderAddress (IntTree t)
Returns a new tree that has the same structure as t where the value at every node has been incremented by the preorder address of the node. Hint: define addPreorderAddress in terms of an auxiliary recursive function that takes two arguments -- a tree and a pre-order address -- and returns a tree. You may find it helpful to use the IntListOps.countNodes() method, which counts the number of nodes in a tree.

Notes:

Submission Details: Your hardcopy submission for this problem should be your final version of PS5IntTreeOps.java. Your softcopy submission for all five problems should be your final version of the Trees folder.


Problem 2: RoseTree Methods

Binary trees aren't the only game in town. As noted in class, there are many different categories of tree-like data structures. Here you will practice with one briefly mentioned in class: Rose trees. A Rose tree is either a content-bearing leaf , or a node that has a tag and a list of subtrees.

As defined here, a Rose tree is a persistent data structures (also called immutable, non-destructive, or functional data structures); this means that there are no operations to change an existing tree, only operations to create new trees. Later in the semester we will study mutable trees.

You should study the contract for the RoseTree class in Appendix B. This contract mentions the RoseTreeList class, which is just like IntList or ObjectList except that every node is guaranteed to have a RoseTree at its head.

Rose trees are useful for representing tree structures where (1) leaves hold data and (2) the branching factor can differ from node to node. For instance, they are handy for representing a file directory structure on a computer. In this case, a node represents a directory or folder, where the tag is a string that is the name of the directory, and a leaf represents a file, where the contents is a string that is the name of the file. Below is a graphical depiction of a simple file structure as a Rose tree, where nodes (directories) are represented as ovals and leaves (files) as rectangles. The node labelled "/" is called the "root" of the file system. Note that a directory can contain both files and other directories. A directory may also be empty.

 

 

As an example of manipulating Rose trees, consider the following methods, which finds the height of a Rose tree. The height of a Rose tree is defined as the length of the longest path to either (1) a leaf or (2) a node with no subtrees. For example, the directory structure depicted above has height 5.

	public static int height (RoseTree rtree) {
	// Returns the height of a RoseTree.
	// The height is the length of the longest path from the root 
     // to a leaf or to a node with no subtrees.
		if (R.isRleaf(rtree) || RL.isEmpty(R.subtrees(rtree))) {
			return 0; 
		} else {
			return 1 + maxHeightList(R.subtrees(rtree));
		}
	}
 
	public static int maxHeightList (RoseTreeList rtrees) {
	// Returns the maximum of the heights of rtrees
		if (RL.isEmpty(rtrees)) {
			return 0; 
		} else {
			return Math.max(height(RL.head(rtrees)), 
                                maxHeightList(RL.tail(rtrees)));
		}
	}

Note that the height is determined by a pair of mututally recursive methods: one that finds the height of a Rose tree, and the other that finds the maximum of the heights of a list of Rose trees. It is common when writing Rose tree operations to have two such methods, one of which takes a RoseTree parameter, and the other of which takes a RoseTreeList parameter.

Below, you are asked to write three methods that manipulate Rose trees. Here are some general notes that apply to all the problems:

a. countRnodes

Implement the following method:

public static int countRnodes (RoseTree rtree)
Returns the number of nodes in rtree.

For example, the directory tree shown above has 15 nodes.

 

b. paths

Implement the following method:

public static ObjectList paths (RoseTree rtree)
Returns a list of all paths from the root of rtree down to any node or leaf in rtree. In this context, a path is a list of strings indicating the sequence of tags (in the case of nodes) or contents (in the case of a leaves) visited when the path is followed from the root downward.

For example, assuming that the contents of a directory are stored in alphabetical order, the result of invoking paths on the usr subdirectory of the above directory tree should yield:

[[usr],
 [usr, bin],
 [usr, bin, grep],
 [usr, bin, ls],
 [usr, local],
 [usr, local, bin],
 [usr, local, bin, emacs],
 [usr, local, bin, netscape],
 [usr, local, src],
 [usr, users],
 [usr, users, astracks],
 [usr, users, astracks, .login],
 [usr, users, astracks, public_html],
 [usr, users, astracks, public_html, index.html],
 [usr, users, astracks, public_html, me.jpg],
 [usr, users, vtorr],
 [usr, users, vtorr, .login],
 [usr, users, vtorr, public_html]
 ]

Notes:

c. readTree

In class, we studied a recursive approach to translating a parenthesized string representation of an IntTree into an instance of the IntTree class. Here you will implement a similar approach for translating parenthesized string representations of Rose trees into instances of the RoseTree class. For simplicity, we will only consider Rose trees where the node tags and leaf contents are strings, where the strings do not contain any whitespace characters (such as spaces, tabs, or newlines). Under these assumptions, we assume the following string representation of Rose trees:

For instance, with this representation, the users subdirectory in the directory tree example can be represented as the following string:

"(users (astracks .login (public_html index.html me.jpg)) (vtorr .login (public_html)))"

Note that the representation distinguishes between empty files (such as (public_html)) and files (such as .login); the former is parenthesized while the latter is not.

Recall that the translation of IntTree representations was done in two stages:

  1. Convert the string into a sequence of tokens, as implemented by the TokenEnumeration class. Each token is a string that is either "(", ")", or a string containing no whitespace characters.
  2. Parse the tokens from the string into an instance of the IntTree class.

Before continuing with this problem, you should study the implementation of the read() and readTree() methods in the file IntTreeOps.java. These refer to the TokenEnumeration class, the contract for which appears in Appendix C.

In this problem, you are provided with the read() method for translating a string representation of a RoseTree into an instance of the RoseTree class:

	public static RoseTree read (String s) {
	// Parse a string representation of a RoseTree into a RoseTree object.
	// Returns null if string not of the right form.
		TokenEnumeration tokens = new TokenEnumeration(s); 
		RoseTree r = readTree(tokens);
		if (tokens.hasMoreElements()) {
			// There is still unread input; it's not of the right form!
			throw new RoseTreeException("read: Unread tokens");
		} else {
			return r;
		}
	}

Your goal is to implement the following readTree() method, which is invoked by read():

public static RoseTree readTree (TokenEnumeration tokens)
Consumes the initial tokens of the enumeration corresponding to a Rose tree,
and returns an instance of the RoseTree class representing this Rose tree.
After readTree returns, tokens should contain any tokens not consumed by the process.
If the token sequence is not of the right form, readTree() should throw a
TreeException error indincating that there is a problem.

Notes:

Submission Details: Your hardcopy submission for this problem should be your final version of PS5RoseTreeOps.java. Your softcopy submission for all XXX problems should be your final version of the Trees folder.


Appendix A: IntTree API

Instances of the IntTree class are binary trees, where a binary tree is either a leaf, or a node that has an integer value and left and right subtrees. As defined here, an IntTree is a persistent data structures (also called immutable, non-destructive, or functional data structures); this means that there are no operations to change an existing tree, only operations to create new trees. Later in the semester we will study mutable trees.

The ObjectTree class is similar except that the value at any node is not an integer but any Java object.

public static IntTree leaf()
Returns the leaf of a binary tree.

public static IntTree node(int v, IntTree l, IntTree r)
Returns a binary tree node with value v, left subtree l, and right subtree r.

public static boolean isLeaf(IntTree t)
Returns true if t is a leaf, and false if it is a node.

public static int value (IntTree t)
Returns the value of a binary tree node. Throws an IntTreeException if t is a leaf.

public static IntTree left (IntTree t)
Returns the left subtree of a binary tree node. Throws an IntTreeException if t is a leaf.

public static IntTree right (IntTree t)
Returns the right subtree of a binary tree node. Throws an IntTreeException if t is a leaf.


Appendix B: RoseTree API

Instances of the RoseTree class are Rose trees, where a Rose Tree is either a content-bearing leaf , or a node that has a tag and a list (a RoseTreeList) of subtrees. As defined here, a RoseTree is a persistent data structures (also called immutable, non-destructive, or functional data structures); this means that there are no operations to change an existing tree, only operations to create new trees. Later in the semester we will study mutable trees.

A RoseTreeList supports the standard operations for persistent lists. It is distinguished from ObjectList in that the head of every node is a RoseTree, not an arbitrary Java object.

public static RoseTree rleaf (Object contents)
Creates a Rose tree leaf with the given contents.

public static RoseTree rnode (Object tag, RoseTreeList subtrees)
Creats a Rose Tree node with the given tag and list of subtrees.

public static boolean isRleaf (RoseTree rtree)
Returns tree if rtree is a leaf, and false if it is a node.

public static Object contents (RoseTree rtree)
Returns the contents of a Rose tree leaf. Throws a RoseTreeException if rtree is a node.

public static Object tag (RoseTree rtree)
Returns the tag of a Rose tree node. Throws a RoseTreeException if rtree is a leaf.

public static RoseTreeList subtrees (RoseTree rtree)
Returns the subtrees of a Rose tree node as a RoseTreeList. Throws a RoseTreeException if rtree is a leaf.


Appendix C: TokenEnumeration API

An instance of the TokenEnumeration class represents a sequence of tokens, where a token is a string that it either "(", ")", or a string containing no whitespace characters (e.g., spaces, tabs, or newline characters). The purpose of the TokenEnumeration class is to abstract over the process of analyzing a string into a sequence of tokens.

public TokenEnumeration(String s)
Returns an enumeration of the tokens that result from analyzing s.

public boolean hasMoreElements()
Returns true if this enumeration has more tokens, and false otherwise.

public Object nextElement()
Removes the first token from the enumeration and returns it.

public Object peekElement()
Returns the first token from the enumeration without removing it. Successive calls to peekElement without intervening calls to nextElement will always return tokens that are .equals().