Question: MyTreeSet Class: 1. Constructor - set the root instance field such that it's an empty tree. 2. Add helper method (line 58) - a. Use
MyTreeSet Class: 1. Constructor - set the root instance field such that it's an empty tree. 2. Add helper method (line 58) - a. Use the compare To method** to decide if your node needs to go left or right of the root, and then call either setLeft() or setRight() (from the TreeNode class). Since we don't know if the node could be placed immediately, have setLeft() or setRight() call the add method by passing a call to the add method as your parameter for setLeft() or setRight(). This is a little different than the recursive methods we've used lately, which just returned the recursive call. Here's the general idea: 1. Check for the base case 2. If not the base case, a. if newNode needs to go on the left, call setLeft(), passing it a recursive call to this add method. b. else, call setRight( ), passing it a recursive call to this add method 3. Return the node ** Compare To method hint - Since we need to compare the node with the parameter "value" which is of the generic type Object, you need to cast that field to a Comparable type before you'll be able to use the compare To method with it. That will make your code work for any type of variable that value might be. 3. Printing Helper methods: to String, printPost and printPre (line 64-76) These are all recursive methods. Based on the traversal required, return recursive calls that will generate the correct order of the nodes. This is simpler than you would imagine. For the base case, you can return an empty String "". Main method: 1. Declare two MyTreeSet objects. 2. Declare an array of words and an array of integers. Give each array 10-15 entries, and organize them in a random order, so that the tree is pretty balanced. I will probably paste in my own arrays when I run your program. 3. Do the following for each array: a. Using a loop, add each array element to one of your MyTreeSet objects. b. Call the three print methods to display the results of each tree in the various traversals. Here's an example, using this array of Strings ("one", "TWO", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten"); Note, it's going by alphabetical order, which is confusings since these are numbers! Added: One- result: true Added: Two- result: true Added: Three- result: true Added: Four- result: true Added: Five- result: true Added: Six- result: true Added: Seven- result: true Added: Eight- result: true Added: Nine- result: true Added: Ten- result: true InOrder Traversal: ( Eight Five Four Nine One Seven Six Ten Three Two ) PostOrder Traversal: [ Eight Five Nine Four Seven Ten Sex Three Two One] PreOrder Traversal: [One Four Five Eight Nine Two Three Six Seven Ten ] - Flass Main { public static void main(String[] args) { System.out.println("Hello world!"); } } 1 | Implements a BST with TreeNode nodes 2 3 4 5 6 import java.util.Stack; import java.util.Iterator; import java.util. No SuchElementException; 7 8 9 10 @SuppressWarnings ("unchecked") // Normally, TreeNode and MyTreeSet would be "generic" (type-specific) // classes and hold comparable objects, but this is beyond the scope of // the Java Methods book. Without @SuppressWarnings, this class would give // three "Unchecked cast" warnings. 11 12 13 14 15 16 17 18 public class MyTreeSet implements Iterable { //instance field for the root private TreeNode root; //constructor to create an empty BST 19 20 21 22 23 24 // Returns true if value has been added; otherwise returns false. public boolean add(Object value) { root = add(root, value); return true; } 25 26 27 28 29 30 31 32 33 34 35 36 37 // These 3 methods each return a different string representation of this BST. public String toString() { return "[" + toString(root) + "]"; } public String printPre() { return "[" + printPre(root) + "]"; } 38 39 40 41 42 43 public String printPost() { return "[" + printPost (root) + "]"; } 44 45 46 47 48 49 50 51 52 53 // Returns an iterator for this BST. public Iterator iterator() { return new MyTreeSetIterator(root); } //oloko colocok //*************** Private helper methods: ********************* //************************************************************* // Adds value to the BST rooted at node. Returns the // root of the new tree. // Precondition: the tree rooted at node does not contain value. 54 55 56 57 private TreeNode add (TreeNode node, Object value) { //you'll code this method, using recursion. return null; } // Returns a string representation of the tree rooted at node, in the inorder traversal. private String toString(TreeNode node) { //you'll code this, using recursion return null; } // Returns a string representation of the tree rooted at node, in the Postorder traversal. private String printPost(TreeNode node) //you'll code this, using recursion return null; 1/ Returns a string representation of the tree rooted at node, in the PreOrder traversal. private String print Pre (TreeNode node) //you'll code this, using recursion return null; } //** *** // Implements an Iterator for this tree. //****************************************** private class MyTreeSetIterator implements Iterator private StackTreeNode> stk; public MyTreeSetIterator(TreeNode root) stk = new StackTreeNode>(); TreeNode node = root; while (node != null) { stk.push(node); node = node.getLeft(); } } public boolean hasNext() return !stk. isEmpty(); } public Object next() if (stk.isEmpty()) throw new No SuchelementException(); TreeNode node = stk.pop(); Object obj = node.getValue(); node = node.getRight(); while (node != null) { stk.push(node); node = node.getLeft(); } return obj; } public void remove() throw new UnsupportedoperationException(); 1 public class TreeNode 2 { 3 private Object value; 4 private TreeNode left; 5 private TreeNode right; 6 7 public TreeNode(Object initValue) 8 E { 9 value = initValue; 10 left = null; 11 right = null; 12 } 13 14 public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight) 15 { 16 value = initValue; 17 left = initLeft; 18 right = initRight; } 19 20 public Object getValue() { return value; } 21 22 public TreeNode getLeft() { return left; } 23 24 public TreeNode getRight() { return right; } 25 26 public void setValue(Object theNewValue) { value = theNewValue; } 27 28 public void setLeft(TreeNode theNewLeft) { left = theNewLeft; } 29 30 public void setRight (TreeNode theNewRight) { right = theNewRight; } 31 32 } 33 MyTreeSet Class: 1. Constructor - set the root instance field such that it's an empty tree. 2. Add helper method (line 58) - a. Use the compare To method** to decide if your node needs to go left or right of the root, and then call either setLeft() or setRight() (from the TreeNode class). Since we don't know if the node could be placed immediately, have setLeft() or setRight() call the add method by passing a call to the add method as your parameter for setLeft() or setRight(). This is a little different than the recursive methods we've used lately, which just returned the recursive call. Here's the general idea: 1. Check for the base case 2. If not the base case, a. if newNode needs to go on the left, call setLeft(), passing it a recursive call to this add method. b. else, call setRight( ), passing it a recursive call to this add method 3. Return the node ** Compare To method hint - Since we need to compare the node with the parameter "value" which is of the generic type Object, you need to cast that field to a Comparable type before you'll be able to use the compare To method with it. That will make your code work for any type of variable that value might be. 3. Printing Helper methods: to String, printPost and printPre (line 64-76) These are all recursive methods. Based on the traversal required, return recursive calls that will generate the correct order of the nodes. This is simpler than you would imagine. For the base case, you can return an empty String "". Main method: 1. Declare two MyTreeSet objects. 2. Declare an array of words and an array of integers. Give each array 10-15 entries, and organize them in a random order, so that the tree is pretty balanced. I will probably paste in my own arrays when I run your program. 3. Do the following for each array: a. Using a loop, add each array element to one of your MyTreeSet objects. b. Call the three print methods to display the results of each tree in the various traversals. Here's an example, using this array of Strings ("one", "TWO", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten"); Note, it's going by alphabetical order, which is confusings since these are numbers! Added: One- result: true Added: Two- result: true Added: Three- result: true Added: Four- result: true Added: Five- result: true Added: Six- result: true Added: Seven- result: true Added: Eight- result: true Added: Nine- result: true Added: Ten- result: true InOrder Traversal: ( Eight Five Four Nine One Seven Six Ten Three Two ) PostOrder Traversal: [ Eight Five Nine Four Seven Ten Sex Three Two One] PreOrder Traversal: [One Four Five Eight Nine Two Three Six Seven Ten ] - Flass Main { public static void main(String[] args) { System.out.println("Hello world!"); } } 1 | Implements a BST with TreeNode nodes 2 3 4 5 6 import java.util.Stack; import java.util.Iterator; import java.util. No SuchElementException; 7 8 9 10 @SuppressWarnings ("unchecked") // Normally, TreeNode and MyTreeSet would be "generic" (type-specific) // classes and hold comparable objects, but this is beyond the scope of // the Java Methods book. Without @SuppressWarnings, this class would give // three "Unchecked cast" warnings. 11 12 13 14 15 16 17 18 public class MyTreeSet implements Iterable { //instance field for the root private TreeNode root; //constructor to create an empty BST 19 20 21 22 23 24 // Returns true if value has been added; otherwise returns false. public boolean add(Object value) { root = add(root, value); return true; } 25 26 27 28 29 30 31 32 33 34 35 36 37 // These 3 methods each return a different string representation of this BST. public String toString() { return "[" + toString(root) + "]"; } public String printPre() { return "[" + printPre(root) + "]"; } 38 39 40 41 42 43 public String printPost() { return "[" + printPost (root) + "]"; } 44 45 46 47 48 49 50 51 52 53 // Returns an iterator for this BST. public Iterator iterator() { return new MyTreeSetIterator(root); } //oloko colocok //*************** Private helper methods: ********************* //************************************************************* // Adds value to the BST rooted at node. Returns the // root of the new tree. // Precondition: the tree rooted at node does not contain value. 54 55 56 57 private TreeNode add (TreeNode node, Object value) { //you'll code this method, using recursion. return null; } // Returns a string representation of the tree rooted at node, in the inorder traversal. private String toString(TreeNode node) { //you'll code this, using recursion return null; } // Returns a string representation of the tree rooted at node, in the Postorder traversal. private String printPost(TreeNode node) //you'll code this, using recursion return null; 1/ Returns a string representation of the tree rooted at node, in the PreOrder traversal. private String print Pre (TreeNode node) //you'll code this, using recursion return null; } //** *** // Implements an Iterator for this tree. //****************************************** private class MyTreeSetIterator implements Iterator private StackTreeNode> stk; public MyTreeSetIterator(TreeNode root) stk = new StackTreeNode>(); TreeNode node = root; while (node != null) { stk.push(node); node = node.getLeft(); } } public boolean hasNext() return !stk. isEmpty(); } public Object next() if (stk.isEmpty()) throw new No SuchelementException(); TreeNode node = stk.pop(); Object obj = node.getValue(); node = node.getRight(); while (node != null) { stk.push(node); node = node.getLeft(); } return obj; } public void remove() throw new UnsupportedoperationException(); 1 public class TreeNode 2 { 3 private Object value; 4 private TreeNode left; 5 private TreeNode right; 6 7 public TreeNode(Object initValue) 8 E { 9 value = initValue; 10 left = null; 11 right = null; 12 } 13 14 public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight) 15 { 16 value = initValue; 17 left = initLeft; 18 right = initRight; } 19 20 public Object getValue() { return value; } 21 22 public TreeNode getLeft() { return left; } 23 24 public TreeNode getRight() { return right; } 25 26 public void setValue(Object theNewValue) { value = theNewValue; } 27 28 public void setLeft(TreeNode theNewLeft) { left = theNewLeft; } 29 30 public void setRight (TreeNode theNewRight) { right = theNewRight; } 31 32 } 33
Study Help