complete thr following methods you can use recursion using the binaryNode class
ID: 3876820 • Letter: C
Question
complete thr following methods you can use recursion using the binaryNode class
@Override
public T getMin() {
return null;
}
@Override
public T getMax() {
return null;
}
@Override
public T getNextToSmallest() {
return null;
}
@Override
public T getNextToLargest() {
return null;
}
@Override
public T getMedian() {
return null;
}
@Override
public T getIthValue(int i) {
return null;
}
@Override
public int getSortedIndex(T value) {
return 0;
}
class BinaryNode<T> {
private T data;
private BinaryNode<T> leftChild; // Reference to left child
private BinaryNode<T> rightChild; // Reference to right child
private int numNodesLeft, numNodesRight;
public BinaryNode() {
this(null); // Call next constructor
} // end default constructor
public BinaryNode(T dataPortion) {
this(dataPortion, null, null); // Call next constructor
} // end constructor
public BinaryNode(T dataPortion, BinaryNode<T> newLeftChild, BinaryNode<T> newRightChild) {
data = dataPortion;
leftChild = newLeftChild;
rightChild = newRightChild;
} // end constructor
/**
* Retrieves the data portion of this node.
*
* @return The object in the data portion of the node.
*/
public T getData() {
return data;
} // end getData
/**
* Sets the data portion of this node.
*
* @param newData
* The data object.
*/
public void setData(T newData) {
data = newData;
} // end setData
/**
* Retrieves the left child of this node.
*
* @return The node’s left child.
*/
public BinaryNode<T> getLeftChild() {
return leftChild;
} // end getLeftChild
/**
* Sets this node’s left child to a given node.
*
* @param newLeftChild
* A node that will be the left child.
*/
public void setLeftChild(BinaryNode<T> newLeftChild) {
leftChild = newLeftChild;
} // end setLeftChild
/**
* Detects whether this node has a left child.
*
* @return True if the node has a left child.
*/
public boolean hasLeftChild() {
return leftChild != null;
} // end hasLeftChild
/**
* Retrieves the right child of this node.
*
* @return The node’s right child.
*/
public BinaryNode<T> getRightChild() {
return rightChild;
} // end getRightChild
/**
* Sets this node’s right child to a given node.
*
* @param newRightChild
* A node that will be the right child.
*/
public void setRightChild(BinaryNode<T> newRightChild) {
rightChild = newRightChild;
} // end setRightChild
/**
* Detects whether this node has a right child.
*
* @return True if the node has a right child.
*/
public boolean hasRightChild() {
return rightChild != null;
} // end hasRightChild
/**
* Detects whether this node is a leaf.
*
* @return True if the node is a leaf.
*/
public boolean isLeaf() {
return (leftChild == null) && (rightChild == null);
} // end isLeaf
/**
* Counts the nodes in the subtree rooted at this node.
*
* @return The number of nodes in the subtree rooted at this node.
*/
public int getNumberOfNodes() {
int leftNumber = 0;
int rightNumber = 0;
if (leftChild != null)
leftNumber = leftChild.getNumberOfNodes();
if (rightChild != null)
rightNumber = rightChild.getNumberOfNodes();
return 1 + leftNumber + rightNumber;
} // end getNumberOfNodes
/**
* Computes the height of the subtree rooted at this node.
*
* @return The height of the subtree rooted at this node.
*/
public int getHeight() {
return getHeight(this); // Call private getHeight
} // end getHeight
private int getHeight(BinaryNode<T> node) {
int height = 0;
if (node != null)
height = 1 + Math.max(getHeight(node.getLeftChild()), getHeight(node.getRightChild()));
return height;
} // end getHeight
/**
* Copies the subtree rooted at this node.
*
* @return The root of a copy of the subtree rooted at this node.
*/
public BinaryNode<T> copy() {
BinaryNode<T> newRoot = new BinaryNode<>(data);
if (leftChild != null)
newRoot.setLeftChild(leftChild.copy());
if (rightChild != null)
newRoot.setRightChild(rightChild.copy());
return newRoot;
} // end copy
} // end BinaryNode
Explanation / Answer
BinaryNode.java:
import java.util.ArrayList;
import java.util.Collections;
public class BinaryNode<T extends Comparable<T>> {
private T data;
private BinaryNode<T> leftChild; // Reference to left child
private BinaryNode<T> rightChild; // Reference to right child
private int numNodesLeft, numNodesRight;
public BinaryNode() {
this(null); // Call next constructor
} // end default constructor
public BinaryNode(T dataPortion) {
this(dataPortion, null, null); // Call next constructor
} // end constructor
public BinaryNode(T dataPortion, BinaryNode<T> newLeftChild, BinaryNode<T> newRightChild) {
data = dataPortion;
leftChild = newLeftChild;
rightChild = newRightChild;
} // end constructor
/**
* Retrieves the data portion of this node.
*
* @return The object in the data portion of the node.
*/
public T getData() {
return data;
} // end getData
/**
* Sets the data portion of this node.
*
* @param newData
* The data object.
*/
public void setData(T newData) {
data = newData;
} // end setData
/**
* Retrieves the left child of this node.
*
* @return The node’s left child.
*/
public BinaryNode<T> getLeftChild() {
return leftChild;
} // end getLeftChild
/**
* Sets this node’s left child to a given node.
*
* @param newLeftChild
* A node that will be the left child.
*/
public void setLeftChild(BinaryNode<T> newLeftChild) {
leftChild = newLeftChild;
} // end setLeftChild
/**
* Detects whether this node has a left child.
*
* @return True if the node has a left child.
*/
public boolean hasLeftChild() {
return leftChild != null;
} // end hasLeftChild
/**
* Retrieves the right child of this node.
*
* @return The node’s right child.
*/
public BinaryNode<T> getRightChild() {
return rightChild;
} // end getRightChild
/**
* Sets this node’s right child to a given node.
*
* @param newRightChild
* A node that will be the right child.
*/
public void setRightChild(BinaryNode<T> newRightChild) {
rightChild = newRightChild;
} // end setRightChild
/**
* Detects whether this node has a right child.
*
* @return True if the node has a right child.
*/
public boolean hasRightChild() {
return rightChild != null;
} // end hasRightChild
/**
* Detects whether this node is a leaf.
*
* @return True if the node is a leaf.
*/
public boolean isLeaf() {
return (leftChild == null) && (rightChild == null);
} // end isLeaf
/**
* Counts the nodes in the subtree rooted at this node.
*
* @return The number of nodes in the subtree rooted at this node.
*/
public int getNumberOfNodes() {
int leftNumber = 0;
int rightNumber = 0;
if (leftChild != null)
leftNumber = leftChild.getNumberOfNodes();
if (rightChild != null)
rightNumber = rightChild.getNumberOfNodes();
return 1 + leftNumber + rightNumber;
} // end getNumberOfNodes
/**
* Computes the height of the subtree rooted at this node.
*
* @return The height of the subtree rooted at this node.
*/
public int getHeight() {
return getHeight(this); // Call private getHeight
} // end getHeight
private int getHeight(BinaryNode<T> node) {
int height = 0;
if (node != null)
height = 1 + Math.max(getHeight(node.getLeftChild()), getHeight(node.getRightChild()));
return height;
} // end getHeight
/**
* Copies the subtree rooted at this node.
*
* @return The root of a copy of the subtree rooted at this node.
*/
public BinaryNode<T> copy() {
BinaryNode<T> newRoot = new BinaryNode<>(data);
if (leftChild != null)
newRoot.setLeftChild(leftChild.copy());
if (rightChild != null)
newRoot.setRightChild(rightChild.copy());
return newRoot;
} // end copy
public T getMin() {
if(isLeaf()) {
return data;
}
T leftMin=null, rightMin=null;
if(hasLeftChild()) {
leftMin = leftChild.getMin();
}
if(hasRightChild()) {
rightMin = rightChild.getMin();
}
// check which has lesser value and compare to root node
if(leftMin != null && rightMin != null) {
if(leftMin.compareTo(rightMin) > 0) {
return rightMin.compareTo(data) < 0 ? rightMin : data;
} else {
return leftMin.compareTo(data) < 0 ? leftMin : data;
}
} else {
return (leftMin != null ? leftMin.compareTo(data) < 0 ? leftMin : data : rightMin.compareTo(data) < 0 ? rightMin : data);
}
}
public T getMax() {
if(isLeaf()) {
return data;
}
T leftMax=null, rightMax=null;
if(hasLeftChild()) {
leftMax = leftChild.getMax();
}
if(hasRightChild()) {
rightMax = rightChild.getMax();
}
if(leftMax != null && rightMax != null) {
if(leftMax.compareTo(rightMax) > 0) {
return rightMax.compareTo(data) > 0 ? rightMax : data;
} else {
return leftMax.compareTo(data) > 0 ? leftMax : data;
}
} else {
return (leftMax != null ? leftMax.compareTo(data) > 0 ? leftMax : data : rightMax.compareTo(data) > 0 ? rightMax : data);
}
}
public ArrayList<T> getTreeData() {
ArrayList<BinaryNode<T>> listToProcess = new ArrayList<>();
listToProcess.add(this);
ArrayList<T> treeData = new ArrayList<>();
while(!listToProcess.isEmpty()) {
BinaryNode<T> node = listToProcess.remove(0);
treeData.add(node.data);
if(node.hasLeftChild()) {
listToProcess.add(node.leftChild);
}
if(node.hasRightChild()) {
listToProcess.add(node.rightChild);
}
}
return treeData;
}
public T getNextToSmallest() {
ArrayList<T> treeData = getTreeData();
Collections.sort(treeData);
if(treeData.size() > 1) {
return treeData.get(1);
} else {
return null;
}
}
public T getNextToLargest() {
ArrayList<T> treeData = getTreeData();
Collections.sort(treeData);
if(treeData.size() > 1) {
return treeData.get(treeData.size()-2);
} else {
return null;
}
}
public T getMedian() {
ArrayList<T> treeData = getTreeData();
Collections.sort(treeData);
if(treeData.size() > 0) {
return treeData.get(treeData.size()/2);
} else {
return null;
}
}
public T getIthValue(int i) {
ArrayList<T> treeData = getTreeData();
Collections.sort(treeData);
if(treeData.size() > i) {
return treeData.get(i);
} else {
return null;
}
}
public int getSortedIndex(T value) {
ArrayList<T> treeData = getTreeData();
Collections.sort(treeData);
return treeData.indexOf(value);
}
} // end BinaryNode
========================
As you have not provided the main class, i can not give you a screenshot of the runnning program.. still if you have any issue, please do ask in comments. Thanks! If you find it helpful, please upvote
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.