For the code below complete the preOrder() method so that it performs a preOrder traversal of the tree. For each node it traverses, it should call sb.append() to add a "[" the results of traversing the subtree rooted at that node, and then a "]". You should add a space before the results of the left and right child traversals, but only if the node exists.
code:
package edu.buffalo.cse116; import java.util.AbstractSet; import java.util.Iterator; public class BinarySearchTree<E extends Comparable<E>> extends AbstractSet<E> { protected Entry<E> root; protected int size; /** * Initializes this BinarySearchTree object to be empty, to contain only * elements of type E, to be ordered by the Comparable interface, and to * contain no duplicate elements. */ public BinarySearchTree() { root = null; size = 0; } /** * Initializes this BinarySearchTree object to contain a shallow copy of a * specified BinarySearchTree object. The worstTime(n) is O(n), where n is the * number of elements in the specified BinarySearchTree object. * * @param otherTree - the specified BinarySearchTree object that this * BinarySearchTree object will be assigned a shallow copy of. */ public BinarySearchTree(BinarySearchTree<? extends E> otherTree) { root = copy(otherTree.root, null); size = otherTree.size; } /* Method to complete is here! */ public void preOrder(Entry<E> ent, StringBuilder sb) { // TODO: Complete me! } protected Entry<E> copy(Entry<? extends E> p, Entry<E> parent) { if (p != null) { Entry<E> q = new Entry<E>(p.element, parent); q.left = copy(p.left, q); q.right = copy(p.right, q); return q; } return null; } // method copy @SuppressWarnings("unchecked") @Override public boolean equals(Object obj) { if (!(obj instanceof BinarySearchTree)) { return false; } return equals(root, ((BinarySearchTree<? extends E>) obj).root); } public boolean equals(Entry<E> p, Entry<? extends E> q) { if ((p == null) || (q == null)) { return p == q; } if (!p.element.equals(q.element)) { return false; } if (equals(p.left, q.left) && equals(p.right, q.right)) { return true; } return false; } /** * Returns the size of this BinarySearchTree object. * * @return the size of this BinarySearchTree object. */ @Override public int size() { return size; } /** * Iterator method will be implemented for a future * * @return an iterator positioned at the smallest element in this * BinarySearchTree object. */ @Override public Iterator<E> iterator() { throw new UnsupportedOperationException("Not implemented yet!"); } /** * Determines if there is at least one element in this BinarySearchTree object * that equals a specified element. The worstTime(n) is O(n) and * averageTime(n) is O(log n). * * @param obj - the element sought in this BinarySearchTree object. * @return true - if there is an element in this BinarySearchTree object that * equals obj; otherwise, return false. * @throws ClassCastException - if obj cannot be compared to the elements in * this BinarySearchTree object. * @throws NullPointerException - if obj is null. */ @Override public boolean contains(Object obj) { return getEntry(obj) != null; } /** * Ensures that this BinarySearchTree object contains a specified element. The * worstTime(n) is O(n) and averageTime(n) is O(log n). * * @param element - the element whose presence is ensured in this * BinarySearchTree object. * @return true - if this BinarySearchTree object changed as a result of this * method call (that is, if element was actually inserted); otherwise, * return false. * @throws ClassCastException - if element cannot be compared to the elements * already in this BinarySearchTree object. * @throws NullPointerException - if element is null. */ @Override public boolean add(E element) { if (root == null) { if (element == null) { throw new NullPointerException(); } root = new Entry<E>(element, null); size++ ; return true; } else { Entry<E> temp = root; int comp; while (true) { comp = element.compareTo(temp.element); if (comp == 0) { return false; } if (comp < 0) { if (temp.left != null) { temp = temp.left; } else { temp.left = new Entry<E>(element, temp); size++ ; return true; } // temp.left == null } else if (temp.right != null) { temp = temp.right; } else { temp.right = new Entry<E>(element, temp); size++ ; return true; } // temp.right == null } // while } // root not null } // method add /** * Ensures that this BinarySearchTree object does not contain a specified * element. The worstTime(n) is O(n) and averageTime(n) is O(log n). * * @param obj - the object whose absence is ensured in this BinarySearchTree * object. * @return true - if this BinarySearchTree object changed as a result of this * method call (that is, if obj was actually removed); otherwise, * return false. * @throws ClassCastException - if obj cannot be compared to the elements * already in this BinarySearchTree object. * @throws NullPointerException - if obj is null. */ @Override public boolean remove(Object obj) { Entry<E> e = getEntry(obj); if (e == null) { return false; } deleteEntry(e); return true; } /** * Finds the Entry object that houses a specified element, if there is such an * Entry. The worstTime(n) is O(n), and averageTime(n) is O(log n). * * @param obj - the element whose Entry is sought. * @return the Entry object that houses obj - if there is such an Entry; * otherwise, return null. * @throws ClassCastException - if obj is not comparable to the elements * already in this BinarySearchTree object. * @throws NullPointerException - if obj is null. */ @SuppressWarnings("unchecked") protected Entry<E> getEntry(Object obj) { int comp; if (obj == null) { throw new NullPointerException(); } if (!(obj instanceof Comparable)) { return null; } Comparable<E> compObj = (Comparable<E>) obj; Entry<E> e = root; while (e != null) { comp = compObj.compareTo(e.element); if (comp == 0) { return e; } else if (comp < 0) { e = e.left; } else { e = e.right; } } // while return null; } /** * Deletes the element in a specified Entry object from this BinarySearchTree. * * @param p - the Entry object whose element is to be deleted from this * BinarySearchTree object. * @return the Entry object that was actually deleted from this * BinarySearchTree object. */ protected Entry<E> deleteEntry(Entry<E> p) { size-- ; // If p has two children, replace p's element with p's successor's // element, then make p reference that successor. if ((p.left != null) && (p.right != null)) { Entry<E> s = successor(p); p.element = s.element; p = s; } // p had two children // At this point, p has either no children or one child. Entry<E> replacement; if (p.left != null) { replacement = p.left; } else { replacement = p.right; } // If p has at least one child, link replacement to p.parent. if (replacement != null) { replacement.parent = p.parent; if (p.parent == null) { root = replacement; } else if (p == p.parent.left) { p.parent.left = replacement; } else { p.parent.right = replacement; } } // p has at least one child else if (p.parent == null) { root = null; } else { if (p == p.parent.left) { p.parent.left = null; } else { p.parent.right = null; } } // p has a parent but no children return p; } // method deleteEntry /** * Finds the successor of a specified Entry object in this BinarySearchTree. * The worstTime(n) is O(n) and averageTime(n) is constant. * * @param e - the Entry object whose successor is to be found. * @return the successor of e, if e has a successor; otherwise, return null. */ protected Entry<E> successor(Entry<E> e) { if (e == null) { return null; } else if (e.right != null) { // successor is leftmost Entry in right subtree of e Entry<E> p = e.right; while (p.left != null) { p = p.left; } return p; } // e has a right child else { // go up the tree to the left as far as possible, then go up // to the right. Entry<E> p = e.parent; Entry<E> ch = e; while ((p != null) && (ch == p.right)) { ch = p; p = p.parent; } // while return p; } // e has no right child } // method successor @Override public String toString() { StringBuilder sb = new StringBuilder(); preOrder(root, sb); return sb.toString(); } protected static class Entry<E> { protected E element; protected Entry<E> left = null, right = null, parent; /** * Initializes this Entry object. This default constructor is defined for * the sake of subclasses of the BinarySearchTree class. */ public Entry() {} /** * Initializes this Entry object from element and parent. */ public Entry(E element, Entry<E> parent) { this.element = element; this.parent = parent; } // constructor } // class Entry } // class BinarySearchTree
In preorder Nodes visited are in the order of
code:
package edu.buffalo.cse116;
import java.util.AbstractSet;
import java.util.Iterator;
public class BinarySearchTree<E extends Comparable<E>> extends AbstractSet<E> {
protected Entry<E> root;
protected int size;
/**
* Initializes this BinarySearchTree object to be empty, to contain only
* elements of type E, to be ordered by the Comparable interface, and to
* contain no duplicate elements.
*/
public BinarySearchTree() {
root = null;
size = 0;
}
/**
* Initializes this BinarySearchTree object to contain a shallow copy of a
* specified BinarySearchTree object. The worstTime(n) is O(n), where n is the
* number of elements in the specified BinarySearchTree object.
*
* @param otherTree - the specified BinarySearchTree object that this
* BinarySearchTree object will be assigned a shallow copy of.
*/
public BinarySearchTree(BinarySearchTree<? extends E> otherTree) {
root = copy(otherTree.root, null);
size = otherTree.size;
}
/* Method to complete is here! */
public void preOrder(Entry<E> ent, StringBuilder sb) {
preorder(root)
protected Entry<E> copy(Entry<? extends E> p, Entry<E> parent) {
if (p != null) {
Entry<E> q = new Entry<E>(p.element, parent);
q.left = copy(p.left, q);
q.right = copy(p.right, q);
return q;
}
return null;
} // method copy
@SuppressWarnings("unchecked")
@Override
public boolean equals(Object obj) {
if (!(obj instanceof BinarySearchTree)) {
return false;
}
return equals(root, ((BinarySearchTree<? extends E>) obj).root);
}
public boolean equals(Entry<E> p, Entry<? extends E> q) {
if ((p == null) || (q == null)) {
return p == q;
}
if (!p.element.equals(q.element)) {
return false;
}
if (equals(p.left, q.left) && equals(p.right, q.right)) {
return true;
}
return false;
}
/**
* Returns the size of this BinarySearchTree object.
*
* @return the size of this BinarySearchTree object.
*/
@Override
public int size() {
return size;
}
/**
* Iterator method will be implemented for a future
*
* @return an iterator positioned at the smallest element in this
* BinarySearchTree object.
*/
@Override
public Iterator<E> iterator() {
throw new UnsupportedOperationException("Not implemented yet!");
}
/**
* Determines if there is at least one element in this BinarySearchTree object
* that equals a specified element. The worstTime(n) is O(n) and
* averageTime(n) is O(log n).
*
* @param obj - the element sought in this BinarySearchTree object.
* @return true - if there is an element in this BinarySearchTree object that
* equals obj; otherwise, return false.
* @throws ClassCastException - if obj cannot be compared to the elements in
* this BinarySearchTree object.
* @throws NullPointerException - if obj is null.
*/
@Override
public boolean contains(Object obj) {
return getEntry(obj) != null;
}
/**
* Ensures that this BinarySearchTree object contains a specified element. The
* worstTime(n) is O(n) and averageTime(n) is O(log n).
*
* @param element - the element whose presence is ensured in this
* BinarySearchTree object.
* @return true - if this BinarySearchTree object changed as a result of this
* method call (that is, if element was actually inserted); otherwise,
* return false.
* @throws ClassCastException - if element cannot be compared to the elements
* already in this BinarySearchTree object.
* @throws NullPointerException - if element is null.
*/
@Override
public boolean add(E element) {
if (root == null) {
if (element == null) {
throw new NullPointerException();
}
root = new Entry<E>(element, null);
size++ ;
return true;
}
else {
Entry<E> temp = root;
int comp;
while (true) {
comp = element.compareTo(temp.element);
if (comp == 0) {
return false;
}
if (comp < 0) {
if (temp.left != null) {
temp = temp.left;
} else {
temp.left = new Entry<E>(element, temp);
size++ ;
return true;
} // temp.left == null
} else if (temp.right != null) {
temp = temp.right;
} else {
temp.right = new Entry<E>(element, temp);
size++ ;
return true;
} // temp.right == null
} // while
} // root not null
} // method add
/**
* Ensures that this BinarySearchTree object does not contain a specified
* element. The worstTime(n) is O(n) and averageTime(n) is O(log n).
*
* @param obj - the object whose absence is ensured in this BinarySearchTree
* object.
* @return true - if this BinarySearchTree object changed as a result of this
* method call (that is, if obj was actually removed); otherwise,
* return false.
* @throws ClassCastException - if obj cannot be compared to the elements
* already in this BinarySearchTree object.
* @throws NullPointerException - if obj is null.
*/
@Override
public boolean remove(Object obj) {
Entry<E> e = getEntry(obj);
if (e == null) {
return false;
}
deleteEntry(e);
return true;
}
/**
* Finds the Entry object that houses a specified element, if there is such an
* Entry. The worstTime(n) is O(n), and averageTime(n) is O(log n).
*
* @param obj - the element whose Entry is sought.
* @return the Entry object that houses obj - if there is such an Entry;
* otherwise, return null.
* @throws ClassCastException - if obj is not comparable to the elements
* already in this BinarySearchTree object.
* @throws NullPointerException - if obj is null.
*/
@SuppressWarnings("unchecked")
protected Entry<E> getEntry(Object obj) {
int comp;
if (obj == null) {
throw new NullPointerException();
}
if (!(obj instanceof Comparable)) {
return null;
}
Comparable<E> compObj = (Comparable<E>) obj;
Entry<E> e = root;
while (e != null) {
comp = compObj.compareTo(e.element);
if (comp == 0) {
return e;
} else if (comp < 0) {
e = e.left;
} else {
e = e.right;
}
} // while
return null;
}
/**
* Deletes the element in a specified Entry object from this BinarySearchTree.
*
* @param p - the Entry object whose element is to be deleted from this
* BinarySearchTree object.
* @return the Entry object that was actually deleted from this
* BinarySearchTree object.
*/
protected Entry<E> deleteEntry(Entry<E> p) {
size-- ;
// If p has two children, replace p's element with p's successor's
// element, then make p reference that successor.
if ((p.left != null) && (p.right != null)) {
Entry<E> s = successor(p);
p.element = s.element;
p = s;
} // p had two children
// At this point, p has either no children or one child.
Entry<E> replacement;
if (p.left != null) {
replacement = p.left;
} else {
replacement = p.right;
}
// If p has at least one child, link replacement to p.parent.
if (replacement != null) {
replacement.parent = p.parent;
if (p.parent == null) {
root = replacement;
} else if (p == p.parent.left) {
p.parent.left = replacement;
} else {
p.parent.right = replacement;
}
} // p has at least one child
else if (p.parent == null) {
root = null;
} else {
if (p == p.parent.left) {
p.parent.left = null;
} else {
p.parent.right = null;
}
} // p has a parent but no children
return p;
} // method deleteEntry
/**
* Finds the successor of a specified Entry object in this BinarySearchTree.
* The worstTime(n) is O(n) and averageTime(n) is constant.
*
* @param e - the Entry object whose successor is to be found.
* @return the successor of e, if e has a successor; otherwise, return null.
*/
protected Entry<E> successor(Entry<E> e) {
if (e == null) {
return null;
} else if (e.right != null) {
// successor is leftmost Entry in right subtree of e
Entry<E> p = e.right;
while (p.left != null) {
p = p.left;
}
return p;
} // e has a right child
else {
// go up the tree to the left as far as possible, then go up
// to the right.
Entry<E> p = e.parent;
Entry<E> ch = e;
while ((p != null) && (ch == p.right)) {
ch = p;
p = p.parent;
} // while
return p;
} // e has no right child
} // method successor
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
preOrder(root, sb);
return sb.toString();
}
protected static class Entry<E> {
protected E element;
protected Entry<E> left = null, right = null, parent;
/**
* Initializes this Entry object. This default constructor is defined for
* the sake of subclasses of the BinarySearchTree class.
*/
public Entry() {}
/**
* Initializes this Entry object from element and parent.
*/
public Entry(E element, Entry<E> parent) {
this.element = element;
this.parent = parent;
} // constructor
} // class Entry
} // class BinarySearchTree
public class Preorder_Recursive_BST
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
BinarySearchTree sb = new BinarySearchTree();
System.out.println("Enter the first 10 elements of the tree\n");
int N = 10;
for (int i = 0; i < N; i++)
sb.append(scan.nextInt());
System.out.print("\nPre order : ");
sb.preorder();
scan.close();
}
}
Output:
Enter the first 10 elements of the tree
12 10 11 03 15 19 02 01 04 70
Pre order : 12 10 3 2 1 4 11 15 19 70
For the code below complete the preOrder() method so that it performs a preOrder traversal of...
Since we do not want to have to rewrite this code when the element type changes, this classes uses a Comparator to assist in ordering the elements. You will need to complete the siftUpComparator() and siftDownComparator() methods in the LinkedHeap Class. siftUp §Added element may violate heap-order property §siftUp() restores order starting at added node §Processing will continue working up the tree until: úFinds properly ordered node & parent úReaches the root (reaches node without parent) siftDown §Restores heap’s order...
Add a non-recursive inorder() method to class LinkedBinaryTree<E> to traverse binary tree. Test inorder() method. Implementation in Java #########LinkedBinary Tree class######### public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> { //---------------- nested Node class ---------------- /** Nested static class for a binary tree node. */ protected static class Node<E> implements Position<E> { private E element; // an element stored at this node private Node<E> parent; // a reference to the parent node (if any) private Node<E> left; // a reference to the left...
write a new test program called RemoveDuplicates.java. The program reads text input from keyboard or a text file and adds the words to a BST. The program then traverses the BST and prints out the words in order (based on ASCII/UNICODE order) on the screen (or to output text file). Note that you may need to make some changes to BST.java. Sample test: ----jGRASP exec: java -ea removeDuplicates Original Text: a B 2 n w C q K l 0...
Java help! Please help complete the min method below in bold. import java.util.Arrays; import java.util.ArrayList; import java.util.Collections; import java.util.Iterator; import java.util.List; /** * Provides an implementation of a binary search tree * with no balance constraints, implemented with linked nodes. * * * */ public class Bst<T extends Comparable<T>> implements Iterable<T> { ////////////////////////////////////////////////////////////////// // I M P L E M E N T T H E M I N M E T H O D B E L O W...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to completely test every method in the BST class to ensure the class meets all its requirements. You should read the Listing 25.5: TestBST.java for an idea of what your program should look like. Listing 25.4 BST.java public class BST> extends AbstractTree { protected TreeNode...
In Java Language. Modify the LinkedPostionalList class to support a method swap(p,q) that causes the underlying nodes referenced by positions p and q to be exchanged for each other. Relink the existing nodes, do not create any new nodes. ---------------------------------------------------------------------------------------------------------------------------------------------------------------------- package lists; import java.util.Iterator; import java.util.NoSuchElementException; public class LinkedPositionalList implements PositionalList { //---------------- nested Node class ---------------- /** * Node of a doubly linked list, which stores a reference to its * element and to both the previous and next...
In Java. How would this method look? LinkedBinaryTree.java import java.util.Iterator; public class LinkedBinaryTree implements BinaryTreeADT { private BinaryTreeNode root; /** * Creates an empty binary tree. */ public LinkedBinaryTree() { root = null; } /** * Creates a binary tree from an existing root. */ public LinkedBinaryTree(BinaryTreeNode root) { this.root = root; } /** * Creates a binary tree with the specified element...
Complete HeapPriorityQueue (7 points). In lecture we implemented HeapPriorityQueue using an array-based representation of a heap (a complete binary tree whose entries satisfy the heap-order property). For this problem, complete the included HeapPriorityQueue class by using the LinkedBinaryTree class to represent a heap. Hint: the most challenging part of this problem is identifying the last Position in the heap and the next available Position in the heap. It is suggested that you review the array-based heap to better understand how...
JAVA: Already completed: MyList.java, MyAbstractList.java, MyArrayList.java, MyLinkedLink.java, MyStack.java, MyQueue.java. Need to complete: ReversePoem.java. This program has you display a pessimistic poem from a list of phrases. Next, this program has you reverse the phrases to find another more optimistic poem. Use the following algorithm. 1. You are given a list of phrases each ending with a pound sign: ‘#’. 2. Create a single String object from this list. 3. Then, split the String of phrases into an array of phrases...
Question - modify the code below so that for a node, the value of every node of its right subtree is less the node, and the value of each node of its left subtree is greater than the node. - create such a binary tree in the Main method, and call the following method: InOrder(Node theRoot), PreOrder(Node theRoot), PostOrder(Node theRoot), FindMin(), FindMax(), Find(int key) using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;...