So I am given two classes http://www2.hawaii.edu/~ztomasze/teaching/ics211/2012f

Question

So I am given two classes http://www2.hawaii.edu/~ztomasze/teaching/ics211/2012fa/hw/A10/BinarySearchTree.java and http://www2.hawaii.edu/~ztomasze/teaching/ics211/2012fa/hw/A10/TreeNode.java I then have to: add a constructor that takes a java.util.Collection, add a public String toFullString() method, and make the BST Iterable. A picture with the full directions is attached. Any help is greatly appreciated and will receive full ratings!

Explanation / Answer

package com.cramster.nov16; import java.util.Collections; import java.util.List; import java.util.ArrayList; import java.util.Collection; import java.util.Stack; import java.util.Iterator; /** * A binary search tree (BST) is a sorted ADT that uses a binary * tree to keep all elements in sorted order. If the tree is * balanced, performance is very good: O(n lg n) for most operations. * If unbalanced, it performs more like a linked list: O(n). * * @author Zach Tomaszewski */ public class BinarySearchTree { private TreeNode root = null; private int size = 0; /** Creates an empty tree. */ public BinarySearchTree() { } public BinarySearchTree(Collection collection) { List list = new ArrayList(collection); Collections.shuffle(list); for(E item : list) add(item); } public Iterator iterator() { return new TreeIterator(root); } /** Adds the given item to this BST. */ public void add(E item) { this.size++; if (this.root == null) { //tree is empty, so just add item this.root = new TreeNode(item); }else { //find where to insert, with pointer to parent node TreeNode parent = null; TreeNode curr = this.root; boolean wentLeft = true; while (curr != null) { //will execute at least once parent = curr; if (item.compareTo(curr.getData()) 0) { //go to right, saving any resulting changes node.setRight(remove(item, node.getRight())); return node; }else { //found node to be removed! if (node.getLeft() == null && node.getRight() == null) { //leaf node return null; }else if (node.getRight() == null) { //has only a left child return node.getLeft(); }else if (node.getLeft() == null) { //has only a right child return node.getRight(); }else { //two children, so replace the contents of this node with max of left tree E max = findMax(node.getLeft()); //get max value node.setLeft(remove(max, node.getLeft())); //and remove its node from tree node.setData(max); return node; } } } /** Returns the number of elements currently in this BST. */ public int size() { return this.size; } /** * Returns a single-line representation of this BST's contents. * Specifically, this is a comma-separated list of all elements in their * natural Comparable ordering. The list is surrounded by [] characters. */ @Override public String toString() { return "[" + toString(this.root) + "]"; } private String toString(TreeNode n) { //would have been simpler to use Iterator... but not implemented yet. if (n == null) { return ""; }else { String str = ""; str += toString(n.getLeft()); if (!str.isEmpty()) { str += ", "; } str += n.getData(); if (n.getRight() != null) { str += ", "; str += toString(n.getRight()); } return str; } } public String toFullString() { return toFullstring(root,""); } public String toFullstring(TreeNode n,String character) { if (n == null) { character = "|"; return ""; } else { String str = ""; if(n == root) { character = "|"; } str+= character; str += n.getData() + " " + toFullstring(n.getLeft(),character + ""); return str; } } private class TreeIterator implements Iterator { /* the class variables keep track of how much the iterator * has done so far, and what remains to be done. * root is null when the iterator has not been initialized, * or the entire tree has been visited. * the first stack keeps track of the last node to return * and all its ancestors * the second stack keeps track of whether the node visited * is to the left (false) or right (true) of its parent */ protected TreeNode root = null; protected Stack visiting = new Stack(); protected Stack visitingRightChild = new Stack(); /* only one of these booleans can be true */ boolean preorder = false; boolean inorder = true; boolean postorder = false; /* constructor for in-order traversal * @param root of the tree to traverse */ public TreeIterator(TreeNode root) { this.root = root; visiting = new Stack(); visitingRightChild = new Stack(); preorder = false; inorder = true; postorder = false; } /* constructor for pre-order or post-order traversal * @param root of the tree to traverse * @param inPreorder true if pre-order, false if post-order */ public TreeIterator(TreeNode root, boolean inPreorder) { this.root = root; visiting = new Stack(); visitingRightChild = new Stack(); preorder = inPreorder; inorder = false; postorder = ! preorder; } public boolean hasNext() { return (root != null); } public E next() { if (! hasNext()) { throw new java.util.NoSuchElementException("no more elements"); } if (preorder) { return preorderNext(); } else if (inorder) { return inorderNext(); } else if (postorder) { return postorderNext(); } else { assert(false); return null; } } // return the node at the top of the stack, push the next node if any private E preorderNext() { if (visiting.empty()) { // at beginning of iterator visiting.push(root); } TreeNode node = visiting.pop(); E result = node.getData(); // need to visit the left subtree first, then the right // since a stack is a LIFO, push the right subtree first, then // the left. Only push non-null trees if (node.getRight() != null) { visiting.push(node.getRight()); } if (node.getLeft() != null) { visiting.push(node.getLeft()); } // may not have pushed anything. If so, we are at the end if (visiting.empty()) { // no more nodes to visit root = null; } return node.getData(); } /* find the leftmost node from this root, pushing all the * intermediate nodes onto the visiting stack * @param node the root of the subtree for which we * are trying to reach the leftmost node * @changes visiting takes all nodes between node and the leftmost */ private void pushLeftmostNode(TreeNode node) { // find the leftmost node if (node != null) { visiting.push(node); // push this node pushLeftmostNode(node.getLeft()); // recurse on next left node } } /* return the leftmost node that has not yet been visited * that node is normally on top of the stack * inorder traversal doesn't use the visitingRightChild stack */ private E inorderNext() { if (visiting.empty()) { // at beginning of iterator // find the leftmost node, pushing all the intermediate nodes // onto the visiting stack pushLeftmostNode(root); } // now the leftmost unvisited node is on top of the visiting stack TreeNode node = visiting.pop(); E result = node.getData(); // this is the value to return // if the node has a right child, its leftmost node is next if (node.getRight() != null) { TreeNode right = node.getRight(); // find the leftmost node of the right child pushLeftmostNode (right); // note "node" has been replaced on the stack by its right child } // else: no right subtree, go back up the stack // next node on stack will be next returned if (visiting.empty()) { // no next node left root = null; } return result; } /* find the leftmost node from this root, pushing all the * intermediate nodes onto the visiting stack * and also stating that each is a left child of its parent * @param node the root of the subtree for which we * are trying to reach the leftmost node * @changes visiting takes all nodes between node and the leftmost */ private void pushLeftmostNodeRecord(TreeNode node) { // find the leftmost node if (node != null) { visiting.push(node); // push this node visitingRightChild.push(false); // record that it is on the left pushLeftmostNodeRecord(node.getLeft()); // continue looping } } // private E postorderNext() { if (visiting.empty()) { // at beginning of iterator // find the leftmost node, pushing all the intermediate nodes // onto the visiting stack pushLeftmostNodeRecord(root); } // the node on top of the visiting stack is the next one to be // visited, unless it has a right subtree if ((visiting.peek().getRight() == null) || // no right subtree, or (visitingRightChild.peek())) { // right subtree already visited // already visited right child, time to visit the node on top E result = visiting.pop().getData(); visitingRightChild.pop(); if (visiting.empty()) { root = null; } return result; } else { // now visit this node's right subtree // pop false and push true for visiting right child if (visitingRightChild.pop()) { assert(false); } visitingRightChild.push(true); // now push everything down to the leftmost node // in the right subtree TreeNode right = visiting.peek().getRight(); assert(right != null); pushLeftmostNodeRecord(right); // use recursive call to visit that node return postorderNext(); } } public void remove() { throw new java.lang.UnsupportedOperationException("remove"); } /* give the entire state of the iterator: the tree and the two stacks */ public String toString() { if (preorder) { return "pre: " + toString(root) + " " + visiting + " "; } if (inorder) { return "in: " + toString(root) + " " + visiting + " "; } if (postorder) { return "post: " + toString(root) + " " + visiting + " " + visitingRightChild; } return "none of pre-order, in-order, or post-order are true"; } private String toString(TreeNode node) { if (node == null) { return ""; } else { return node.toString() + "(" + toString(node.getLeft()) + ", " + toString(node.getRight()) + ")"; } } } } package com.cramster.nov16; /** * A single binary tree node. *

* Each node has both a left or right child, which can be null. * * @author Zach Tomaszewski */ public class TreeNode { private E data; private TreeNode left; private TreeNode right; /** * Constructs a new node with the given data and references to the * given left and right nodes. */ public TreeNode(E data, TreeNode left, TreeNode right) { this.data = data; this.left = left; this.right = right; } /** * Constructs a new node containing the given data. * Its left and right references will be set to null. */ public TreeNode(E data) { this(data, null, null); } /** Returns the item currently stored in this node. */ public E getData() { return data; } /** Overwrites the item stored in this Node with the given data item. */ public void setData(E data) { this.data = data; } /** * Returns this Node's left child. * If there is no left left, returns null. */ public TreeNode getLeft() { return left; } /** Causes this Node to point to the given left child Node. */ public void setLeft(TreeNode left) { this.left = left; } /** * Returns this nodes right child. * If there is no right child, returns null. */ public TreeNode getRight() { return right; } /** Causes this Node to point to the given right child Node. */ public void setRight(TreeNode right) { this.right = right; } } package com.cramster.nov16; import java.util.ArrayList; import java.util.Arrays; import java.util.Iterator; import java.util.List; public class UsernameA10 { public static void main(String[] arguments) { BinarySearchTree tree = new BinarySearchTree(); tree.add(15); tree.add(12); tree.add(18); tree.add(10); tree.add(11); tree.add(16); tree.add(17); tree.add(20); System.out.println(tree); Iterator it; it = tree.iterator(); System.out.println("Binary Tree printing through Iterator: "); while (it.hasNext()) { System.out.print(it.next() + ", "); } System.out.println(""); System.out.println(tree.toFullString()); Integer[] array = {1,2,3,4,5,6,7,8}; List list = new ArrayList(Arrays.asList(array)); BinarySearchTree tree1 = new BinarySearchTree(list); System.out.println("Bnary tree created with collections constructor :"); System.out.println(tree1); it = tree1.iterator(); System.out.println("Binary Tree printing through Iterator: "); while (it.hasNext()) { System.out.print(it.next() + ", "); } System.out.println(""); System.out.println(tree1.toFullString()); } }

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.