The concept of \"checking\" is very important in computer science. For instance,
ID: 3578139 • Letter: T
Question
The concept of "checking" is very important in computer science. For instance, instead of sorting, we might just want to check that an array is sorted. Generally, checking for a property is simpler than computing that property. In the following, you may assume any primitive that we have discussed in lectures or homeworks. Write the method boolean isHeap(int[] A); to check that A is actually a heap. Write the Java method boolean isBST(BinNode u); to check that the binary tree rooted at u represents a BST. Assume that u.key is an int. Recall that you may use any known BST methods to simplify this task. Write the Java Method boolean sameShape(BinNode u, BinNode v); to check if the two binary trees have the same shape. Note that we are not interested in whether they are BST's or not.Explanation / Answer
a)
public static boolean isHeap(int[] A) {
if (A = null)
return false;
return isHeapTree(A, 0);
}
private static boolean isHeapTree(int[] A, int i) {
if (i = A.length - 1)
return true;
// check if a parent's value is larger or equal to both of
// its left child and right child
else if (A[i] >= A[2i + 1] && A[i] >= A[2i + 2])
return (isHeapTree(A, 2i + 1) && isHeapTree(A, 2i + 2));
else
return false;
}
b)
public boolean isBST(BinNode u)
{
int[] bad ={1, -1};
int[] pair = new int[2];
if (u.left != null)
{
pair = isBST(u.left);
if (pair[1]>u.key)
return bad;
}
elsepair[0]=u.key;
int[] tmppair;
if (u.right != null)
{
tmppair = isBST(u.left);
if (tmppair[0]<u.key)
return bad;
}
elsepair[1]=tmppair[1];
return pair;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.