Question

There are plenty of examples of Binary Search Tree classes written in Java available on the Internet. Find one. Either download or copy and paste the code into an appropriately named Java class file. Compile that file. Then, create the class BinarySrcTree, which will inherit from the class you downloaded from the Internet. Place a comment in the class that states where you obtained your base class (URL or Web page or site name). You will then overwrite or overload to create the following methods:

 leftRotate(Node n) : performs a single left rotation on the specified Node

 fullLeft(Node n): performs a full left rotation on the specified Node

 rightRotate(Node n) : performs a single right rotation on the specified Node

 fullRight(Node n): performs a full right rotation on the specifid Node

 int balance() : returns whether a tree is balanced or not. If it is balanced, it returns a 0. If the left subtree is unbalanced, it returns a negative value, and the actual value will be the node number (counting from the root) of the unbalanced node. If the right subtree is unbalanced, it returns a positive value, calculated the same way.

Answer 1

//JAVA CODE TO COPY//


import java.util.Scanner;

class Node
{
  
Node left, right;
int data;
int height;

public Node root;
public Node()
{
left = null;
right = null;
data = 0;
height = 0;
}

public Node(int n)
{

left = null;
right = null;
data = n;
height = 0;
}
  
public void inorder()
{
inorder(root);
}

private void inorder(Node r)
{
if (r != null)
{
inorder(r.left);
System.out.print(r.data + " ");
inorder(r.right);
}
}

public void preorder()
{

preorder(root);
}

private void preorder(Node r)
{
if (r != null)
{
System.out.print(r.data + " ");
preorder(r.left);
preorder(r.right);
}
}

public void postorder()
{
postorder(root);
}

private void postorder(Node r)
{
if (r != null)
{
postorder(r.left);
postorder(r.right);
System.out.print(r.data + " ");
}
}
  
  
}

//BinarySrcTree class inherited from Node
class BinarySrcTree extends Node
{
  

public BinarySrcTree()
{
root = null;
}
  
private int height(Node t)
{

return t == null ? -1 : t.height;
}

private int max(int lhs, int rhs)
{
return lhs > rhs ? lhs : rhs;
}

void insert(int key) {
root = insertRec(root, key);
}
  
/* A recursive function to insert a new key in Node */
Node insertRec(Node root, int key) {
  
/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(key);
return root;
}
  
/* Otherwise, recur down the tree */
if (key < root.data)
root.left = insertRec(root.left, key);
else if (key > root.data)
root.right = insertRec(root.right, key);
  
/* return the (unchanged) node pointer */
return root;
}

//method leftRotate
Node leftRotate(Node k2)
{
System.out.println("Left Rotation Performed");
Node k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max(height(k2.left), height(k2.right)) + 1;
k1.height = max(height(k1.left), k2.height) + 1;
return k1;
}

//method rightRotate
Node rightRotate(Node k1)
{
//System.out.println("Right Rotation Performed");
Node k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max(height(k1.left), height(k1.right)) + 1;
k2.height = max(height(k2.right), k1.height) + 1;
return k2;
}

//method fullLeftRotate
Node fullLeftRotate(Node k3)
{
System.out.println("Left Rotation Performed");
k3.left = rightRotate(k3.left);
return leftRotate(k3);
}

//method fullRightRotate
private Node fullRightRotate(Node k1)
{
//System.out.println("Right Rotation Performed");
k1.right = leftRotate(k1.right);
return rightRotate(k1);
}

/* Returns 0 if binary tree with root as root is height-balanced */
int balance(Node node)
{
int lh; /* for height of left subtree */
  
int rh; /* for height of right subtree */
  
/* If tree is empty then return 0 */
if (node == null)
return 0;
  
/* Get the height of left and right sub trees */
lh = Nodeheight(node.left);
rh = Nodeheight(node.right);
  
if (Math.abs(lh - rh) <= 1
&& balance(node.left)==0
&& balance(node.right)==0)
return 0;
  
/* If we reach here then tree is not height-balanced */
if(lh>1)
return -lh;
else
return rh;
}
  
/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */
/* The function Compute the "height" of a tree. Height is the
number of nodes along the longest path from the root node
down to the farthest leaf node.*/
int Nodeheight(Node n)
{
/* base case tree is empty */
if (n == null)
return 0;
  
/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + Math.max(Nodeheight(n.left), Nodeheight(n.right));
}
  
  
  
}

//test class
class Test
{
//main driver method
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);

BinarySrcTree sbbst = new BinarySrcTree();
System.out.println("Node Testing\n");

System.out.println("Insert first 5 Elements");
int N = 5;
for (int i = 0; i < N; i++)
{
System.out.println("\nEnter a Number(integer): ");
sbbst.insert(scan.nextInt());

System.out.println("\nPre-order :");
sbbst.preorder();
System.out.println("\nIn-order :");
sbbst.inorder();
System.out.println("\nPost-order :");
sbbst.postorder();

System.out.println();
}
  
int res = sbbst.balance(sbbst.root);
if(res==0)
System.out.println("\nBalance Tree.");
if(res<0)
System.out.println("\nNot a Balance Tree\nLeft Unbalance node height: "+res);
if(res>0)
System.out.println("\nNot a Balance Tree\nRight Unbalance node height: "+res);
System.out.println("\n\nLeft Rotate: "+sbbst.leftRotate(sbbst.root));
sbbst.preorder();
System.out.println("\n\nRight Rotate: "+sbbst.rightRotate(sbbst.root));
sbbst.preorder();
}
}

//PROGRAM OUTPUTS//

//COMMENT DOWN FOR ANY QUERIES...
//HIT A THUMBS UP IF YOU DO LIKE IT!!!