it's a java question
/* * From Data Structures and Algorithms in Java, Sixth Edition, Goodrich et al. */
/** * An interface for a tree where nodes can have an arbitrary number of children. */
public interface Tree{
/** * 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 for this tree. */ 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 for this tree. */ 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 for this tree. */ 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 for this tree. */ 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 for this tree. */ 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 for this tree. */ 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(); } -----------------------------------------------------------------------------------
import java.util.*; public abstract class AbstractBinaryTree extends AbstractTree implements BinaryTree {
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) }
public int numChildren(Position p) { int count=0; if (left(p) != null) count++; if (right(p) != null) count++; return count; }
public Iterable> children(Position p) { List> snapshot = new ArrayList(2); // max capacity of 2 if (left(p) != null) snapshot.add(left(p)); if (right(p) != null) snapshot.add(right(p)); return snapshot; } } -------------------------------------------------------------------------
/** * From Data Structures and Algorithms in Java, Sixth Edition, Goodrich et al. */
/** * An interface for a binary tree, in which each node has at most two children. */
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 for this tree */ 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 for this tree */ 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 for this tree */ Position sibling(Position p) throws IllegalArgumentException; } ------------------------------------------------------------------------
public abstract class AbstractTree implements Tree { public boolean isInternal(Position p) { return numChildren(p) > 0; } public boolean isExternal(Position p) { return numChildren(p) == 0; } public boolean isRoot(Position p) { return p == root( ); } public boolean isEmpty( ) { return size( ) == 0; } }
------------------------------------------------------------------------
* * From Data Structures and Algorithms in Java, Sixth Edition, Goodrich et al. */ 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; }
-------------------------------------------------------------------------
public class LinkedBinaryTree extends AbstractBinaryTree {
//---------------- nested Node class ---------------- 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. / 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( ) { } // nonpublic utility / Validates the position and returns it as a node. / 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. / public int size( ) { return size; }
/ Returns the 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). / public Position parent(Position p) throws IllegalArgumentException { Node node = validate(p); 66 return node.getParent( ); }
/ Returns the Position of p's left child (or null if no child exists). / 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). / 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. / 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; returns its Position. / 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; returns its Position. / 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 e and returns the replaced element. / public E set(Position p, E e) throws IllegalArgumentException { Node node = validate(p); E temp = node.getElement( ); node.setElement(e); return temp; } 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 of node t1.root.setParent(node); node.setLeft(t1.root); t1.root = null; t1.size = 0; } if (!t2.isEmpty( )) { // attach t2 as right subtree of node 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. / 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( )); // childs 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; } }
1. Using your Lab 5 LinkedBinaryTree implementation, add a position and element iterator. a. Have the Tree interface extend Iterable. Add the abstract methods iterator () and positions() that return Iterator
and Iterable> respectively. b. Add the nested class and methods from your notes/text. ElementIterator, iterator(), positions() and methods required for your tree traversals. Note that your classes require the java.util.Iterator package c. Override the toString method to display a tree in the following format: Output: Structure: - B B D E - H HT D G - - F - G H 2. Create an interactive program that asks the user to work through a Yes/No decision tree with height of at least 3. You must come up with a decision tree of your own. Name your driver class PartA_Driver. E.g. of decision tree from your notes (Textbook figure 8.5 on p. 317 or L10 slide 30) Sample output: Are you nervous? (yeso) no no Will you need to access most of the money within the next 5 years? (yeso) Are you willing to accept risks in exchange for higher expected returns? (yeso) yes Stock portfolio *** End of program Notes: Iterator implementation: a. In your tree interface: Extend Iterable and add 2 abstract methods: iterator () that returns Iterator and positions() that returns Iterable> b. In the Abstract Tree class: add the nested Elementlterator class from your notes. Implement the iterator() method by returning a new instance of Elementiterator C. Add the code for 3 traversal algorithms: preorder () and its associated recursive private method postorder() and its associated recursive private method breadthfirst() import List and ArrayList from Java Class Libraries. For Queue you can use one from java.util, or add one of our implementations from class in your package e.g. ArrayQueue from Asi d. Implement the positions() method by returning an Iterable> from one of the above. Select your preferred default, and override toString() to return a simple list view of your tree in the default traversal order. toString: "indentation" of each item depends on its positions' depth in the tree your algorithm should work with any tree test this with your tree from Lab 5 decision tree: - Build the tree by assigning/re-assigning positions as you go along. Map your yeso to left/right child, and work through the decisions until an answer is reached (external node) Your code should work for any linked binary decision tree: starts at the root as the first question and advances to left/right depending on the user input i.e. do not hardcode questions/answers to work only with your tree 1. Using your Lab 5 LinkedBinaryTree implementation, add a position and element iterator. a. Have the Tree interface extend Iterable. Add the abstract methods iterator () and positions() that return Iterator and Iterable> respectively. b. Add the nested class and methods from your notes/text. ElementIterator, iterator(), positions() and methods required for your tree traversals. Note that your classes require the java.util.Iterator package c. Override the toString method to display a tree in the following format: Output: Structure: - B B D E - H HT D G - - F - G H 2. Create an interactive program that asks the user to work through a Yes/No decision tree with height of at least 3. You must come up with a decision tree of your own. Name your driver class PartA_Driver. E.g. of decision tree from your notes (Textbook figure 8.5 on p. 317 or L10 slide 30) Sample output: Are you nervous? (yeso) no no Will you need to access most of the money within the next 5 years? (yeso) Are you willing to accept risks in exchange for higher expected returns? (yeso) yes Stock portfolio *** End of program Notes: Iterator implementation: a. In your tree interface: Extend Iterable and add 2 abstract methods: iterator () that returns Iterator and positions() that returns Iterable> b. In the Abstract Tree class: add the nested Elementlterator class from your notes. Implement the iterator() method by returning a new instance of Elementiterator C. Add the code for 3 traversal algorithms: preorder () and its associated recursive private method postorder() and its associated recursive private method breadthfirst() import List and ArrayList from Java Class Libraries. For Queue you can use one from java.util, or add one of our implementations from class in your package e.g. ArrayQueue from Asi d. Implement the positions() method by returning an Iterable> from one of the above. Select your preferred default, and override toString() to return a simple list view of your tree in the default traversal order. toString: "indentation" of each item depends on its positions' depth in the tree your algorithm should work with any tree test this with your tree from Lab 5 decision tree: - Build the tree by assigning/re-assigning positions as you go along. Map your yeso to left/right child, and work through the decisions until an answer is reached (external node) Your code should work for any linked binary decision tree: starts at the root as the first question and advances to left/right depending on the user input i.e. do not hardcode questions/answers to work only with your tree
