For the code below complete the preOrder() method so that it performs a preOrder traversal of...
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
Homework Answers
In preorder Nodes visited are in the order of
- visit Root node
- visit Left node
- visit Right node
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
Add Answer to:
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,...
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...
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 word...
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 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 com...
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...
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 {...
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...
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...
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...
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;...
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...
Most questions answered within 3 hours.
-
Hypothesis Testing, P-values: For the given
alternate hypothesis (H1) and test statistic
(z), determine the P-value...
asked 1 hour ago -
#22 Suppose cars pass an intersection at a rate of 120 per hour.
What is the...
asked 4 hours ago -
should software developers who work on critical applications whose
failure could result in loss of human...
asked 2 hours ago -
6. You have a parallel-plate capacitor made of two circular
metal plates. The radius of each...
asked 2 hours ago -
A 1 230.0 kg car traveling initially with a speed of 25.000 m/s
in an easterly...
asked 3 hours ago -
1-how inefficient management affects patient care in a hospital?
2-Thinking as a COO how would you...
asked 3 hours ago -
for project management course
An indicator of project success within an organization is the
strength of...
asked 4 hours ago -
How did immigration affect the culture of the United States?
Explain in detail and give specific...
asked 4 hours ago -
A dolphin in an aquatic show jumps straight up out of the water
at a velocity...
asked 6 hours ago -
x
P(x)
0
0.25
1
0.2
2
0.15
3
0.4
Find the standard deviation of this...
asked 7 hours ago -
An economist claims that he has found evidence to support the
assumption that the investment expenditure...
asked 7 hours ago -
Question 10 (1 point)
Suppose that a researcher studying the weight of female college
athletes wants...
asked 9 hours ago