Write the body of the following static method, which returns true if and only if
ID: 3858857 • Letter: W
Question
Write the body of the following static method, which returns true if and only if the given BinaryTree, t, satisfies the heap ordering property according to the <= relation. (Note that this says nothing about the shape of the tree, i.e., it should work whether or not t is a complete binary tree, and should not check whether it is.) [JAVA]
/**
* Checks if the given {@code BinaryTree} satisfies the heap
* ordering property according to the <= relation.
*
* @param t
* the binary tree
* @return true if the given tree satisfies the heap ordering property;
* false otherwise
* @ensures
* satisfiesHeapOrdering = [t satisfies the heap ordering property]
*
*/
private static boolean satisfiesHeapOrdering(BinaryTree t) {...}
Explanation / Answer
As you have not provided the class for BinaryTree, i have created mine and provided the code according to that:
public class BinaryTree {
public int value;
private BinaryTree leftChild;
private BinaryTree rightChild;
/**
* Constructor for BinaryTree
*/
public BinaryTree(int value, BinaryTree leftChild, BinaryTree rightChild) {
this.value = value;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
/**
* Constructor for a BinaryTree leaf node (that is, with no children).
*
* @param value
* The value to be placed in the root.
*/
public BinaryTree(int value) {
this(value, null, null);
}
/**
* Getter method for the value in this BinaryTree node.
*
* @return The value in this node.
*/
public int getValue() {
return value;
}
/**
* Getter method for left child of this BinaryTree node.
*
* @return The left child (<code>null</code> if no left child).
*/
public BinaryTree getLeftChild() {
return leftChild;
}
/**
* Getter method for right child of this BinaryTree node.
*
* @return The right child (<code>null</code> if no right child).
*/
public BinaryTree getRightChild() {
return rightChild;
}
private static boolean satisfiesHeapOrdering(BinaryTree t) {
BinaryTree left = t.getLeftChild();
BinaryTree right = t.getRightChild();
int value = t.getValue();
// if this node has no children, then it satisfies
if(left==null && right==null) {
return true;
}
// check if there is a left node, it should have more or equal value
if(left != null) {
if(left.getValue() < value)
return false;
else if(!satisfiesHeapOrdering(left)) {
// the left subtree should also satisfy the heapify property
return false;
}
}
// similar for right subtree
if(right != null) {
if(right.getValue() < value)
return false;
else if(!satisfiesHeapOrdering(right)) {
return false;
}
}
return true;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.