/ Complete the four exercises below. For each \"EXERCISE\" comment, add code imm
ID: 3886854 • Letter: #
Question
/ Complete the four exercises below. For each "EXERCISE" comment, add code immediately below the comment.
//You MUST NOT edit the IDEA/SBT configuration/tests. Altering it in your submission will result in 0 points for this assignment.
//
// This class represents operations on simple Binary Search Trees (BST) with integer keys and no values, i.e., a set of integers.
//
// DO NOT change the name or type of any function (the first line of the function)
// All of the methods in this class are static (and mostly recursive).
// These methods could naturally appear inside Node.java also.
//
// This code is not representative of the object-oriented style of programming, but is concise and allows null to be used to represent leaf nodes.
//////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 1: A tree is size-perfect if for every node, size of left == size of
right.
public boolean isPerfectlyBalancedS () {
// TODO: Complete this method.
return false;
}
//////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 2: A tree is height-perfect if for every node, height of left == height
of right.
public boolean isPerfectlyBalancedH () {
// TODO: Complete this method.
return false;
}
//////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 3: A tree is semi-perfect if every node is semi-perfect.
// A node with 0 children is semi-perfect.
// A node with 1 child is NOT semi-perfect.
// A node with 2 children is semi-perfect if (size-of-larger-child <= size-of-smaller-child * 3)
public boolean isSemiBalanced (){
// TODO: Complete this method.
return false;
}
//////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 4:
// tree is odd-perfect if for every node, #odd descendant on left == # odd descendants on right
// A node is odd if it has an odd key
// hint: in the helper, return -1 if the tree is not odd-perfect, otherwise return the odd size
public boolean isOddBalanced() {
// TODO: Complete this method.
return false;
}
Explanation / Answer
The following is the required methods.
/////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 1: A tree is size-perfect if for every node, size of left == size ofright.
public boolean isPerfectlyBalancedS () {
Node t = null;
if(size(t.left)==size(t.right))
return true;
// TODO: Complete this method.
return false;
}
//////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 2: A tree is height-perfect if for every node, height of left == heightof right.
public boolean isPerfectlyBalancedH () {
Node t = null;
if(height(t.left)==height(t.right))
return true;
return false;
}
//////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 3: A tree is semi-perfect if every node is semi-perfect.
// A node with 0 children is semi-perfect.
// A node with 1 child is NOT semi-perfect.
// A node with 2 children is semi-perfect if (size-of-larger-child <= size-of-smaller-child * 3)
public boolean isSemiBalanced (){
Node t = null;
// A node with 0 children is semi-perfect.
if(t.left==null && t.right==null)
return true;
// A node with 1 child is NOT semi-perfect.
if(t.left==null || t.right==null)
return false;
if(height(t.left)==height(t.right))
return true;
return false;
}
//////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 4:
// tree is odd-perfect if for every node, #odd descendant on left == # odd descendants on right
// A node is odd if it has an odd key
// hint: in the helper, return -1 if the tree is not odd-perfect, otherwise return the odd size
public boolean isOddBalanced()
{
Node t = null;
if(sizeOdd(t.left)==sizeOdd(t.right))
return true;
return false;
}
===============================================
Complete program:
public class NodeOps {
private Node root;
private static class Node {
public final String key;
public Node left, right;
public Node(String key2, Node node, Node node2) {
this.key = key2;
}
}
public static String toString (Node t) {
if (t == null) {
return "null";
} else {
return "new Node (" + t.key + ", " + toString (t.left) + ", " + toString
(t.right) + ")";
}
}
public static String toStringIndent (Node t, String indent) {
if (t == null) {
return indent + "null";
} else {
String indent2 = indent + " ";
return indent + "new Node ( " + indent2 + t.key + ", " + toStringIndent
(t.left, indent2) + ", " + toStringIndent (t.right, indent2) + " " + indent + ")";
}
}
public static Node copy (Node n) {
if (n == null) {
return null;
} else {
return new Node (n.key, copy (n.left), copy (n.right));
}
}
// The size of "null" must be 0.
public static int size (Node t) {
// TODO: Complete this method.
if (t == null) return 0;
// count both left and right child and including
return 1 + size(t.left) + size(t.right);
}
public static int height (Node t)
{
// TODO: Complete this method.
if(t == null)
return -1;
//getting both subtrees height
int lefth = height(t.left);
int righth = height(t.right);
if(lefth > righth)
return lefth + 1;
else
return righth +1;
}
//////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 7: A tree is size-perfect if for every node, size of left == size ofright.
public boolean isPerfectlyBalancedS () {
Node t = null;
if(size(t.left)==size(t.right))
return true;
// TODO: Complete this method.
return false;
}
//////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 8: A tree is height-perfect if for every node, height of left == heightof right.
public boolean isPerfectlyBalancedH () {
Node t = null;
if(height(t.left)==height(t.right))
return true;
return false;
}
//////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 9: A tree is semi-perfect if every node is semi-perfect.
// A node with 0 children is semi-perfect.
// A node with 1 child is NOT semi-perfect.
// A node with 2 children is semi-perfect if (size-of-larger-child <= size-of-smaller-child * 3)
public boolean isSemiBalanced (){
Node t = null;
// A node with 0 children is semi-perfect.
if(t.left==null && t.right==null)
return true;
// A node with 1 child is NOT semi-perfect.
if(t.left==null || t.right==null)
return false;
if(height(t.left)==height(t.right))
return true;
return false;
}
//////////////////////////////////////////////////////////////////////////////////////
// EXERCISE 10:
// tree is odd-perfect if for every node, #odd descendant on left == # odd descendants on right
// A node is odd if it has an odd key
// hint: in the helper, return -1 if the tree is not odd-perfect, otherwise return the odd size
public boolean isOddBalanced()
{
Node t = null;
if(sizeOdd(t.left)==sizeOdd(t.right))
return true;
return false;
}
public static int sizeOdd (Node t)
{
// TODO: Complete this method.
//comapring odd values
if(t==null){
return -1;
}
if ((Integer.parseInt(t.key)%2 == 1)){
return 1+ sizeOdd(t.left) + sizeOdd(t.right);
}
return -1;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.