public class BTNode

{

private E data;

private BTNode left, right;

public BTNode(E initialData, BTNode initialLeft, BTNode initialRight)

{

data = initialData;

left = initialLeft;

right = initialRight;

}

public E getData( )

{

return data;

}

public BTNode getLeft( )

{

return left;

}

public E getLeftmostData( )

{

if (left == null)

return data;

else

return left.getLeftmostData( );

}

public BTNode getRight( )

{

return right;

}

// !!! this may need some work

public E getRightmostData( )

{

if (right == null)

return data;

else

return right.getRightmostData( );

}

public boolean isLeaf( )

{

return (left == null) && (right == null);

}

public void inorderPrint( )

{

if (left != null)

left.inorderPrint( );

System.out.println(data);

if (right != null)

right.inorderPrint( );

}

public void preorderPrint( )

{

System.out.println(data);

if (left != null)

left.preorderPrint( );

if (right != null)

right.preorderPrint( );

}

public void postorderPrint( )

{

if (left != null)

left.postorderPrint( );

if (right != null)

right.postorderPrint( );

System.out.println(data);

}

// inorder print with indentations

public void print(int depth)

{

int i;

// Print the indentation and the data from the current node:

for (i = 1; i

System.out.print(" ");

System.out.println(data);

// Print the left subtree (or a dash if there is a right child and no left child)

if (left != null)

left.print(depth+1);

else if (right != null)

{

for (i = 1; i

System.out.print(" ");

System.out.println("--");

}

// Print the right subtree (or a dash if there is a left child and no left child)

if (right != null)

right.print(depth+1);

else if (left != null)

{

for (i = 1; i

System.out.print(" ");

System.out.println("--");

}

}

public BTNode removeLeftmost( )

{

if (left == null)

return right;

else

{

left = left.removeLeftmost( );

return this;

}

}

public BTNode removeRightmost( )

{

if (right == null)

return left;

else

{

right = right.removeRightmost( );

return this;

}

}

public void setData(E newData)

{

data = newData;

}

public void setLeft(BTNode newLeft)

{

left = newLeft;

}

public void setRight(BTNode newRight)

{

right = newRight;

}

public static BTNode treeCopy(BTNode source)

{

BTNode leftCopy, rightCopy;

if (source == null)

return null;

else

{

leftCopy = treeCopy(source.left);

rightCopy = treeCopy(source.right);

return new BTNode(source.data, leftCopy, rightCopy);

}

}

// return the number of nodes in the tree

public static long treeSize(BTNode root)

{

if (root == null)

return 0;

else

return 1 + treeSize(root.left) + treeSize(root.right);

}

}

Binary Tree a tree in which each node has at most two subtrees, labeled left and right Binary Search Tree-a binary tree organized such that all values in the left subtree are less than the value in a node and all values in the right subtree are greater than the value in the node. AVL Tree (invented by Adelson-Velskii and Landis) a dynamically balanced binary search tree where pairs of subtrees differ in height by at most 1 Helpful: The Java Math class has a method named max that returns the maximum value of its two parameters Create a Java program named Lab7 java. In this program, Therefore, the method should accept When the method 1) Write a method that will sort an array of integers. The array is not necessanily full. two parameters: the array and an integer that determines the number of elements that are occupied. is finished, the array should be sorted in non-descending order 2) The parameters to the method are the array write a method that will read integers from a file and store them in an array and the FILE reference. The method should stop reading input when one of the following situations occurs: ethe array is ful there is no more data in the file (the hasNext method returns false) The return value is the number of elements that were actually stored in the array *At this point, I recommend you write a main method just so you can test these methods. When you're sure that they work correctly, proceed to the next step. Download the file BTNode java and make these modifications 3) Add an instance variable named height. The definition of height is as follows: a. a leaf has height1 b. a non-leaf has height one more than the maximum of the heights of its left and right subtrees 4) Add an accessor and a mutator for height. 5) Implement the insertion algorithm for a balanced binary search tree (AVL tree). " write a main method in Lab7.java. The main method should do the following: 6) Create an empty balanced, binary search tree of integers (type BTNode cinteger> 7) Create an array of 100 integers. 8) Prompt the user for a filename. 9) Read integers from the file and store them in the array using the method written in step1. Keep track of the number returned from the method because it tells you how many elements of the array were filled 10) Sort the array using the method written in step 2