write these methods in the BST class: protected T getMax(BSTNode<T> p ) : return
ID: 3919972 • Letter: W
Question
write these methods in the BST class:
protected T getMax(BSTNode<T> p ) :
return the maximum key in the tree referenced by p
protected void printNonLeaves(BSTNode<T> p)
that prints all non-leaves nodes in the tree referenced by p
note that :
in both cases you need to have a public overloaded version of the methods that call the protected version with root as the
intial for p
BST class :
/************************ BST.java **************************
* generic binary search tree
*/
import java.util.*;
public class BST<T extends Comparable<T>> implements Iterable<T> {
protected BSTNode<T> root = null;
public BST() {
}
public BST(BSTNode<T> p) {
root = p;
}
public void clear() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
protected void visit(BSTNode<T> p) {
System.out.print(p.key + " ");
}
public T search(T el) {
return search(el, root);
}
//recursive search
protected T search(T el, BSTNode<T> p) {
if (p == null)
return null;
else if(el.compareTo(p.key ) < 0)
return search(el, p.left);
else if(el.compareTo(p.key) > 0)
return search(el, p.right );
else
return p.key;
}
/*
//Iterative search
public T search(T el) {
BSTNode<T> p = root;
while (p != null) {
if (el.equals(p.key))
return p.key;
else if (el.compareTo(p.key) < 0)
p = p.left;
else p = p.right;
}
return null;
}
*/
public boolean isInTree(T el) {
return search(el) != null;
}
public void breadthFirst() {
BSTNode<T> p = root;
LLQueue<BSTNode<T>> queue = new LLQueue<BSTNode<T>>();
if (p != null) {
queue.enqueue(p);
while (!queue.isEmpty()) {
p = queue.dequeue();
visit(p);
if (p.left != null)
queue.enqueue(p.left);
if (p.right != null)
queue.enqueue(p.right);
}
}
}
public void preorder() {
preorder(root);
}
protected void preorder(BSTNode<T> p) {
if (p != null) {
visit(p);
preorder(p.left);
preorder(p.right);
}
}
public void inorder() {
inorder(root);
}
protected void inorder(BSTNode<T> p) {
if (p != null) {
inorder(p.left);
visit(p);
inorder(p.right);
}
}
public void postorder() {
postorder(root);
}
protected void postorder(BSTNode<T> p) {
if (p != null) {
postorder(p.left);
postorder(p.right);
visit(p);
}
}
public void insert(T el) {
root = insert(el, root);
}
protected BSTNode<T> insert(T el, BSTNode<T> p) {
if( p == null )
p = new BSTNode<T>(el);
else if(el.compareTo(p.key ) < 0 )
p.left = insert(el, p.left );
else if( el.compareTo(p.key ) > 0 )
p.right = insert(el, p.right );
return p;
}
/* iterative version
public void insert(T el) {
BSTNode<T> p = root, prev = null;
while (p != null) { // find a place for inserting new node;
prev = p;
if (el.compareTo(p.key) < 0)
p = p.left;
else p = p.right;
}
if (root == null) // tree is empty;
root = new BSTNode<T>(el);
else if (el.compareTo(prev.key) < 0)
prev.left = new BSTNode<T>(el);
else prev.right = new BSTNode<T>(el);
}
*/
public void delete (T el) {
root = delete (el, root);
}
//recursive delete by copying
protected BSTNode<T> delete(T el, BSTNode<T> p) {
if (p == null)
return null;
else if (el.compareTo(p.key) < 0) //target is less than p.key
p.left = delete(el, p.left); // delete from left
else if (el.compareTo(p.key) > 0) //target is greater than p.key
p.right = delete(el, p.right);
else { //p.key is the key to be deleted
if (p.left == null || p.right == null) {//if there is one or no child
if (p.left == null) //if no left child
p = p.right;
else //if no right child or no child at all
p = p.left;
}
else { //if p has two children
BSTNode<T> tmp = getMinNode(p.right);//get the successor of the p.key
p.key = tmp.key; //replace p.key with its successor
p.right = delete(tmp.key, p.right); //delete the successor from the right subtree.
}
}
return p;
}
//given a non-empty tree, retuns the node with the minimum key.
private BSTNode<T> getMinNode(BSTNode<T> p) {
BSTNode<T> tmp = p;
while (tmp.left != null)
tmp = tmp.left;
return tmp;
}
//Iterative delete by copying
/*
public void deleteByCopying(T el) {
BSTNode<T> node, p = root, prev = null;
while (p != null && !p.key.equals(el)) { // find the node p
prev = p; // with element el;
if (el.compareTo(p.key) < 0)
p = p.left;
else p = p.right;
}
node = p;
if (p != null && p.key.equals(el)) {
if (node.right == null) // node has no right child;
node = node.left;
else if (node.left == null) // no left child for node;
node = node.right;
else {
BSTNode<T> tmp = node.left; // node has both children;
BSTNode<T> previous = node; // 1.
while (tmp.right != null) { // 2. find the rightmost
previous = tmp; // position in the
tmp = tmp.right; // left subtree of node;
}
node.key = tmp.key; // 3. overwrite the reference
// to the element being deleted;
if (previous == node) // if node's left child's
previous.left = tmp.left; // right subtree is null;
else previous.right = tmp.left; // 4.
}
if (p == root)
root = node;
else if (prev.left == p)
prev.left = node;
else prev.right = node;
}
else if (root != null)
System.out.println("el " + el + " is not in the tree");
else System.out.println("the tree is empty");
}
*/
public Iterator<T> iterator() {
return new BSTIterator();
}
private class BSTIterator implements Iterator<T> {
BSTNode<T> p = root;
LLQueue<BSTNode<T>> queue;
public BSTIterator() {
queue = new LLQueue<BSTNode<T>>();
queue.enqueue(p);
}
public boolean hasNext() {
return !queue.isEmpty();
}
public T next() {
p = queue.dequeue();
if (p.left != null)
queue.enqueue(p.left);
if (p.right != null)
queue.enqueue(p.right);
return p.key;
}
public void remove() {
// not implemented
}
}
//Generic BSTNode class;
private class BSTNode<T extends Comparable<T>> {
protected T key;
protected BSTNode<T> left, right;
public BSTNode() {
left = right = null;
}
public BSTNode(T el) {
this(el,null,null);
}
public BSTNode(T el, BSTNode<T> lt, BSTNode<T> rt) {
key = el; left = lt; right = rt;
}
}
}
Explanation / Answer
//BST class :
/************************ BST.java **************************
* generic binary search tree
*/
import java.util.*;
public class BST<T extends Comparable<T>> implements Iterable<T> {
protected BSTNode<T> root = null;
public BST() {
}
public BST(BSTNode<T> p) {
root = p;
}
public void clear() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
protected void visit(BSTNode<T> p) {
System.out.print(p.key + " ");
}
public T search(T el) {
return search(el, root);
}
//recursive search
protected T search(T el, BSTNode<T> p) {
if (p == null)
return null;
else if(el.compareTo(p.key ) < 0)
return search(el, p.left);
else if(el.compareTo(p.key) > 0)
return search(el, p.right );
else
return p.key;
}
protected T getMax(BSTNode<T> p ) {
if(null == root) {
return null;
}
if(root.right == null) {
return root.key;
}
return getMax(root.right);
}
public T getMax() {
return getMax(root);
}
protected void printNonLeaves(BSTNode<T> p) {
if (root == null) {
return;
}
if (!(root.left == null && root.right == null)) {
System.out.print(root.key + " ");
}
printNonLeaves(root.left);
printNonLeaves(root.right);
}
public void printNonLeaves() {
printNonLeaves(root);
}
/*
//Iterative search
public T search(T el) {
BSTNode<T> p = root;
while (p != null) {
if (el.equals(p.key))
return p.key;
else if (el.compareTo(p.key) < 0)
p = p.left;
else p = p.right;
}
return null;
}
*/
public boolean isInTree(T el) {
return search(el) != null;
}
public void breadthFirst() {
BSTNode<T> p = root;
LLQueue<BSTNode<T>> queue = new LLQueue<BSTNode<T>>();
if (p != null) {
queue.enqueue(p);
while (!queue.isEmpty()) {
p = queue.dequeue();
visit(p);
if (p.left != null)
queue.enqueue(p.left);
if (p.right != null)
queue.enqueue(p.right);
}
}
}
public void preorder() {
preorder(root);
}
protected void preorder(BSTNode<T> p) {
if (p != null) {
visit(p);
preorder(p.left);
preorder(p.right);
}
}
public void inorder() {
inorder(root);
}
protected void inorder(BSTNode<T> p) {
if (p != null) {
inorder(p.left);
visit(p);
inorder(p.right);
}
}
public void postorder() {
postorder(root);
}
protected void postorder(BSTNode<T> p) {
if (p != null) {
postorder(p.left);
postorder(p.right);
visit(p);
}
}
public void insert(T el) {
root = insert(el, root);
}
protected BSTNode<T> insert(T el, BSTNode<T> p) {
if( p == null )
p = new BSTNode<T>(el);
else if(el.compareTo(p.key ) < 0 )
p.left = insert(el, p.left );
else if( el.compareTo(p.key ) > 0 )
p.right = insert(el, p.right );
return p;
}
/* iterative version
public void insert(T el) {
BSTNode<T> p = root, prev = null;
while (p != null) { // find a place for inserting new node;
prev = p;
if (el.compareTo(p.key) < 0)
p = p.left;
else p = p.right;
}
if (root == null) // tree is empty;
root = new BSTNode<T>(el);
else if (el.compareTo(prev.key) < 0)
prev.left = new BSTNode<T>(el);
else prev.right = new BSTNode<T>(el);
}
*/
public void delete (T el) {
root = delete (el, root);
}
//recursive delete by copying
protected BSTNode<T> delete(T el, BSTNode<T> p) {
if (p == null)
return null;
else if (el.compareTo(p.key) < 0) //target is less than p.key
p.left = delete(el, p.left); // delete from left
else if (el.compareTo(p.key) > 0) //target is greater than p.key
p.right = delete(el, p.right);
else { //p.key is the key to be deleted
if (p.left == null || p.right == null) {//if there is one or no child
if (p.left == null) //if no left child
p = p.right;
else //if no right child or no child at all
p = p.left;
}
else { //if p has two children
BSTNode<T> tmp = getMinNode(p.right);//get the successor of the p.key
p.key = tmp.key; //replace p.key with its successor
p.right = delete(tmp.key, p.right); //delete the successor from the right subtree.
}
}
return p;
}
//given a non-empty tree, retuns the node with the minimum key.
private BSTNode<T> getMinNode(BSTNode<T> p) {
BSTNode<T> tmp = p;
while (tmp.left != null)
tmp = tmp.left;
return tmp;
}
//Iterative delete by copying
/*
public void deleteByCopying(T el) {
BSTNode<T> node, p = root, prev = null;
while (p != null && !p.key.equals(el)) { // find the node p
prev = p; // with element el;
if (el.compareTo(p.key) < 0)
p = p.left;
else p = p.right;
}
node = p;
if (p != null && p.key.equals(el)) {
if (node.right == null) // node has no right child;
node = node.left;
else if (node.left == null) // no left child for node;
node = node.right;
else {
BSTNode<T> tmp = node.left; // node has both children;
BSTNode<T> previous = node; // 1.
while (tmp.right != null) { // 2. find the rightmost
previous = tmp; // position in the
tmp = tmp.right; // left subtree of node;
}
node.key = tmp.key; // 3. overwrite the reference
// to the element being deleted;
if (previous == node) // if node's left child's
previous.left = tmp.left; // right subtree is null;
else previous.right = tmp.left; // 4.
}
if (p == root)
root = node;
else if (prev.left == p)
prev.left = node;
else prev.right = node;
}
else if (root != null)
System.out.println("el " + el + " is not in the tree");
else System.out.println("the tree is empty");
}
*/
public Iterator<T> iterator() {
return new BSTIterator();
}
private class BSTIterator implements Iterator<T> {
BSTNode<T> p = root;
LLQueue<BSTNode<T>> queue;
public BSTIterator() {
queue = new LLQueue<BSTNode<T>>();
queue.enqueue(p);
}
public boolean hasNext() {
return !queue.isEmpty();
}
public T next() {
p = queue.dequeue();
if (p.left != null)
queue.enqueue(p.left);
if (p.right != null)
queue.enqueue(p.right);
return p.key;
}
public void remove() {
// not implemented
}
}
//Generic BSTNode class;
private class BSTNode<T extends Comparable<T>> {
protected T key;
protected BSTNode<T> left, right;
public BSTNode() {
left = right = null;
}
public BSTNode(T el) {
this(el,null,null);
}
public BSTNode(T el, BSTNode<T> lt, BSTNode<T> rt) {
key = el; left = lt; right = rt;
}
}
}
=========
Thanks
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.