CIS 256 Lab 3

Goal: to give you experience with general trees and encapsulation. The trees

we use in this lab use the SibTree data structure described in Lecture

(which you should review now). SibTrees are designed to ensure that the SibTree and

SibTreeNode invariants (which are

written out in their respective files) cannot be violated.

All the code is in the tree package. You can compile it from your lab10

directory with "javac -g tree/*.java". Extensive test code is provided and

can be run with "java tree.SibTree".

Familiarize yourself with the fields and methods of the SibTree and SibTreeNode

classes. SibTree has two fields, one inherited from the Tree abstract class.

int size; // The number of SibTreeNodes in the SibTree.

SibTreeNode root; // The node that serves as the root of the tree.

SibTreeNode has six fields, two inherited from the TreeNode abstract class.

Object item; // Item stored at this SibTreeNode.

boolean valid; // True if and only if this is a valid node.

SibTree myTree; // The SibTree that contains this node.

SibTreeNode parent; // This node's parent.

SibTreeNode firstChild; // This node's first (leftmost) child.

SibTreeNode nextSibling; // This node's next sibling to the right.

As with the Homework 5 lists, the Tree class defines certain nodes to be

invalid. In constrast to the Homework 5 lists, valid and invalid nodes are

distinguished solely through the state of the "valid" field. When a TreeNode

is removed from a tree, it becomes invalid. Methods like parent(), child(),

and nextSibling() return an invalid node (never null!) if no such node exists.

You may create an invalid node by calling the zero-parameter SibTreeNode()

constructor. You may test whether a node n is valid by calling

n.isValidNode().

Every valid SibTreeNode is in some tree, specified by the "myTree" field.

Your task is to implement the parent(), insertChild(), and removeLeaf() methods

of the SibTreeNode class. After you write each one, you may use the test code

to check your progress.

Part I: Accessing a Node's Parent (1 point)

--------------------------------------------

Fill in the body of the parent() method in SibTreeNode.java. parent() returns

the SibTreeNode that is the parent of "this" SibTreeNode. If "this" node is

the root, return an invalid node.

Throw an InvalidNodeException if "this" node is not valid.

Part II: Inserting New Children (3 points)

-------------------------------------------

Fill in the body of insertChild(). insertChild() takes two parameters: an

item and an integer c. Create a new child that is the cth child (from the

left) of "this" node, and references the item indicated. Existing children

numbered c or higher are shifted one place to the right to accommodate. If

c < 1, act as if c is 1. If "this" node has fewer than c children, the new

node is the last sibling.

Don't forget that SibTrees have a "size" field that needs to be updated.

Throw an InvalidNodeException if "this" node is not valid.

BONUS Part III: Removing a Leaf (1 bonus point)

------------------------------------------------

Fill in the body of removeLeaf(), which removes "this" node from the tree if it

is a leaf, and does nothing if it is not a leaf. Upon completion, "this" node

should be invalid.

As always, throw an InvalidNodeException if "this" node is not valid.

Check-off

---------

You'll receive points for each part that runs without printing any

error messages. You can receive up to 5 points out of 4.

--------------------------------------------------------------------------------------------

/* InvalidNodeException.java */

package tree;

/** * Implements an Exception that signals an attempt to use an invalid ListNode. */

public class InvalidNodeException extends Exception { protected InvalidNodeException() { super(); }

protected InvalidNodeException(String s) { super(s); } }

-------------------------------------------------------------------

/* SibTree.java */

package tree;

/** * The SibTree class implements general trees using linked nodes. Each node * has pointers to its parent, its first (leftmost) child, and its sibling to * the immediate right. * @author Jonathan Shewchuk */

public class SibTree extends Tree {

/** * (inherited) size is the number of items in the tree. * root is the tree's root node. **/

SibTreeNode root;

/** * ADT implementation invariants: * * Definition: SibTreeNode y is a "sibling of" SibTreeNode x if * 1) x.nextSibling == y, or * 2) y is a sibling of x.nextSibling * Definition: SibTreeNode y is a "descendant of" SibTreeNode x if * 1) x == y, or * 2) y is a descendant of x.firstChild, or * 3) y is a descendant of some SibTreeNode z and * z is a sibling of x.firstChild * Definition: a SibTreeNode x is said to be "in" SibTree "this" if * x is a descendant of this.root * * 1) if root != null, then root.valid == true, and root.parent == null. * 2) for any SibTreeNode x in SibTree "this", x.valid == true. * 3) for any SibTreeNodes x and y in SibTree "this", if * x.firstChild == y or y is a sibling of x.firstChild, then * y.parent == x. * 4) for any SibTreeNodes x and y in SibTree "this", if x.parent == y, then * y.firstChild == x or x is a sibling of y.firstChild. * 5) for any SibTreeNode x in SibTree "this", if x.parent == null, then * x == root. * 6) "size" is the number of nodes in SibTree "this". * 7) for any SibTreeNode x in SibTree "this", x satisfies all the * invariants of SibTreeNode (listed in SibTreeNode.java). */

/** * Construct an empty SibTree. */ public SibTree() { root = null; size = 0; }

/** * Construct a one-node SibTree. */ public SibTree(Object item) { root = new SibTreeNode(this, item); size = 1; }

/** * root() returns the root node, if one exists. Returns an invalid node if * the tree is empty. */ public TreeNode root() { if (root == null) { return new SibTreeNode(); } else { return root; } }

/** * insertRoot() inserts a node containing "item" at the root of the tree. * If a root already exists, it becomes a child of the new node. */ public void insertRoot(Object item) { SibTreeNode newRoot = new SibTreeNode(this, item); newRoot.firstChild = root; if (root != null) { root.parent = newRoot; } root = newRoot; size++; }

/** * toString() returns a string representation of the SibTree. */ public String toString() { return preorderString(root, 0); }

private String preorderString(SibTreeNode currentNode, int depth) { if (currentNode == null) { return ""; } String s = ""; for (int i = 0; i < depth; i++) { s = s + " "; } return s + currentNode.item + " " + preorderString(currentNode.firstChild, depth + 1) + preorderString(currentNode.nextSibling, depth); }

/** * main() contains mounds and mounds of icky test code. */ public static void main(String[] args) { TreeNode r, r1, r2, r3, r31, r32;

// Create two-node tree. Tree t = new SibTree(new Integer(11)); t.insertRoot(new Integer(1)); System.out.println("Creating 2-node tree.");

// Reference the nodes. r = t.root(); r1 = null; try { r1 = r.child(1); } catch (InvalidNodeException e) { }

// Does parent() work? System.out.println("Testing parent()."); try { if (r != r1.parent()) { System.out.println(" ERROR: parent of root node's child is" + " not the root, but should be."); } if (r.parent() == null) { System.out.println(" ERROR: parent() returned null."); } else if (r.parent().isValidNode()) { System.out.println(" ERROR: parent() of root is valid," + " but shouldn't be."); } } catch (Exception e) { System.out.println(" ERROR: parent() threw interrupt on valid node."); } try { TreeNode stp = r.child(2).parent(); System.out.println(" ERROR: parent() failed to throw exception on" + " invalid node."); } catch (InvalidNodeException e) { }

// Add more nodes to tree. System.out.println(" Testing insertChild()." + " Adding two more nodes to the 2-node tree."); r2 = null; r3 = null; r31 = null; r32 = null; try { r.insertChild(new Integer(13), 1000); r.insertChild(new Integer(12), 2); r2 = r.child(2); r3 = r.child(3); if (((Integer) r2.item()).intValue() != 12) { System.out.println(" ERROR: Second child of root does not contain" + " the correct key, 12."); } if (((Integer) r3.item()).intValue() != 13) { System.out.println(" ERROR: Third child of root does not contain" + " the correct key, 13."); } if (r2.parent() != r) { System.out.println(" ERROR: Second child of root does not think" + " the root is its parent."); } if (r3.parent() != r) { System.out.println(" ERROR: Third child of root does not think" + " the root is its parent."); } if (r2.nextSibling() != r3) { System.out.println(" ERROR: Second child of root does not think" + " the root's third child is its next sibling."); } if (r3.nextSibling().isValidNode()) { System.out.println(" ERROR: Third child of root thinks it has" + " a next sibling."); }

System.out.println("Adding two more nodes to the 4-node tree."); r3.insertChild(new Integer(132), 1); r3.insertChild(new Integer(131), 1); r31 = r3.child(1); r32 = r3.child(2); if (((Integer) r31.item()).intValue() != 131) { System.out.println(" ERROR: Node r31 does not contain" + " the correct key, 131."); } if (((Integer) r32.item()).intValue() != 132) { System.out.println(" ERROR: Node r32 does not contain" + " the correct key, 132."); } if (r31.parent() != r3) { System.out.println(" ERROR: Node r31 does not think" + " Node r3 is its parent."); } if (r32.parent() != r3) { System.out.println(" ERROR: Node r32 does not think" + " Node r3 is its parent."); } if (r31.nextSibling() != r32) { System.out.println(" ERROR: Node r31 does not think" + " Node r32 is its next sibling."); } if (r32.nextSibling().isValidNode()) { System.out.println(" ERROR: Node r32 thinks it has a next sibling."); } } catch (Exception e) { System.out.println(" ERROR: unexpected exception while adding and" + " testing nodes."); // System.exit(1); } try { if (r.parent() == null) { System.out.println(" ERROR: parent() returned null."); } else { r.parent().insertChild(new Integer(0), 1); System.out.println(" ERROR: insertChild() failed to throw" + " exception on invalid node."); } } catch (InvalidNodeException e) { } if (t.size() != 6) { System.out.println(" ERROR: tree size is " + t.size() + " but should be 6."); }

System.out.println("The tree looks like this:"); System.out.print(t.toString()); System.out.println("[The above sequence should be" + " 1, 11, 12, 13, 131, 132.]");

// Remove nodes from tree. System.out.println(" Testing removeLeaf()." + " Removing one node from 6-node tree."); try { r1.removeLeaf(); } catch (Exception e) { System.out.println(" ERROR: unexpected exception while removing."); } if (r1.isValidNode()) { System.out.println(" ERROR: the removed node should be invalid."); } if (t.size() != 5) { System.out.println(" ERROR: tree size is " + t.size() + " but should be 5."); } try { r1 = r.child(1); } catch (Exception e) { } if (r1 != r2) { System.out.println(" ERROR: after deleting Node r1, Node r2 has" + " not become the first child of the root."); }

System.out.println("Removing another node from 5-node tree."); try { r32.removeLeaf(); } catch (Exception e) { System.out.println(" ERROR: unexpected exception while removing."); } if (t.size() != 4) { System.out.println(" ERROR: tree size is " + t.size() + " but should be 4."); } try { r32 = r3.child(2); } catch (Exception e) { } if (r32.isValidNode()) { System.out.println(" ERROR: Node r3 still has a second child."); } try { r32 = r31.nextSibling(); } catch (Exception e) { } if (r32.isValidNode()) { System.out.println(" ERROR: Node r31 still has a next sibling."); }

System.out.println("Attempting to remove non-leaf node from 4-node tree."); System.out.println(" Operation should have no effect."); try { r3.removeLeaf(); if (!r3.isValidNode()) { System.out.println(" ERROR: removed non-leaf is invalid."); } if (r.child(2) != r3) { System.out.println(" ERROR: removed non-leaf is no longer" + " the root's second child."); } } catch (Exception e) { System.out.println(" ERROR: removeLeaf() threw exception."); }

System.out.println("Attempting to remove invalid node from 4-node tree."); try { r32.removeLeaf(); System.out.println(" ERROR: removeLeaf() failed to throw exception."); } catch (InvalidNodeException e) { }

System.out.println("The tree looks like this:"); System.out.print(t.toString()); System.out.println("[The above sequence should be" + " 1, 12, 13, 131.]");

System.out.println("Removing remaining nodes from 4-node tree."); try { r31.removeLeaf(); r2.removeLeaf(); r3.removeLeaf(); r.removeLeaf(); } catch (Exception e) { System.out.println(" ERROR: unexpected exception while removing."); } if (t.size() != 0) { System.out.println(" ERROR: tree size is " + t.size() + " but should be zero."); } r = t.root(); if (r.isValidNode()) { System.out.println(" ERROR: the root should be invalid."); } }

}

----------------------------------------------------------------------------

/* SibTreeNode.java */

package tree;

/** * A SibTreeNode object is a node in a SibTree (sibling-based general tree). * @author Jonathan Shewchuk */

class SibTreeNode extends TreeNode {

/** * (inherited) item references the item stored in this node. * (inherited) valid is true if and only if this is a valid node in some * Tree. * myTree references the Tree that contains this node. * parent references this node's parent node. * firstChild references this node's first (leftmost) child. * nextSibling references this node's next sibling. * * DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS. */

/** * ADT implementation invariants: * 1) if valid == true, myTree != null. * 2) if valid == true, then this is a descendent of myTree.root. * 3) if valid == true, myTree satisfies all the invariants of a * SibTree (listed in SibTree.java). */

protected SibTree myTree; protected SibTreeNode parent; protected SibTreeNode firstChild; protected SibTreeNode nextSibling;

/** * Construct a valid SibTreeNode referring to a given item. */ SibTreeNode(SibTree tree, Object item) { this.item = item; valid = true; myTree = tree; parent = null; firstChild = null; nextSibling = null; }

/** * Construct an invalid SibTreeNode. */ SibTreeNode() { valid = false; }

/** * children() returns the number of children of the node at this position. * WARNING: Does not run in constant time. Actually counts the kids. */ public int children() { if (isValidNode()) { int count = 0; SibTreeNode countNode = firstChild; while (countNode != null) { count++; countNode = countNode.nextSibling; } return count; } else { return 0; } }

/** * parent() returns the parent TreeNode of this TreeNode. Throws an * exception if `this' is not a valid node. Returns an invalid TreeNode if * this node is the root. */ public TreeNode parent() throws InvalidNodeException { // REPLACE THE FOLLOWING LINE WITH YOUR SOLUTION TO PART I. return null; }

/** * child() returns the cth child of this TreeNode. Throws an exception if * `this' is not a valid node. Returns an invalid TreeNode if there is no * cth child. */ public TreeNode child(int c) throws InvalidNodeException { if (isValidNode()) { if (c < 1) { return new SibTreeNode(); } SibTreeNode kid = firstChild; while ((kid != null) && (c > 1)) { kid = kid.nextSibling; c--; } if (kid == null) { return new SibTreeNode(); } else { return kid; } } else { throw new InvalidNodeException(); } }

/** * nextSibling() returns the next sibling TreeNode to the right from this * TreeNode. Throws an exception if `this' is not a valid node. Returns * an invalid TreeNode if there is no sibling to the right of this node. */ public TreeNode nextSibling() throws InvalidNodeException { if (isValidNode()) { if (nextSibling == null) { return new SibTreeNode(); } else { return nextSibling; } } else { throw new InvalidNodeException(); } }

/** * insertChild() inserts an item as the cth child of this node. Existing * children numbered c or higher are shifted one place to the right * to accommodate. If the current node has fewer than c children, * the new item is inserted as the last child. If c < 1, act as if c is 1. * * Throws an InvalidNodeException if "this" node is invalid. */ public void insertChild(Object item, int c) throws InvalidNodeException { // FILL IN YOUR SOLUTION TO PART II HERE. }

/** * removeLeaf() removes the node at the current position from the tree if * it is a leaf. Does nothing if `this' has one or more children. Throws * an exception if `this' is not a valid node. If 'this' has siblings to * its right, those siblings are all shifted left by one. */ public void removeLeaf() throws InvalidNodeException { // FILL IN YOUR SOLUTION TO PART III HERE. }

}

------------------------------------------------------------------------------------------------------------------------

/* Tree.java */

package tree;

/** * A Tree is a mutable ADT for general trees (wherein a node can have any * number of children). * @author Jonathan Shewchuk */

public abstract class Tree {

/** * size is the number of items in the tree. **/

protected int size;

/** * isEmpty() returns true if this Tree is empty, false otherwise. * * @return true if this Tree is empty, false otherwise. * * Performance: runs in O(1) time. **/ public boolean isEmpty() { return size == 0; }

/** * size() returns the size of this Tree. * * @return the size of this Tree. * * Performance: runs in O(1) time. **/ public int size() { return size; }

/** * root() returns the root node, if one exists. Returns an invalid node if * the tree is empty. */ public abstract TreeNode root();

/** * insertRoot() inserts a node containing "item" at the root of the tree. * If a root already exists, it becomes a child of the new node. */ public abstract void insertRoot(Object item);

}

------------------------------------------------------------------------------------------------

/* TreeNode.java */

package tree;

/** * A TreeNode object is a mutable node in a tree. No implementation is * provided. * * DO NOT CHANGE THIS FILE. * @author Jonathan Shewchuk */

public abstract class TreeNode {

/** * item references the item stored in this node. * valid is true if and only if this is a valid node in some Tree. * * DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS. */

protected Object item; protected boolean valid;

/** * isValidNode returns true if this node is valid; false otherwise. * * @return true if this node is valid; false otherwise. * * Performance: runs in O(1) time. */ public boolean isValidNode() { return valid; }

/** * item() returns this node's item. If this node is invalid, * throws an exception. * * @return the item stored in this node. * * Performance: runs in O(1) time. */ public Object item() throws InvalidNodeException { if (isValidNode()) { return item; } else { throw new InvalidNodeException(); } }

/** * setItem() sets this node's item to "item". If this node is invalid, * throws an exception. * * Performance: runs in O(1) time. */ public void setItem(Object item) throws InvalidNodeException { if (isValidNode()) { this.item = item; } else { throw new InvalidNodeException(); } }

/** * children() returns the number of children of the node at this position. */ public abstract int children();

/** * parent() returns the parent TreeNode of this TreeNode. Throws an * exception if `this' is not a valid node. Returns an invalid TreeNode if * this node is the root. */ public abstract TreeNode parent() throws InvalidNodeException;

/** * child() returns the cth child of this TreeNode. Throws an exception if * `this' is not a valid node. Returns an invalid TreeNode if there is no * cth child. */ public abstract TreeNode child(int c) throws InvalidNodeException;

/** * nextSibling() returns the next sibling TreeNode to the right from this * TreeNode. Throws an exception if `this' is not a valid node. Returns * an invalid TreeNode if there is no sibling to the right of this node. */ public abstract TreeNode nextSibling() throws InvalidNodeException;

/** * insertChild() inserts an item as the cth child of this node. Existing * children numbered c or higher are shifted one place to the right * to accommodate. If the current node has fewer than c children, * the new item is inserted as the last child. If c < 1, act as if c is 1. */ public abstract void insertChild(Object item, int c) throws InvalidNodeException;

/** * removeLeaf() removes the node at the current position from the tree if * it is a leaf. Does nothing if `this' has one or more children. Throws * an exception if `this' is not a valid node. If 'this' has siblings to * its right, those siblings are all shifted left by one. */ public abstract void removeLeaf() throws InvalidNodeException;

}

Thank you very much for all the help!