Homework SourseFor the code below complete the preOrder method so that it p
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:
Solution
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
