Java Language.

Objective: In this lab assignment you will be implementing the abstract tree, the abstract binary tree, and the linked binary tree.

Create a NetBeans project using the standard convention, i.e. Lab107-LastFM and ensure it is saved to a location like desktop or your flash drive.

In completing this assignment, you must include and use the interfaces and classes for the abstract tree, abstract binary tree and the linked binary tree ADTs presented in the textbook.

A large part of this exercise will be gathering together the various code fragments and placing them in the right classes.

Be sure to review code fragments 8.1 to 8.28 to make sure that you have include all of the necessary code. In some cases, the needed code may not appear in a formal code fragment but is implied in the text.

You will probably not get rid of all of the compiler errors until you include all of the necessary code fragments in their correct classes.

Implement the LinkedBinaryTree class described in code fragments 8.8 to 8.11 in the textbook. Also implement all classes that the LinkedBinaryTree class depends on. Many of these classes will just need to be copied from previous assignments. Review code fragments 8.13 to 8.28 and determine which of these fragments need to be included in your solution.

In completing this assignment, you may import only the following if needed (try using you over versions of these first):

• Java.util.Iterable
• java.util.Iterator
• java.util.ArrayList
• java.util.List

Once you have successfully implement the LinkedBinaryTree class:

Create a client class that does the following:

• Manually creates an instance of a binary expression tree that represents the following expression:
• ( 2 + 9 ) + ( 7 - ( 3 * 8 ) )
• Do this by using methods such as addRoot, addLeft, addRight, set, and attach.
• The element should be of type String
• Note that you are manually building this specific expression tree, the pseudo code might look something like:
  • Create a LinkedBinaryTree with 2 as its root element.
  • Create another LinkedBinaryTree with 9 as its root element.
  • Create a third LinkedBinaryTree with + as its root element.
  • Attach the tree with the 2 as the left child and the tree with the 9 as the right child to the tree with the +.
  • You now have a subexpression that can be attached to the expression tree as you build it.
  • etc.

The above example implies a bottom-up construction of the tree. You may want to consider if it would be easier to build the tree in a top-down fashion or in a bottom-up fashion.

Once you have created the expression tree have your client print out the following:

• The literal string that represents the expression, i.e.:

( 2 + 9 ) + ( 7 - ( 3 * 8 ) )

• The height of the expression tree
• The preOrder traversal of the tree
• The inOrder traversal of the tree
• The postOrder traversal of the tree
• The breathFirst traversal of the tree
• The parenthesized representation of the tree using Eulers Tour ( section 8.4.6 and Code Fragment 8.29 ), this is NOT the parenthesize( ) method in Code Fragment 8.26.

In Code Fragment 8.1, we formalize the Tree ADT by defining the Tree interface in Java. We rely upon the same definition of the Position interface as introduced for positional lists in Section 7.3.2. Note well that we declare the Tree interface to formally extend Java's Iterable interface (and we include a declaration of the required iterator() method). 6 1 /** An interface for a tree where nodes can have an arbitrary number of children. */ 2 public interface Tree extends Iterable { 3 Position root(); 4 Position parent(Position p) throws IllegalArgumentException; 5 Iterable> children(Position p) throws IllegalArgumentException: 7 int numChildren(Position p) throws IllegalArgumentException; 8 boolean isinternal(Position p) throws IllegalArgumentException; boolean isExternal(Position p) throws lilegalArgumentException: 10 boolean isRoot(Position p) throws IllegalArgumentException: 11 int size(); 12 boolean isEmpty(); 13 Iterator iterator(); 14 Iterable> positions(): 15 } Code Fragment 8.1: Definition of the Tree interface. 9 An Abstract Tree Base Class in Java In Section 2.3, we discussed the role of interfaces and abstract classes in Java. definition that includes public declarations of vari- In racin all other base class. class that provides the most trivial methods of the Tree interface. We will dele Code Fragment 8.2 presents an initial implementation of an Abstract Trees to produced the positions() iteration within the Abstract Tree class. As with our until Section 8.4 a discussion of general tree-traversal algorithms that can be positional list ADT in Chapter 7, the iteration of positions of the tree can easily adapted to produce an iteration of the elements of a tree, or even to determine the size of a tree (although our concrete tree implementations will provide more de means for reporting the size). 1 /** An abstract base class providing some functionality of the Tree interface. 2 public abstract class Abstract Tree implements Tree { 3 public boolean isinternal(Position p) { return numChildren(p) > 0;} 4 public boolean isExternal(Position p) { return numChildren(p) == 0;} 5 public boolean isRoot(Position p) { return p == root(); } 6 public boolean isEmpty() { return size() == 0; } Code Fragment 8.2: An initial implementation of the Abstract Tree base clas ( add additional functionality to this class as the chapter continues.) 8.1.3 Computing Depth and Height Let p be a position within tree T. The depth of p is the number of ancestas International P, other than p itself. For example, in the tree of Figure 8.2, the node.com linn that the depth of 1. General Trees 315 1 /** Returns the number of levels separating Position p from the root. */ 2 public int depth(Position p) { 3 if (isRoot(p)) 4 return 0; 5 else 6 return 1 + depth(parent(p)); 7 } Code Fragment 8.3: Method depth, as implemented within the Abstract Tree class. Height We next define the height of a tree to be equal to the maximum of the depths of Tion nyomnle the tree of Figure 8.2 has The following proposition relates our original definition of the height of a tee to the height of the root position using this recursive formula. Proposition 8.3: The height of the root of a nonempty tree T, according to the recursive definition, equals the maximum depth among all leaves of tree T. We leave the justification of this proposition as Exercise R-8.3. An implementation of a recursive algorithm to compute the height of a subtres rooted at a given position p is presented in Code Fragment 8.5. The overall height of a nonempty tree can be computed by sending the root of the tree as a parameter 1 /** Returns the height of the subtree rooted at Position p. */ 2 public int height(Position p) { 3 int h = 0; // base case if p is external for (Positionc: children(p)) 5 h = Math.max(h, 1 + height(c)); 6 return h; 7 } Code Fragment 8.5: Method height for computing the height of a subtree rooted a a position p of an Abstract Tree. It is important to understand why method height is more efficient than method the method is initially called on the root of t it will ontually be called once heightBad. The algorithm is recursive, and it progresses in a top-down fashion. I applications of binary trees. Defining a Binary Tree Interface Code Fragment 8.6 formalizes the binary tree ADT by defining a BinaryTree in- terface in Java. This interface extends the Tree interface that was given in Sec- tion 8.1.2 to add the three new behaviors. In this way, a binary tree is expected to support all the functionality that was defined for general trees (e.g., root, isExternal, parent), and the new behaviors left, right, and sibling. | ** An interface for a binary tree, in which each node has at most two children. */ 2 public interface Binary Tree extends Tree { 3 /** Returns the Position of p's left child (or null if no child exists). / + Position left(Position p) throws IllegalArgumentException; 5 /** Returns the Position of p's right child (or null if no child exists). */ 6 Position right(Position p) throws IllegalArgumentException; 7 /** Returns the Position of p's sibling (or null if no sibling exists). */ Position sibling(Position p) throws IllegalArgumentException; Code Fragment 8.6: A Binary Tree interface that extends the Tree interface from Code Fragment 8.1. Defining an AbstractBinary Tree Base Classe We continue our use of abstract base classes to promote greater reusability within plemente plementations of the original Tree interface. Using the terminology tion of the children method relies on producing a snapshot. We create an e java.util. ArrayList, which qualities as being an iterable container, and then add children that exist, ordered so that a left child is reported before a right child. 1. An abstract base class providing some functionality of the Binary Tree interface 2 public abstract class Abstract Binary Tree extends Abstract Tree implements Binary Tree 3 + Returns the Position of p's sibling (or null if no sibling exists). 5 public Position sibling(Position p) { 6 Position parent = parent(p): // p must be the root 7 if (parent == null) return null; // p is a left child if (p left(parent)) W (right child might be nully 9 return right(parent); //p is a right child 10 else // (left child might be null) 11 return left(parent); 12 } 13 / Returns the number of children of Position p/ 14 public int numChildren(Position p) { 15 int count=0 16 if (left(p) != null) 17 count++; 18 if (right(p) != null) 19 count++ 20 return count: 21 } 22 1. Returns an iterable collection of the Positions representing p's children 23 public Iterable> children(PositionP) { 24 List> snapshot = new ArrayList(2); // max capacity of 2 25 if (left(p) I= null) 26 snapshot.add(left(p)): 27 if (right(p) != null) 28 snapshot add(right(p)); 29 return snapshot: 30 } 31 } Code Fragment 8.7: An AbstractBinary Tree class that extends the Abstract class of Code Fragment 8.2 and implements the Binary Tree interface of Code For ment 8.6. Amplementing Trees public class LindbinaryTerextenda AbutractSinay Times ested Noclam protected static class Podec >> implements Position private Element private Node parent private Nodece left private Node node - (Node) (node petParent) - node) 1/ our contion for det throw new legalmente a longer is the tree return node 40 9 10 rence to the leti for to the chidi 11 52 14 15 17 TH 19 20 parent above et left Child right Child 2 acce methods public EcetElement() { return element, public Node getParent) return parent] public NodecE>get() { return :) public Nude Right() { return right: // update methods public void setElement(E e) [dement =] public void setParentNodec parentNode) parent-parentNode] public void setler(Node.Es left Child) { left leftChild; } public void setoghtNodec> rightChild) (right rightChild) end of rested Node liss 5+ 55 36 S7 SR 2 // access methods not already mleted in AbstractBinary / Returns the number of rodes in the tree. public int sie returns 1 1. Returns the root Position of the tree for nulla tom). public PositionCE root) retum mot 61 22 23 24 25 26 27 fa 45 1 70 30 31 32 Factory function to create a new node storing elemente protected Node CE createNode(Ee Node ES parent Node ft. Node Eright) return new Node(e. parent, left, right); 1 // LinkedBinary Trer instance variables protected Nodec root null root of the tree private int site-0 // number of nodes in the tree - Returns the Position of sent (or nullo public Position parentPosition) throws legalmentException Nodec node validate() return node getParent: > / Return the position of child fornul if necht) public Position of Position ) throws legalmentti Node sode validate(): return node gete() ) 70 71 72 73 74 75 74 13 36 17 77 75 79 39 constructor 10 public LinkedBinary Tree() () // constructs an empty binary tree Code Franvat 8.8: An implementation of the Linked Binary Tree class. (Continues in Code Fragments 8.9.811) I. Returns the Position of p's right child (or ralltro child public Position right PositionCE>) throwser Mode node validate() return nodege Right 1 Code Fragment : An implementation of the LinkedBirury Tecla (Continued from Code Fragment R&. continues in Code Page 10 and 11.) Chapter 12 NE 13 Update methods and by the des put Position RootE6) throws State Exception a wewcation la ply Attached tremi and the public void atac Position and in Linked BinarTec612) theowo Node rode validate(pl. mon throw new tipust let te) (11 Empty(1) Watch the 11 Parentide) mode (11) thull 1 0 return attach ta bor LU (it is my rootse Parentinade) node eRight(t2004) 12 root = null 12-0 1 11 138 110 141 11 Grata new did Pestion portemente retums. Poco 001 public Foodleft(Prisition. E) throw legalment caption 92 Nodec tvaldati ir port throw new largumentation direndy has left te Nodechid chatNode.parent, nu, null) parent Lechild) 97 36 return 99 100 JO 7. Create a new child of Position storing elementer i the public Police addRightPosition ) 100 throws ilegalArgumentException 101 Node Esparent validate os a presetog (= null) throw new ArgumentException already ha right chule 107 Node child createNode.parent, null null) MON part tight(child) 0 : 110 return child 1 1. Replace the element at Position with and return the replaced 114 public setPosition . E .) throws illegal gumentException 115 Node ES node - validate() 116 E temo - nodegetElement) 117 node Element(0) TIN return temp 110 2 Code Fragment.10: An implementation of the LinkedBinary Tree class (Continuand from Code Fragments 88 and 8.9. continues in Code Fagtem 8:16) 17 14 149 INO ISI 152 193 154 155 156 Fomes the node at Potion and replace it with its child if any. public Enemove Position ) throws Exception Node de validate() if (numid) - 2) throw new generato all"} Nodec Echinodegetele nollrodepse) ndertight) If did null did setParentnode Prem) // grandparent com a pret IF (noderoot) Tot child child becomes to che Node parentnodige Parent) (ode rentgelt parentschid) che porest stigh child 158 159 100 101 162 163 Etemp = node petElement non setElement(lb) What colectie nodesete (nally node.setRog(null) node.setParent(node) / our confort de return temp 1 end of Linary Tree class CodeFragment. At implementative of the LinkedBinary Tree Continued from Code Fragments 83-8.10) 161 tree traversal algorithms we have introduced can be used to produce these iterations as concrete implementations within the Abstract Tree or AbstractBinary Tree base u Ulder in which these uns Section, we will demonstrate how any of the classes. es an First, we note that an iteration of all elements of a tree can easily be produced if we have an iteration of all positions of that tree. Code Fragment 8.16 provides implementation of the iterator() method by adapting an iteration produced by the positions() method. In fact, this is the identical approach we used in Code Fragment 7.14 of Section 7.4.2 for the LinkedPositionalList class. -------- nested Elementlterator class This class adapts the iteration produced by positions() to return elements. */ 3 private class Elementlterator implements Iterator { Iterator> poslterator = positions() iterator(); public boolean hasNext() { return poslterator hasNext(); } 6 public E next() { return poslterator.next().getElement(); } // return element! public void remove() { poslterator.remove(); } 5 7 8 } 10 /** Returns an iterator of the elements stored in the tree. / 11 public Iterator iterator() { return new ElementIterator(); } Code Fragment 8.16: Iterating all elements of an Abstract Tree instance, based upon an iteration of the positions of the tree. To implement the positions() method, we have a choice of tree traversal algo- rithms. Given that there are advantages to each of those traversal orders, we provide public implementations of each strategy that can be called directly by a user of our class. We can then trivially adapt one of those as a default order for the positions method of the Abstract Tree class. For example, on the following page we will de- We begin by defining Fragment 8.18, which allows us to parameterize the recursive process with a cific position of the tree that serves as the root of a subtree to traverse Web pass a list as a parameter that serves as a buffer to which "visited positions added.) no- put 6 7 8 9 10 11 12 13 L if r Code code Brea Ont trave Reca of pc from 1 /Adds positions of the subtree rooted at Position p to the given snapshots 2 private void preorderSubtree(Position p. List> Snapshot) 3 snapshot.add(p): // for preorder, we add position p before exploring 4 for (Positionc: children(p)) 5 preorderSubtree(c. snapshot): 6 } Code Fragment 8.18: A recursive subroutine for performing a preorder traversele the subtree rooted at position p of a tree. This code should be included within te body of the Abstract Tree class. The preorderSubtree method follows the high-level algorithm originally de scribed as pseudocode in Code Fragment 8.12. It has an implicit base case, as the for loop body never executes if a position has no children. The public preorder method, shown in Code Fragment 8.19, has the rese sibility of creating an empty list for the snapshot buffer, and invoking the rece sive method at the root of the tree (assuming the tree is nonempty). We rely at i java.util.ArrayList instance as an Iterable instance for the snapshot buffer 1 - Returns an Iterable collection of positions of the tree, reported in precede 2 public Iterable> preorder() { 3 List> snapshot = new Arrayl.isto: 4 if (lisEmpty) 5 preorderSubtree root().snapshot): // fill the snapshot recursively 6 return snapshot: 7 } Code Fragment 8.19: A public method that performs a preorder traversal of an tree. This code should be included within the body of the Abstract Tree class Inord The trees a left its de desig travel F travel defau was i posit Trees X4 The Traversal Algorithms Postorder Traversal 341 de a We implement a postorder traversal using a similar design as we used for a pre- order traversal. The only difference is that a "visited" position is not added to a postorder snapshot until after all of its subtrees have been traversed. Both the re- cursive utility and the top-level public method are given in Code Fragment 8.20 iter- ion hing de De- Iso are 6 7 1. Adds positions of the subtree rooted at Position p to the given snapshot 2 private void postorderSubtree(Position p. List> snapshot) { for (Position C: children(p)) postorderSubtree(c, snapshot); 5 snapshot.add(p): 7/ for postorder, we add position p after exploring subtrees } /** Returns an iterable collection of positions of the tree, reported in postorder / 8 public Iterable> postorder() { List> snapshot = new ArrayList0: if (!isEmpty()) postorderSubtree(root(), snapshot); // fill the snapshot recursively 12 return snapshot; 13] Code Fragment 8.20: Support for performing a postorder traversal of a tree. This code should be included within the body of the Abstract Tree class. 9 10 as Breadth-First Traversal On the following page, we will provide an implementation of the breadth-first traversal algorithm in the context of our Abstract Tree class (Code Fragment 8.21). Recall that the breadth first traversal algorithm is not recursive; it relies on a queue ala Chapter 8. Then & 342 / Returns an Iterable collection of positions of the tree in breadth-first order // start with the root public Iterable> breadthfirst() { List> snapshot = new ArrayList0); if (lisEmpty() Queve> fringe = new LinkedQueue 0; fringe.enqueue(root(); while (fringe.isEmpty()) { Position p = fringe dequeue(): snapshot add(p) for (Positionc: children(p)) fringe enqueue(c); 6 7 8 9 10 // remove from front of the que // report this position // add children to back of queue 13 14 15 return snapshot: 1 Code Fragment 8.21: An implementation of a breadth-first traversal of a tree. This code should be included within the body of the Abstract Tree class. 1 2 3 - Adds positions of the subtree rooted at Position p to the given snapshot private void inorderSubtree(Position p. List> Snapshot) { if (left(p) = null) inorderSubtree(left(p), snapshot): snapshot add(p): if (right(p) = null) inorderSubtree(right(p), snapshot); 1. Returns an iterable collection of positions of the tree, reported in inorder public Iterable> inorder() { List> snapshot = new ArrayList0; if (lisEmpty()) inorderSubtree(root(), snapshot); // fill the snapshot recursively return snapshot: 8 9 10 11 12 13 14 15 16 17 18 19 - Overrides positions to make inorder the default order for binary trees. public Iterable > positions() { return inorder(): Code Fragment 8,22: Support for performing an inorder traversal of a binary tres and for making that order the default traversal for binary trees. This code should included within the body of the AbstractBinary Tree class. Chapter 8. Tree 344 parame A preferred approach to producing an indented table of contents is to rem runs in worst-case O(n) time (except, technically, the time it takes to print trims Such an implementation is provided in Code Fragment 8.23. This implement a top-down recursion that includes the current depth as an of increasing lengths). Prints preorder representation of subtree of T rooted at p having depth o. 2 public static void printPreorderindent Tree T. Position p. int d) 7/indent based on // child depth is d+1 1 3 1 5 6) (spaces+ p getElement(); for (Position c. T.children(p)) printPreorderindent(T. cd+1); order traversal. To print an entire tree T, the recursion should be started with for Code Fragment 8.23: Efficient recursion for printing indented version of a pre printPreorderindent(T. T.root(), 0). In the example of Figure 8.18, we were fortunate in that the numbering was embedded within the elements of the tree. More generally, we might be interested in using a preorder traversal to display the structure of a tree, with indentation and also explicit numbering that was not present in the tree. For example, we might display the tree from Figure 8.2 beginning as: Electronics R'Us 1 R&D 2 Sales 2.1 Domestic 2.2 International 2.2.1 Canada 2.2.2 S. America implicit a particular list of values {2.1} that comprise its label. This is more challenging, because the numbers used as labels are the structure of the tree. A label depends on the path from the root to the cute signature. We send a list of integers representing the labels leading to a position. To accomplish our goal, we add an additional parameter to the recursie position. For example, when visiting the node Domestic above, we will send the At the implementation level, we wish to avoid the inefficiency of duplicate such lists when sending a new parameter from one level of the recursion to the al A standard solution is to math cursion set(2, G) get(2) D G (B, E, G, C, F) (B, E, G, C, F) 9 10 1 /** A simplified version of the java.util.List interface. */ 2 public interface List { 3 /** Returns the number of elements in this list / 4 int size(); 5 6 /** Returns whether the list is empty. */ 7 boolean isEmpty(); 8 /** Returns (but does not remove) the element at index i. */ E get(int i) throws IndexOutOfBoundsException; 11 12 /** Replaces the element at index i with e, and returns the replaced element / E set(int i, E e) throws IndexOutOfBoundsException: /** Inserts element e to be at index i, shifting all subsequent elements later. / 16 void add(int i. E e) throws IndexOutOfBoundsException; 17 18 7** Removes/returns the element at index i, shifting subsequent elements earlier. */ 19 E remove(int i) throws IndexOutOfBoundsException; 20 } Code Fragment 7.1: A simple version of the List interface. 13 14 15 Chapter 7. Landet 7.2 Array Lists 11 12 An abuchode for implementing the list ADTi to use an am A. When wores de ce the element with index. We will begin by using have a fundacity but in Section 7.2.1 describe a more advanced und an array list in Java for vector in Chiste thal tectively allows an array bure list to have unbounded cocy. Se earliest of Java With a representation based on an array A, the get() and settleme asy to implement by accessing An (assuming I is a legitimate inden hel addle and remove are more time consuming, as they require shifting up or down to maintain our mile of always storing an element whose line at index of the array. (See Figure 7.1.) Our initial implementation of the class follows in Code Fragments 72 and 7.3 OT2 H-1 N-1 (a) 261 1/puthic methods e Returns the number of lees is the way it. public int (return) 14 Return whether they at my is public boolean isEmpty() (return) 16 Returns (but does not remove the centaine IT public Eatinti) throws IndeOutOfBoundException 1 checked. return data 20 2 21 public E sint Ee) throws IndexO01BoundException checkindedi, size) 34 Etemp data 25 detail- sh return temp 21 et eleinte to be at index shifting all str./ 20 public void add(nt Ee) throws Inde OutOfBoundException 0 Hegal State Exception 31 checkIndendi, size +1 32 if (data length not modity 13 row new IllegalStateExceptionery is fully 34 for (int 1k) 25 data/11 - data data 37 38 1 39 - Remove/return the mentinde sig met alle public Ecomove(int i) throws IndexOutOfBoundation checkIndelse) Elump dat 40 for (int 2-1) 44 Westo file datal-fut-11 Ihalore collection 17 18 40 tity method Checks whether the venindex in the map 10 - 11 - SE protected vold checklindex(int int) throws Index lourdeception if

2 W ostatic variables 1 public static final int CAPACITY=16, // default array capacity private Ell data 5 private int i = 0; W.constructor public ArrayList() { this CAPACITY):) constructs with de public ArrayListint capacity) 9 data-(EL) new Object capacity capacity (Continnes in Code Fragment 7.3.) Code Fragment 7.21 An implementation of a simple ArrayList class with a constructs with 1/ safe cast compler mer Chapter 7 Lander ADT Example 7.4: The following the showerles person a positional stringere To identystances, we 235 An inte har position is public interface Positionin Method addlar) Return value P P 3 addAttar(x, 5) before addBefore(3) r.getElement() after) before() addFirst (9) remove(last()) set(p. 7) Contents (p) p) (5) (p.5 Sp. 5) pr. 59 Sp. 38.50) (p.3.5) 19. p. Ir. Sah 19. 3) 09.7p3 null 5 8 "mor" ET 10 (4- Tests with the literply. boolean isEmpty -. flatus the first Position in the list for at Positione first - Return the last Position in the store Positioncast) Returns the Position immediately do Position for tests. Position for PositionCES ) low galer Return the Potion immediately after Poution lori last). Position (Position throw legalmentation rets demente at the front of the list and returns its new Postion. Position addFinde) - marts mente at the back of the list and returns oution/ Positione> addas merts element immediately before Position and rese Position Position addBeforPosition E) throw legalArgument.crotor Intemente immediately after Positions and its new position. Position > addAfter PositionCE E.) throws IllegalArgumentException Replaces the element stored at Pation and return the placed element set(Position E) throws illegal ArumentException 3 16 2 Java Interface Definitions We are now ready to formalize the position ADT and positionalist ADT. A la Position interface, representing the position ADT, is given in Code Fragment 71 Following that Code Fragment 7.8 presents a Java definition for our Positionalist Interface. If the getElement() method is called on a Position instance du previously been removed from its list, an illegalStateException is thrown. If im alid Position instance is sent as a parameter to a method of a Positionalista llegal ArgumentException is thrown (Both of those exception types are defined in the Mandard for hierarchy) public interface Position Return the senent stored at this position return the stored element Othrows MealState Exception if position no longer valid . EgetElement() throws StateException 29 30 3 35 16 37 5 19 in 41 * Removes the element stored at Position and retum (imangol EremovePosition p) throws Illegal option Code Fragment 7.8: The Positional Listrace. Code Fragment 7.7 The Position interface