Using a Binary Tree ADT...

We developed the In Order and Post Order traversals of the binary tree using the Pre Order traversal as a template.

You need to decide which of those traversal methods to use to print an indented list, such as you might find in a file directory listing or table of contents, of the elements of the tree.

Create a new method, indented(), to implement this algorithm. The method will print the current element preceded by a fixed number of spaces to indicate the relative position within the tree with respect to parent and child nodes. E.g., the root node will be indented 0 spaces, its children will be indented 2 spaces relative to the parent, and so forth.

You will need six of the .java files from below for your answer. Use the TreeDriver.java attached to this assignment. However, only complete the TreeDriver.java file.

TreeDriver.java

public class TreeDriver { /** * This method constructs an arithmetic expression tree of an expression s in * prefix notation by simply calling the recursive version of the same method. * * Prefix Notation: Operators are written before the operands, e.g + 3 4 */ public static void preorderAET(LinkedBinaryTree T, String s) { preorderAET(T, T.addRoot(null), s); } /** * This method recursively constructs an arithmetic expression tree of an * arithmetic expression s in prefix notation starting at a position v. */ public static String preorderAET(LinkedBinaryTree T, Position v, String s) { if (s.length() == 0) return ""; if (s.charAt(0) == ' ') return preorderAET(T, v, s.substring(1)); // Skip spaces. else if (Character.isDigit(s.charAt(0))) { T.set(v, Character.valueOf(s.charAt(0))); return s.substring(1); } else { T.set(v, Character.valueOf(s.charAt(0))); T.addLeft(v, null); T.addRight(v, null); String t = preorderAET(T, T.left(v), s.substring(1)); return preorderAET(T, T.right(v), t); } } // ******************************* // Add your indented() methods here // ******************************* /** * This main method tests the class LinkedBinaryTree using the example from * Figure 8.6, p. 318, of our textbook. */ public static void main(String[] args) { LinkedBinaryTree bt = new LinkedBinaryTree<>(); preorderAET(bt, "- / * + 3 1 3 + - 9 5 2 + * 3 - 7 4 6"); // expression in prefix notation indented(bt); } }

AbstractBinaryTree.java

public abstract class AbstractBinaryTree extends AbstractTree implements BinaryTree { /** * Returns the Position of p's sibling (or null if no sibling exists). * * @param p a valid Position within the tree * @return the Position of the sibling (or null if no sibling exists) * @throws IllegalArgumentException if p is not a valid Position */ public Position sibling(Position p) { Position parent = parent(p); if (parent == null) return null; // p must be the root if (p == left(parent)) // p is a left child return right(parent); // (right child might be null) else // p is a right child return left(parent); // (left child might be null) } /** * Returns the number of children of Position p. * * @param p a valid Position within the tree * @return number of children of Position p * @throws IllegalArgumentException if p is not a valid Position */ @Override public int numChildren(Position p) { int count=0; if (left(p) != null) count++; if (right(p) != null) count++; return count; } /** * Returns an iterable collection of the Positions representing p's * children. * * @param p a valid Position within the tree * @return iterable collection of the Positions of p's children * @throws IllegalArgumentException if p is not a valid Position */ public Iterable> children(Position p) { List> snapshot = new ArrayList<>(2); if (left(p) != null) snapshot.add(left(p)); if (right(p) != null) snapshot.add(right(p)); return snapshot; } }

AbstractTree.java

public abstract class AbstractTree implements Tree { /** * Returns true if Position p has one or more children. * * @param p a valid Position within the tree * @return true if p has at least one child, false otherwise * @throws IllegalArgumentException if p is not a valid Position */ public boolean isInternal(Position p) { return numChildren(p) > 0; } /** * Returns true if Position p does not have any children. * * @param p a valid Position within the tree * @return true if p has zero children, false otherwise * @throws IllegalArgumentException if p is not a valid Position */ public boolean isExternal(Position p) { return numChildren(p) == 0; } /** * Returns true if Position p represents the root of the tree. * * @param p a valid Position within the tree * @return true if p is the root of the tree, false otherwise */ public boolean isRoot(Position p) { return p == root(); } /** * Returns the number of children of Position p. * * @param p a valid Position within the tree * @return number of children of Position p * @throws IllegalArgumentException if p is not a valid Position */ public int numChildren(Position p) { int count=0; for (Position child : children(p)) count++; return count; } /** * Returns the number of nodes in the tree. * * @return number of nodes in the tree */ public int size() { int count=0; for (Position p : positions()) count++; return count; } /** * Tests whether the tree is empty. * * @return true if the tree is empty, false otherwise */ public boolean isEmpty() { return size() == 0; } //---------- computing depth of nodes and height of (sub)trees ---------- /** * Returns the number of levels separating Position p from the root. * * @param p a valid Position within the tree * @throws IllegalArgumentException if p is not a valid Position */ public int depth(Position p) throws IllegalArgumentException { if (isRoot(p)) return 0; else return 1 + depth(parent(p)); } /** * Returns the height of the tree, using depth(). */ private int heightBad() { int h = 0; for (Position p : positions()) if (isExternal(p)) h = Math.max(h, depth(p)); return h; } /** * Returns the height of the subtree rooted at Position p. * * @param p a valid Position within the tree * @throws IllegalArgumentException if p is not a valid Position */ public int height(Position p) throws IllegalArgumentException { int h = 0; // base case if p is external for (Position c : children(p)) h = Math.max(h, 1 + height(c)); return h; } //---------- support for various iterations of a tree ---------- //---------------- nested ElementIterator class ---------------- /* * This class adapts the iteration produced by positions() to return * elements. */ private class ElementIterator implements Iterator { Iterator> posIterator = positions().iterator(); public boolean hasNext() { return posIterator.hasNext(); } public E next() { return posIterator.next().getElement(); } public void remove() { posIterator.remove(); } } /** * Returns an iterator of the elements stored in the tree. * * @return iterator of the tree's elements */ public Iterator iterator() { return new ElementIterator(); } /** * Returns an iterable collection of the positions of the tree. * * @return iterable collection of the tree's positions */ public Iterable> positions() { return preorder(); } /** * Adds positions of the subtree rooted at Position p to the given snapshot * using a preorder traversal * * @param p Position serving as the root of a subtree * @param snapshot a list to which results are appended */ private void preorderSubtree(Position p, List> snapshot) { snapshot.add(p); for (Position c : children(p)) preorderSubtree(c, snapshot); } /** * Returns an iterable collection of positions of the tree, reported in * preorder. * * @return iterable collection of the tree's positions in preorder */ public Iterable> preorder() { List> snapshot = new ArrayList<>(); if (!isEmpty()) preorderSubtree(root(), snapshot); // fill the snapshot recursively return snapshot; } }

BinaryTree.java

public interface BinaryTree extends Tree { /** * Returns the Position of p's left child (or null if no child exists). * * @param p a valid Position within the tree * @return the Position of the left child (or null if no child exists) * @throws IllegalArgumentException if p is not a valid Position */ Position left(Position p) throws IllegalArgumentException; /** * Returns the Position of p's right child (or null if no child exists). * * @param p a valid Position within the tree * @return the Position of the right child (or null if no child exists) * @throws IllegalArgumentException if p is not a valid Position */ Position right(Position p) throws IllegalArgumentException; /** * Returns the Position of p's sibling (or null if no sibling exists). * * @param p a valid Position within the tree * @return the Position of the sibling (or null if no sibling exists) * @throws IllegalArgumentException if p is not a valid Position */ Position sibling(Position p) throws IllegalArgumentException; }

LinkedBinaryTree.java

public class LinkedBinaryTree extends AbstractBinaryTree { //---------------- nested Node class ---------------- /** Nested static class for a binary tree node. */ protected static class Node implements Position { private E element; // an element stored at this node private Node parent; // a reference to the parent node (if any) private Node left; // a reference to the left child (if any) private Node right; // a reference to the right child (if any) /** * Constructs a node with the given element and neighbors. * * @param e the element to be stored * @param above reference to a parent node * @param leftChild reference to a left child node * @param rightChild reference to a right child node */ public Node(E e, Node above, Node leftChild, Node rightChild) { element = e; parent = above; left = leftChild; right = rightChild; } // accessor methods public E getElement() { return element; } public Node getParent() { return parent; } public Node getLeft() { return left; } public Node getRight() { return right; } // update methods public void setElement(E e) { element = e; } public void setParent(Node parentNode) { parent = parentNode; } public void setLeft(Node leftChild) { left = leftChild; } public void setRight(Node rightChild) { right = rightChild; } } //----------- end of nested Node class ----------- /** Factory function to create a new node storing element e. */ protected Node createNode(E e, Node parent, Node left, Node right) { return new Node(e, parent, left, right); } // LinkedBinaryTree instance variables protected Node root = null; // root of the tree private int size = 0; // number of nodes in the tree // constructor public LinkedBinaryTree() { } // constructs an empty binary tree // nonpublic utility /** * Verifies that a Position belongs to the appropriate class, and is not * one that has been previously removed. Note that our current * implementation does not actually verify that the position belongs to * this particular list instance. * * @param p a Position (that should belong to this tree) * @return the underlying Node instance for the position * @throws IllegalArgumentException if an invalid position is detected */ protected Node validate(Position p) throws IllegalArgumentException { if (!(p instanceof Node)) throw new IllegalArgumentException("Not valid position type"); Node node = (Node) p; // safe cast if (node.getParent() == node) // our convention for defunct node throw new IllegalArgumentException("p is no longer in the tree"); return node; } // accessor methods (not already implemented in AbstractBinaryTree) /** * Returns the number of nodes in the tree. * @return number of nodes in the tree */ @Override public int size() { return size; } /** * Returns the root Position of the tree (or null if tree is empty). * * @return root Position of the tree (or null if tree is empty) */ public Position root() { return root; } /** * Returns the Position of p's parent (or null if p is root). * * @param p a valid Position within the tree * @return Position of p's parent (or null if p is root) * @throws IllegalArgumentException if p is not a valid Position */ public Position parent(Position p) throws IllegalArgumentException { Node node = validate(p); return node.getParent(); } /** * Returns the Position of p's left child (or null if no child exists). * * @param p a valid Position within the tree * @return the Position of the left child (or null if no child exists) * @throws IllegalArgumentException if p is not a valid Position */ public Position left(Position p) throws IllegalArgumentException { Node node = validate(p); return node.getLeft(); } /** * Returns the Position of p's right child (or null if no child exists). * * @param p a valid Position within the tree * @return the Position of the right child (or null if no child exists) * @throws IllegalArgumentException if p is not a valid Position */ public Position right(Position p) throws IllegalArgumentException { Node node = validate(p); return node.getRight(); } // update methods supported by this class /** * Places element e at the root of an empty tree and returns its new * Position. * * @param e the new element * @return the Position of the new element * @throws IllegalStateException if the tree is not empty */ public Position addRoot(E e) throws IllegalStateException { if (!isEmpty()) throw new IllegalStateException("Tree is not empty"); root = createNode(e, null, null, null); size = 1; return root; } /** * Creates a new left child of Position p storing element e and returns its * Position. * * @param p the Position to the left of which the new element is inserted * @param e the new element * @return the Position of the new element * @throws IllegalArgumentException if p is not a valid Position * @throws IllegalArgumentException if p already has a left child */ public Position addLeft(Position p, E e) throws IllegalArgumentException { Node parent = validate(p); if (parent.getLeft() != null) throw new IllegalArgumentException("p already has a left child"); Node child = createNode(e, parent, null, null); parent.setLeft(child); size++; return child; } /** * Creates a new right child of Position p storing element e and returns * its Position. * * @param p the Position to the right of which the new element is inserted * @param e the new element * @return the Position of the new element * @throws IllegalArgumentException if p is not a valid Position * @throws IllegalArgumentException if p already has a right child */ public Position addRight(Position p, E e) throws IllegalArgumentException { Node parent = validate(p); if (parent.getRight() != null) throw new IllegalArgumentException("p already has a right child"); Node child = createNode(e, parent, null, null); parent.setRight(child); size++; return child; } /** * Replaces the element at Position p with element e and returns the * replaced element. * * @param p the relevant Position * @param e the new element * @return the replaced element * @throws IllegalArgumentException if p is not a valid Position */ public E set(Position p, E e) throws IllegalArgumentException { Node node = validate(p); E temp = node.getElement(); node.setElement(e); return temp; } /** * Attaches trees t1 and t2, respectively, as the left and right subtree of * the leaf Position p. As a side effect, t1 and t2 are set to empty trees. * * @param p a leaf of the tree * @param t1 a tree whose structure becomes the left child of p * @param t2 a tree whose structure becomes the right child of p * @throws IllegalArgumentException if p is not a valid Position * @throws IllegalArgumentException if p is not a leaf */ public void attach(Position p, LinkedBinaryTree t1, LinkedBinaryTree t2) throws IllegalArgumentException { Node node = validate(p); if (isInternal(p)) throw new IllegalArgumentException("p must be a leaf"); size += t1.size() + t2.size(); if (!t1.isEmpty()) { // attach t1 as left subtree t1.root.setParent(node); node.setLeft(t1.root); t1.root = null; t1.size = 0; } if (!t2.isEmpty()) { // attach t2 as right subtree t2.root.setParent(node); node.setRight(t2.root); t2.root = null; t2.size = 0; } } /** * Removes the node at Position p and replaces it with its child, if any. * * @param p the relevant Position * @return element that was removed * @throws IllegalArgumentException if p is not a valid Position * @throws IllegalArgumentException if p has two children. */ public E remove(Position p) throws IllegalArgumentException { Node node = validate(p); if (numChildren(p) == 2) throw new IllegalArgumentException("p has two children"); Node child = (node.getLeft() != null ? node.getLeft() : node.getRight() ); if (child != null) child.setParent(node.getParent()); // grandparent becomes its parent if (node == root) root = child; // child becomes root else { Node parent = node.getParent(); if (node == parent.getLeft()) parent.setLeft(child); else parent.setRight(child); } size--; E temp = node.getElement(); node.setElement(null); // help garbage collection node.setLeft(null); node.setRight(null); node.setParent(node); // our convention for defunct node return temp; } } //----------- end of LinkedBinaryTree class -----------

Position.java

public interface Position { /** * Returns the element stored at this position. * * @return the stored element * @throws IllegalStateException if position no longer valid */ E getElement() throws IllegalStateException; }

Tree.java

public interface Tree extends Iterable { /** * Returns the root Position of the tree (or null if tree is empty). * * @return root Position of the tree (or null if tree is empty) */ Position root(); /** * Returns the Position of p's parent (or null if p is root). * * @param p a valid Position within the tree * @return Position of p's parent (or null if p is root) * @throws IllegalArgumentException if p is not a valid Position */ Position parent(Position p) throws IllegalArgumentException; /** * Returns an iterable collection of the Positions representing p's children. * * @param p a valid Position within the tree * @return iterable collection of the Positions of p's children * @throws IllegalArgumentException if p is not a valid Position */ Iterable> children(Position p) throws IllegalArgumentException; /** * Returns the number of children of Position p. * * @param p a valid Position within the tree * @return number of children of Position p * @throws IllegalArgumentException if p is not a valid Position */ int numChildren(Position p) throws IllegalArgumentException; /** * Returns true if Position p has one or more children. * * @param p a valid Position within the tree * @return true if p has at least one child, false otherwise * @throws IllegalArgumentException if p is not a valid Position */ boolean isInternal(Position p) throws IllegalArgumentException; /** * Returns true if Position p does not have any children. * * @param p a valid Position within the tree * @return true if p has zero children, false otherwise * @throws IllegalArgumentException if p is not a valid Position */ boolean isExternal(Position p) throws IllegalArgumentException; /** * Returns true if Position p represents the root of the tree. * * @param p a valid Position within the tree * @return true if p is the root of the tree, false otherwise * @throws IllegalArgumentException if p is not a valid Position */ boolean isRoot(Position p) throws IllegalArgumentException; /** * Returns the number of nodes in the tree. * * @return number of nodes in the tree */ int size(); /** * Tests whether the tree is empty. * * @return true if the tree is empty, false otherwise */ boolean isEmpty(); /** * Returns an iterator of the elements stored in the tree. * * @return iterator of the tree's elements */ Iterator iterator(); /** * Returns an iterable collection of the positions of the tree. * * @return iterable collection of the tree's positions */ Iterable> positions(); }