CS367 Homework 6
Lecture 3, Fall 2015
Due by 11:59 pm on Friday, November 13 (not accepted late)

Questions

Homework assignments must be done individually. Collaboration on homework assignments is not allowed.

Question 1:

Assume that binary trees are implemented using a BinaryTreenode class that includes the following fields and methods:

// fields
private T data;
private BinaryTreenode<T> left, right;
 
// methods
public T getData() { return data; }
public BinaryTreenode<T> getLeft()  { return left; }
public BinaryTreenode<T> getRight() { return right; }
public void setLeft(BinaryTreenode<T> newL)  { left  = newL; }
public void setRight(BinaryTreenode<T> newR) { right = newR; }

Assume that items in a binary tree can be compared with the equals method. For this question you will write the countMatches method whose header is given below.

public int countMatches(BinaryTreenode<T> n, T item)

The method should return the number of items in the binary tree that are equal to the given object item, 0 if the tree is empty, or -1 if item is null. The method is recursively defined as:

• The count of matches is 0 if the tree is empty.
• The count of matches is -1 if item is null.
• The count of matches in a tree with at least one node is the count of matches in the left subtree plus the count of matches in the right subtree, plus 1 if the data in the node itself is equal to item.

Question 2:

Assume that general trees are implemented using a Treenode class that includes the following fields and methods:

// fields
private T data;
private List<Treenode<T>> children;
 
// methods
public T getData() { return data; }
public List<Treenode<T>> getChildren() { return children; }

For efficiency, use an iterator to access the children in the list returned by the method getChildren (as we've done in lecture). You may assume that getChildren never returns null: if a node is a leaf, then getChildren will return a non-null list containing zero elements.

Write the countNonLeaves method whose header is given below.

public int countNonLeaves(Treenode<T> n)

The method should return the number of nodes in the general tree that are not leaf nodes.

Part A: First, complete the English descriptions of the base and recursive cases, like what was given above for Question 1.

• The number of non-leaves is 0 if the tree is empty .
• The number of non-leaves in a tree with one node is (fill in your answer here)
• The number of non-leaves in a tree with more than one node is (fill in your answer here)

Part B: Now write the countNonLeaves method.

Handing in

Please include your name at the top your file.

Put your answers to the questions into one file named Homework6 with the appropriate file extension, e.g., Homework6.pdf (see File Format for acceptable file formats).

Electronically submit your work to the Homework 6 Dropbox on Learn@UW.