need help with this. IntTree.java with the following methods added: A. slightStu
ID: 3848260 • Letter: N
Question
need help with this. IntTree.java with the following methods added:
A. slightStutter(); a public non-recursive method that changes this tree to add stutter nodes on the left when possible, otherwise add a stutter node on the right, but if both left and right are not null then the node cannot be stuttered. replaces every node in the tree with two occurrences of that node.
B. slightStutter(IntTreeNode root); a private recursive method helper, returns an IntTreeNode, that does the tree traversal and modification for public slightStutter You can use : IntTree.javaPreview the documentView in a new window I will also use IntTreeNode.javaPreview the documentView in a new window as is, no changes.
At the very bottom I have the test code.
public class IntTreeNode {
public int data;
public IntTreeNode left;
public IntTreeNode right;
// constructs a leaf node with given data
public IntTreeNode(int data) {
this(data, null, null);
}
// constructs a branch node with given data, left subtree,
// right subtree
public IntTreeNode(int data, IntTreeNode left,
IntTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
import java.util.*;
public class IntTree {
private IntTreeNode overallRoot;
// pre : max > 0
// post: constructs a sequential tree with given number of
// nodes
public IntTree(int max) {
if (max <= 0) {
throw new IllegalArgumentException("max: " + max);
}
overallRoot = buildTree(1, max);
}
public IntTree() {
overallRoot = null;
}
// constructor added so we can build page 1029 reference trees
public IntTree(IntTreeNode given) {
overallRoot = given;
}
//Exercise #7, Chapter 17
public boolean isFull() {
return (overallRoot == null || isFull(overallRoot));
}
private boolean isFull(IntTreeNode root) {
if(root.left == null && root.right == null) {
return true;
} else {
return (root.left != null && root.right != null && isFull(root.left) && isFull(root.right));
}
}
// post: returns a sequential tree with n as its root unless
// n is greater than max, in which case it returns an
// empty tree
private IntTreeNode buildTree(int n, int max) {
if (n > max) {
return null;
} else {
return new IntTreeNode(n, buildTree(2 * n, max),
buildTree(2 * n + 1, max));
}
}
// post: prints the tree contents using a preorder traversal
public void printPreorder() {
System.out.print("preorder:");
printPreorder(overallRoot);
System.out.println();
}
// post: prints the tree contents using a preorder traversal
// post: prints in preorder the tree with given root
private void printPreorder(IntTreeNode root) {
if (root != null) {
System.out.print(" " + root.data);
printPreorder(root.left);
printPreorder(root.right);
}
}
// post: prints the tree contents using a inorder traversal
public void printInorder() {
System.out.print("inorder:");
printInorder(overallRoot);
System.out.println();
}
// post: prints in inorder the tree with given root
private void printInorder(IntTreeNode root) {
if (root != null) {
printInorder(root.left);
System.out.print(" " + root.data);
printInorder(root.right);
}
}
// post: prints the tree contents using a postorder traversal
public void printPostorder() {
System.out.print("postorder:");
printPostorder(overallRoot);
System.out.println();
}
// post: prints in postorder the tree with given root
private void printPostorder(IntTreeNode root) {
if (root != null) {
printPostorder(root.left);
printPostorder(root.right);
System.out.print(" " + root.data);
}
}
// post: prints the tree contents, one per line, following an
// inorder traversal and using indentation to indicate
// node depth; prints right to left so that it looks
// correct when the output is rotated.
public void printSideways() {
printSideways(overallRoot, 0);
}
// post: prints in reversed preorder the tree with given
// root, indenting each line to the given level
private void printSideways(IntTreeNode root, int level) {
if (root != null) {
printSideways(root.right, level + 1);
for (int i = 0; i < level; i++) {
System.out.print(" ");
}
System.out.println(root.data);
printSideways(root.left, level + 1);
}
}
Test code..
public class Post {
public static void main(String[] args) {
IntTree tree =
new IntTree(new IntTreeNode(9,new IntTreeNode(8),new IntTreeNode(7)));
tree.printSideways();
tree.slightStutter();
System.out.println("---------------------------------");
tree.printSideways();
}
}
Explanation / Answer
public class TreeSet<T> extends AbstractSet<T>
85: implements NavigableSet<T>, Cloneable, Serializable
86: {
87: /**
88: * Compatible with JDK 1.2.
89: */
90: private static final long serialVersionUID = -2479143000061671589L;
91:
92: /**
93: * The NavigableMap which backs this Set.
94: */
95: // Not final because of readObject. This will always be one of TreeMap or
96: // TreeMap.SubMap, which both extend AbstractMap.
97: private transient NavigableMap<T, String> map;
98:
99: /**
100: * Construct a new TreeSet whose backing TreeMap using the "natural"
101: * ordering of keys. Elements that are not mutually comparable will cause
102: * ClassCastExceptions down the road.
103: *
104: * @see Comparable
105: */
106: public TreeSet()
107: {
108: map = new TreeMap<T, String>();
109: }
110:
111: /**
112: * Construct a new TreeSet whose backing TreeMap uses the supplied
113: * Comparator. Elements that are not mutually comparable will cause
114: * ClassCastExceptions down the road.
115: *
116: * @param comparator the Comparator this Set will use
117: */
118: public TreeSet(Comparator<? super T> comparator)
119: {
120: map = new TreeMap<T, String>(comparator);
121: }
122:
123: /**
124: * Construct a new TreeSet whose backing TreeMap uses the "natural"
125: * orering of the keys and which contains all of the elements in the
126: * supplied Collection. This runs in n*log(n) time.
127: *
128: * @param collection the new Set will be initialized with all
129: * of the elements in this Collection
130: * @throws ClassCastException if the elements of the collection are not
131: * comparable
132: * @throws NullPointerException if the collection is null
133: * @see Comparable
134: */
135: public TreeSet(Collection<? extends T> collection)
136: {
137: map = new TreeMap<T, String>();
138: addAll(collection);
139: }
140:
141: /**
142: * Construct a new TreeSet, using the same key ordering as the supplied
143: * SortedSet and containing all of the elements in the supplied SortedSet.
144: * This constructor runs in linear time.
145: *
146: * @param sortedSet the new TreeSet will use this SortedSet's comparator
147: * and will initialize itself with all its elements
148: * @throws NullPointerException if sortedSet is null
149: */
150: public TreeSet(SortedSet<T> sortedSet)
151: {
152: Iterator<T> itr;
153:
154: map = new TreeMap<T, String>
155: ((Comparator<? super T>)sortedSet.comparator());
156: itr = ((SortedSet<T>) sortedSet).iterator();
157: ((TreeMap<T, String>) map).putKeysLinear(itr, sortedSet.size());
158: }
159:
160: /**
161: * This private constructor is used to implement the subSet() calls around
162: * a backing TreeMap.SubMap.
163: *
164: * @param backingMap the submap
165: */
166: private TreeSet(NavigableMap<T,String> backingMap)
167: {
168: map = backingMap;
169: }
170:
171: /**
172: * Adds the spplied Object to the Set if it is not already in the Set;
173: * returns true if the element is added, false otherwise.
174: *
175: * @param obj the Object to be added to this Set
176: * @throws ClassCastException if the element cannot be compared with objects
177: * already in the set
178: */
179: public boolean add(T obj)
180: {
181: return map.put(obj, "") == null;
182: }
183:
184: /**
185: * Adds all of the elements in the supplied Collection to this TreeSet.
186: *
187: * @param c The collection to add
188: * @return true if the Set is altered, false otherwise
189: * @throws NullPointerException if c is null
190: * @throws ClassCastException if an element in c cannot be compared with
191: * objects already in the set
192: */
193: public boolean addAll(Collection<? extends T> c)
194: {
195: boolean result = false;
196: int pos = c.size();
197: Iterator<? extends T> itr = c.iterator();
198: while (--pos >= 0)
199: result |= (map.put(itr.next(), "") == null);
200: return result;
201: }
202:
203: /**
204: * Removes all elements in this Set.
205: */
206: public void clear()
207: {
208: map.clear();
209: }
210:
211: /**
212: * Returns a shallow copy of this Set. The elements are not cloned.
213: *
214: * @return the cloned set
215: */
216: public Object clone()
217: {
218: TreeSet<T> copy = null;
219: try
220: {
221: copy = (TreeSet<T>) super.clone();
222: // Map may be either TreeMap or TreeMap.SubMap, hence the ugly casts.
223: copy.map = (NavigableMap<T, String>) ((AbstractMap<T, String>) map).clone();
224: }
225: catch (CloneNotSupportedException x)
226: {
227: // Impossible result.
228: }
229: return copy;
230: }
231:
232: /**
233: * Returns this Set's comparator.
234: *
235: * @return the comparator, or null if the set uses natural ordering
236: */
237: public Comparator<? super T> comparator()
238: {
239: return map.comparator();
240: }
241:
242: /**
243: * Returns true if this Set contains the supplied Object, false otherwise.
244: *
245: * @param obj the Object to check for
246: * @return true if it is in the set
247: * @throws ClassCastException if obj cannot be compared with objects
248: * already in the set
249: */
250: public boolean contains(Object obj)
251: {
252: return map.containsKey(obj);
253: }
254:
255: /**
256: * Returns the first (by order) element in this Set.
257: *
258: * @return the first element
259: * @throws NoSuchElementException if the set is empty
260: */
261: public T first()
262: {
263: return map.firstKey();
264: }
265:
266: /**
267: * Returns a view of this Set including all elements less than
268: * <code>to</code>. The returned set is backed by the original, so changes
269: * in one appear in the other. The subset will throw an
270: * {@link IllegalArgumentException} for any attempt to access or add an
271: * element beyond the specified cutoff. The returned set does not include
272: * the endpoint; if you want inclusion, pass the successor element or
273: * call {@link #headSet(T,boolean)}. This call is equivalent to
274: * <code>headSet(to, false)</code>.
275: *
276: * @param to the (exclusive) cutoff point
277: * @return a view of the set less than the cutoff
278: * @throws ClassCastException if <code>to</code> is not compatible with
279: * the comparator (or is not Comparable, for natural ordering)
280: * @throws NullPointerException if to is null, but the comparator does not
281: * tolerate null elements
282: */
283: public SortedSet<T> headSet(T to)
284: {
285: return headSet(to, false);
286: }
287:
288: /**
289: * Returns a view of this Set including all elements less than
290: * (or equal to, if <code>inclusive</code> is true) <code>to</code>.
291: * The returned set is backed by the original, so changes
292: * in one appear in the other. The subset will throw an
293: * {@link IllegalArgumentException} for any attempt to access or add an
294: * element beyond the specified cutoff.
295: *
296: * @param to the cutoff point
297: * @param inclusive true if <code>to</code> should be included.
298: * @return a view of the set for the specified range.
299: * @throws ClassCastException if <code>to</code> is not compatible with
300: * the comparator (or is not Comparable, for natural ordering)
301: * @throws NullPointerException if to is null, but the comparator does not
302: * tolerate null elements
303: */
304: public NavigableSet<T> headSet(T to, boolean inclusive)
305: {
306: return new TreeSet<T>(map.headMap(to, inclusive));
307: }
308:
309: /**
310: * Returns true if this Set has size 0, false otherwise.
311: *
312: * @return true if the set is empty
313: */
314: public boolean isEmpty()
315: {
316: return map.isEmpty();
317: }
318:
319: /**
320: * Returns in Iterator over the elements in this TreeSet, which traverses
321: * in ascending order.
322: *
323: * @return an iterator
324: */
325: public Iterator<T> iterator()
326: {
327: return map.keySet().iterator();
328: }
329:
330: /**
331: * Returns the last (by order) element in this Set.
332: *
333: * @return the last element
334: * @throws NoSuchElementException if the set is empty
335: */
336: public T last()
337: {
338: return map.lastKey();
339: }
340:
341: /**
342: * If the supplied Object is in this Set, it is removed, and true is
343: * returned; otherwise, false is returned.
344: *
345: * @param obj the Object to remove from this Set
346: * @return true if the set was modified
347: * @throws ClassCastException if obj cannot be compared to set elements
348: */
349: public boolean remove(Object obj)
350: {
351: return map.remove(obj) != null;
352: }
353:
354: /**
355: * Returns the number of elements in this Set
356: *
357: * @return the set size
358: */
359: public int size()
360: {
361: return map.size();
362: }
363:
364: /**
365: * Returns a view of this Set including all elements greater or equal to
366: * <code>from</code> and less than <code>to</code> (a half-open interval).
367: * The returned set is backed by the original, so changes in one appear in
368: * the other. The subset will throw an {@link IllegalArgumentException}
369: * for any attempt to access or add an element beyond the specified cutoffs.
370: * The returned set includes the low endpoint but not the high; if you want
371: * to reverse this behavior on either end, pass in the successor element
372: * or call {@link #subSet(T,boolean,T,boolean)}. This is equivalent to
373: * calling <code>subSet(from,true,to,false)</code>.
374: *
375: * @param from the (inclusive) low cutoff point
376: * @param to the (exclusive) high cutoff point
377: * @return a view of the set between the cutoffs
378: * @throws ClassCastException if either cutoff is not compatible with
379: * the comparator (or is not Comparable, for natural ordering)
380: * @throws NullPointerException if from or to is null, but the comparator
381: * does not tolerate null elements
382: * @throws IllegalArgumentException if from is greater than to
383: */
384: public SortedSet<T> subSet(T from, T to)
385: {
386: return subSet(from, true, to, false);
387: }
388:
389: /**
390: * Returns a view of this Set including all elements greater than (or equal to,
391: * if <code>fromInclusive</code> is true</code> <code>from</code> and less than
392: * (or equal to, if <code>toInclusive</code> is true) <code>to</code>.
393: * The returned set is backed by the original, so changes in one appear in
394: * the other. The subset will throw an {@link IllegalArgumentException}
395: * for any attempt to access or add an element beyond the specified cutoffs.
396: *
397: * @param from the low cutoff point
398: * @param fromInclusive true if <code>from</code> should be included.
399: * @param to the high cutoff point
400: * @param toInclusive true if <code>to</code> should be included.
401: * @return a view of the set for the specified range.
402: * @throws ClassCastException if either cutoff is not compatible with
403: * the comparator (or is not Comparable, for natural ordering)
404: * @throws NullPointerException if from or to is null, but the comparator
405: * does not tolerate null elements
406: * @throws IllegalArgumentException if from is greater than to
407: */
408: public NavigableSet<T> subSet(T from, boolean fromInclusive,
409: T to, boolean toInclusive)
410: {
411: return new TreeSet<T>(map.subMap(from, fromInclusive,
412: to, toInclusive));
413: }
414:
415: /**
416: * Returns a view of this Set including all elements greater or equal to
417: * <code>from</code>. The returned set is backed by the original, so
418: * changes in one appear in the other. The subset will throw an
419: * {@link IllegalArgumentException} for any attempt to access or add an
420: * element beyond the specified cutoff. The returned set includes the
421: * endpoint; if you want to exclude it, pass in the successor element
422: * or call {@link #tailSet(T,boolean)}. This is equivalent to calling
423: * <code>tailSet(from, true)</code>.
424: *
425: * @param from the (inclusive) low cutoff point
426: * @return a view of the set above the cutoff
427: * @throws ClassCastException if <code>from</code> is not compatible with
428: * the comparator (or is not Comparable, for natural ordering)
429: * @throws NullPointerException if from is null, but the comparator
430: * does not tolerate null elements
431: */
432: public SortedSet<T> tailSet(T from)
433: {
434: return tailSet(from, true);
435: }
436:
437: /**
438: * Returns a view of this Set including all elements greater (or equal to,
439: * if <code>inclusive</code> is true) <code>from</code>. The returned set
440: * is backed by the original, so changes in one appear in the other. The
441: * subset will throw an {@link IllegalArgumentException} for any attempt
442: * to access or add an element beyond the specified cutoff.
443: *
444: * @param from the low cutoff point.
445: * @param inclusive true if <code>from</code> should be included.
446: * @return a view of the set for the specified range.
447: * @throws ClassCastException if <code>from</code> is not compatible with
448: * the comparator (or is not Comparable, for natural ordering)
449: * @throws NullPointerException if from is null, but the comparator
450: * does not tolerate null elements
451: */
452: public NavigableSet<T> tailSet(T from, boolean inclusive)
453: {
454: return new TreeSet<T>(map.tailMap(from, inclusive));
455: }
456:
457: /**
458: * Serializes this object to the given stream.
459: *
460: * @param s the stream to write to
461: * @throws IOException if the underlying stream fails
462: * @serialData the <i>comparator</i> (Object), followed by the set size
463: * (int), the the elements in sorted order (Object)
464: */
465: private void writeObject(ObjectOutputStream s) throws IOException
466: {
467: s.defaultWriteObject();
468: Iterator<T> itr = map.keySet().iterator();
469: int pos = map.size();
470: s.writeObject(map.comparator());
471: s.writeInt(pos);
472: while (--pos >= 0)
473: s.writeObject(itr.next());
474: }
475:
476: /**
477: * Deserializes this object from the given stream.
478: *
479: * @param s the stream to read from
480: * @throws ClassNotFoundException if the underlying stream fails
481: * @throws IOException if the underlying stream fails
482: * @serialData the <i>comparator</i> (Object), followed by the set size
483: * (int), the the elements in sorted order (Object)
484: */
485: private void readObject(ObjectInputStream s)
486: throws IOException, ClassNotFoundException
487: {
488: s.defaultReadObject();
489: Comparator<? super T> comparator = (Comparator<? super T>) s.readObject();
490: int size = s.readInt();
491: map = new TreeMap<T, String>(comparator);
492: ((TreeMap<T, String>) map).putFromObjStream(s, size, false);
493: }
494:
495: /**
496: * Returns the least or lowest element in the set greater than or
497: * equal to the given element, or <code>null</code> if there is
498: * no such element.
499: *
500: * @param e the element relative to the returned element.
501: * @return the least element greater than or equal
502: * to the given element, or <code>null</code> if there is
503: * no such element.
504: * @throws ClassCastException if the specified element can not
505: * be compared with those in the map.
506: * @throws NullPointerException if the element is <code>null</code>
507: * and this set either uses natural
508: * ordering or a comparator that does
509: * not permit null elements.
510: * @since 1.6
511: */
512: public T ceiling(T e)
513: {
514: return map.ceilingKey(e);
515: }
516:
517: /**
518: * Returns an iterator over the elements of this set in descending
519: * order. This is equivalent to calling
520: * <code>descendingSet().iterator()</code>.
521: *
522: * @return an iterator over the elements in descending order.
523: * @since 1.6
524: */
525: public Iterator<T> descendingIterator()
526: {
527: return descendingSet().iterator();
528: }
529:
530: /**
531: * Returns a view of the set in reverse order. The descending set
532: * is backed by the original set, so that changes affect both sets.
533: * Any changes occurring to either set while an iteration is taking
534: * place (with the exception of a {@link Iterator#remove()} operation)
535: * result in undefined behaviour from the iteration. The ordering
536: * of the descending set is the same as for a set with a
537: * {@link Comparator} given by {@link Collections#reverseOrder()},
538: * and calling {@link #descendingSet()} on the descending set itself
539: * results in a view equivalent to the original set.
540: *
541: * @return a reverse order view of the set.
542: * @since 1.6
543: */
544: public NavigableSet<T> descendingSet()
545: {
546: return map.descendingKeySet();
547: }
548:
549: /**
550: * Returns the greatest or highest element in the set less than or
551: * equal to the given element, or <code>null</code> if there is
552: * no such element.
553: *
554: * @param e the element relative to the returned element.
555: * @return the greatest element less than or equal
556: * to the given element, or <code>null</code> if there is
557: * no such element.
558: * @throws ClassCastException if the specified element can not
559: * be compared with those in the map.
560: * @throws NullPointerException if the element is <code>null</code>
561: * and this set either uses natural
562: * ordering or a comparator that does
563: * not permit null elements.
564: * @since 1.6
565: */
566: public T floor(T e)
567: {
568: return map.floorKey(e);
569: }
570:
571: /**
572: * Returns the least or lowest element in the set strictly greater
573: * than the given element, or <code>null</code> if there is
574: * no such element.
575: *
576: * @param e the element relative to the returned element.
577: * @return the least element greater than
578: * the given element, or <code>null</code> if there is
579: * no such element.
580: * @throws ClassCastException if the specified element can not
581: * be compared with those in the map.
582: * @throws NullPointerException if the element is <code>null</code>
583: * and this set either uses natural
584: * ordering or a comparator that does
585: * not permit null elements.
586: * @since 1.6
587: */
588: public T higher(T e)
589: {
590: return map.higherKey(e);
591: }
592:
593: /**
594: * Returns the greatest or highest element in the set strictly less
595: * than the given element, or <code>null</code> if there is
596: * no such element.
597: *
598: * @param e the element relative to the returned element.
599: * @return the greatest element less than
600: * the given element, or <code>null</code> if there is
601: * no such element.
602: * @throws ClassCastException if the specified element can not
603: * be compared with those in the map.
604: * @throws NullPointerException if the element is <code>null</code>
605: * and this set either uses natural
606: * ordering or a comparator that does
607: * not permit null elements.
608: * @since 1.6
609: */
610: public T lower(T e)
611: {
612: return map.lowerKey(e);
613: }
614:
615: /**
616: * Removes and returns the least or lowest element in the set,
617: * or <code>null</code> if the map is empty.
618: *
619: * @return the removed first element, or <code>null</code> if the
620: * map is empty.
621: * @since 1.6
622: */
623: public T pollFirst()
624: {
625: return map.pollFirstEntry().getKey();
626: }
627:
628: /**
629: * Removes and returns the greatest or highest element in the set,
630: * or <code>null</code> if the map is empty.
631: *
632: * @return the removed last element, or <code>null</code> if the
633: * map is empty.
634: * @since 1.6
635: */
636: public T pollLast()
637: {
return map.pollLastEntry().getKey();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.