The goal of the homework is to implement a priority queue as a BST adapter. Belo

Question

The goal of the homework is to implement a priority queue as a BST adapter.

Below are the package that has been imported above, dont change them just give me the code required for insert and removemin where it says TODO and dnt change anything please

-------------------------------------------------------

-----------------------------------------------------------

---------------------------------

....................................................................................................................................

-----------------------------------------

package class13;

import java.util.ArrayList;
import class12.Tree;

public class BinaryTree extends Tree {
public BinaryTree() {
super();
}

public void addRoot(T x) throws Exception {
if (root != null) throw new Exception("The tree is not empty");
root = new BNode(x, null, null, null);
size++;
}

public void addLeft(BNode n, T x) throws Exception {
if (n.getLeft() != null) throw new Exception("Already used");
n.setLeft(new BNode(x, n, null, null));
size++;
}

public void addRight(BNode n, T x) throws Exception {
if (n.getRight() != null) throw new Exception("Already used");
n.setRight(new BNode(x, n, null, null));
size++;
}

// returns the parent of the removed node
public BNode removeNode(BNode n) {
if (isLeaf(n)) { // base case
BNode p = (BNode) parent(n);
if (p == null) root = null;
else p.removeChild(n);
size--;
return p;
}
if (n.getLeft() != null) {
BNode m = rightmostLeftDescendant(n);
n.setData(m.getData());
return removeNode(m); // recursively remove rightmost left descendant
}
// otherwise n does have a right child
BNode m = leftmostRightDescendant(n);
n.setData(m.getData());
return removeNode(m);
}

public BNode leftmostRightDescendant(BNode n) {
BNode m = n.getRight();
while (m.getLeft() != null) m = m.getLeft();
return m;
}

public BNode rightmostLeftDescendant(BNode n) {
BNode m = n.getLeft();
while (m.getRight() != null) m = m.getRight();
return m;
}

public ArrayList> inOrder() {
ArrayList> answer = new ArrayList>();
inOrder((BNode) root(), answer);
return answer;
}

public void inOrder(BNode n, ArrayList> v) {
if (n == null) return;
inOrder(n.getLeft(), v);
v.add(n);
inOrder(n.getRight(), v);
}

public ArrayList> flatOrder() {
return inOrder();
}
}

-------------------------------

package class22;

public interface BSTree> {

   public void remove(K x);

   public void insert(K x) throws Exception;

   public boolean find(K x);

}

-------------------------------------------------------------------

package class12;

import java.util.ArrayList;
import java.util.Iterator;

public class Tree<T> {
protected Node<T> root;
protected int size;

public Tree() {
root = null;
size = 0;
}

public Node<T> root() {
return root;
}

public Node<T> parent(Node<T> v) {
return v.getParent();
}

public Iterator<? extends Node<T>> children(Node<T> v) {
return v.children();
}

public boolean isRoot(Node<T> v) {
return v == root;
}

public boolean isInternal(Node<T> v) {
return children(v).hasNext();
}

public boolean isLeaf(Node<T> v) {
return !isInternal(v);
}

public int size() {
return size;
}

public boolean empty() {
return size == 0;
}

public void replace(Node<T> v, T t) {
v.setData(t);
}

public int depth(Node<T> v) {
if (isRoot(v))
return 0;
return 1 + depth(parent(v));
}

public int height(Node<T> v) {
if (isLeaf(v))
return 0;
int maxChild = 0;
Iterator<? extends Node<T>> c = children(v);
while (c.hasNext()) {
int hc = height((Node<T>) c.next());
if (hc > maxChild)
maxChild = hc;
}
return maxChild + 1;
}

public int height() {
if (root == null)
return -1;
return height(root);
}

public ArrayList<Node<T>> preOrder() {
ArrayList<Node<T>> answer = new ArrayList<>();
preOrder(root(), answer);
return answer;
}

public void preOrder(Node<T> n, ArrayList<Node<T>> v) {
if (n == null)
return;
v.add(n);
Iterator<? extends Node<T>> x = children(n);
while (x.hasNext()) {
Node<T> m = x.next();
preOrder(m, v);
}
}

public ArrayList<Node<T>> postOrder() {
ArrayList<Node<T>> answer = new ArrayList<Node<T>>();
postOrder(root(), answer);
return answer;
}

public void postOrder(Node<T> n, ArrayList<Node<T>> v) {
if (n == null)
return;
Iterator<? extends Node<T>> x = children(n);
while (x.hasNext()) {
Node<T> m = x.next();
postOrder(m, v);
}
v.add(n);
}

public ArrayList<Node<T>> levelOrder() {
ArrayList<Node<T>> waiting = new ArrayList<>();
waiting.add(null);
if (root() == null)
return waiting;
waiting.add(root());
int done = 0;
while (done < waiting.size()) {
Node<T> oldNode = waiting.get(done++);
if (oldNode == null) {
if (done < waiting.size())
waiting.add(null);
continue;
}
Iterator<? extends Node<T>> c = children(oldNode);
while (c.hasNext())
waiting.add(c.next());
}
return waiting;
}

public ArrayList<? extends Node<T>> flatOrder() {
return preOrder();
}

public String toString() {
return treePrint(null);
}

public String treePrint(Node<T> cursor) {
String answer = " ";
Iterator<Node<T>> lev = levelOrder().iterator();
Iterator<? extends Node<T>> flat = flatOrder().iterator();
lev.next(); // skip first new line
while (lev.hasNext()) {
Node<T> o = lev.next();
if (o == null) {
answer += " ";
flat = flatOrder().iterator();
} else
while (true) {
boolean atCursor = false;
Node<T> n = flat.next();
if (n == cursor)
atCursor = true;
String s = n.getData().toString();
if (atCursor)
s = "* " + s + " *";
if (n == o) {
answer += s;
break;
} else
for (int i = 0; i < s.length(); i++)
answer += ' ';
}
}
return answer;
}
}

Explanation / Answer

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Random;

class BSTPQ<K> extends BST implements PriorityQueue {

public void insert(K x) throws Exception {
BNode n = findNode(x);
if (n == null) {
addRoot(x);
} else if ((n.getData()).compareTo(x) > 0) {
addLeft(n, x);
} else if ((n.getData()).compareTo(x) < 0) {
addRight(n, x);
}
}

public K removeMin() throws Exception {
BNode nn = null;
int min = 9999;
return removeMinSub(nn, min);
}
public K removeMinSub(BNode nn, int min) throws Exception {
if (nn.getData().compareTo(min) < 0) {
nn = nn.getLeft();
} else {
nn = nn.getRight();
}
return removeMinSub(nn, min);
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.