Here are 4 classes: AVLtree, BinarySearchTree, BinaryNode, and TreePrinter. None

Question

Here are 4 classes: AVLtree, BinarySearchTree, BinaryNode, and TreePrinter. None of them need to be modified. Please make a tester with a main method for these classes to print out all the AVL and Binary Search Trees.

*****************************************AVLTREE:****************************************************************************************************

public class AVLTree<T extends Comparable<T>> extends BinarySearchTree<T>
{
private static final int ALLOWED_IMBALANCE = 1;

private boolean shouldPrintRotations;

public AVLTree()
{
this(false);
}

public AVLTree(boolean shouldPrintRotations)
{
this.shouldPrintRotations = shouldPrintRotations;
}

public boolean isBalanced()
{
return isBalanced(root);
}

private boolean isBalanced(BinaryNode<T> root)
{
if(root == null)
{
return true;
}
else
{
int leftHeight = height(root.getLeft());
int rightHeight = height(root.getRight());
return Math.abs(leftHeight - rightHeight) <= 1;
}
}

@Override
protected BinaryNode<T> insert(T data, BinaryNode<T> root)
{
return balance(super.insert(data, root));
}

@Override
protected BinaryNode<T> remove(T data, BinaryNode<T> root)
{
return balance(super.remove(data, root));
}

private BinaryNode<T> balance(BinaryNode<T> root)
{
if(root == null)
{
return null;
}

if(height(root.getLeft()) - height(root.getRight()) > 1)
{
if(height(root.getLeft().getLeft()) >= height(root.getLeft().getRight()))
{
root = singleRightRotation(root);
}
else
{
root = doubleLeftRightRotation(root);
}
}
else if(height(root.getRight()) - height(root.getLeft()) > 1)
{
if(height(root.getRight().getRight()) >= height(root.getRight().getLeft()))
{
root = singleLeftRotation(root);
}
else
{
root = doubleRightLeftRotation(root);
}
}

return root;
}

private BinaryNode<T> singleRightRotation(BinaryNode<T> k2)
{
if(shouldPrintRotations)
{
System.out.println("Single Right Rotation: " + k2.getData());
}
BinaryNode<T> k1 = k2.getLeft();
k2.setLeft(k1.getRight());
k1.setRight(k2);
k2.setHeight(Math.max(height(k2.getLeft()), height(k2.getRight())) + 1);
k1.setHeight(Math.max(height(k1.getLeft()), k2.getHeight()) + 1);
return k1;
}

private BinaryNode<T> singleLeftRotation(BinaryNode<T> k1)
{
if(shouldPrintRotations)
{
System.out.println("Single Left Rotation: " + k1.getData());
}
BinaryNode<T> k2 = k1.getRight();
k1.setRight(k2.getLeft());
k2.setLeft(k1);
k1.setHeight(Math.max(height(k1.getLeft()), height(k1.getRight())) + 1);
k2.setHeight(Math.max(height(k2.getRight()), k1.getHeight()) + 1);
return k2;
}

private BinaryNode<T> doubleLeftRightRotation(BinaryNode<T> k3)
{
if(shouldPrintRotations)
{
System.out.println("Double Left-Right Rotation: " + k3.getData());
}
k3.setLeft(singleLeftRotation(k3.getLeft()));
return singleRightRotation(k3);
}

private BinaryNode<T> doubleRightLeftRotation(BinaryNode<T> k1)
{
if(shouldPrintRotations)
{
System.out.println("Double Right-Left Rotation: " + k1.getData());
}
k1.setRight(singleRightRotation(k1.getRight()));
return singleLeftRotation(k1);
}
}

*************************************************************BINARYSEARCHTREE*****************************************************************************************************

import java.util.Comparator;
public class BinarySearchTree<T extends Comparable<T>> {
protected BinaryNode<T> root;
public BinarySearchTree() {
root = null;
}
public void empty() {
root = null;
}
public boolean isEmpty(){
return root == null;
}
public BinaryNode<T> getRoot(){
return root;
}
public int height() {
return height(root);
}
protected int height(BinaryNode<T> root) {
if(root == null) {
return -1;
} else {
return Math.max(height(root.getLeft()), height(root.getRight())) + 1;
}
}
public boolean contains(T data){
return contains(data, root);
}
protected boolean contains(T data, BinaryNode<T> root){
if(root == null){
return false;
}
int compareResult = root.getData().compareTo(data);
if(compareResult > 0){
return contains(data, root.getLeft());
}
else if(compareResult < 0){
return contains(data, root.getRight());
}
else{
return true;
}
}
public T findMin() {
BinaryNode<T> node = findMin(root);
return node == null ? null : node.getData();
}
protected BinaryNode<T> findMin(BinaryNode<T> root) {
if(root == null) {
return null;
} else if(root.getLeft() == null) {
return root;
} else {
return findMin(root.getLeft());
}
}
public T findMax() {
BinaryNode<T> node = findMax(root);
return node == null ? null : node.getData();
}
protected BinaryNode<T> findMax(BinaryNode<T> root) {
if(root == null) {
return null;
} else if(root.getRight() == null) {
return root;
} else {
return findMin(root.getRight());
}
}

public void insert(T data) {
root = insert(data, root);
}

protected BinaryNode<T> insert(T data, BinaryNode<T> root) {
if(root == null) {
return new BinaryNode<>(data);
}
int compareResult = root.getData().compareTo(data);

if(compareResult > 0) {
root.setLeft(insert(data, root.getLeft()));
} else if(compareResult < 0) {
root.setRight(insert(data, root.getRight()));
}
return root;
}
public void remove(T data) {
root = remove(data, root);
}
protected BinaryNode<T> remove(T data, BinaryNode<T> root) {
if(root == null) {
return null;
}
int compareResult = root.getData().compareTo(data);
if(compareResult > 0) {
root.setLeft(remove(data, root.getLeft()));
} else if(compareResult < 0) {
root.setRight(remove(data, root.getRight()));
} else if(root.getLeft() != null && root.getRight() != null) {
root.setData(findMin(root.getRight()).getData());
root.setRight(remove(root.getData(), root.getRight()));
} else {
root = root.getLeft() != null ? root.getLeft() : root.getRight();
}
return root;
}
public void printTree() {
printTree(root);
}
protected void printTree(BinaryNode<T> root) {
if(root != null) {
printTree(root.getLeft());
System.out.println(root.getData());
printTree(root.getRight());
}
}
}

******************************************************************BINARYNODE**********************************************************************************************************

public class BinaryNode<T extends Comparable<T>>
{
private T data;
private int height;
private BinaryNode<T> left;
private BinaryNode<T> right;

public BinaryNode(T data)
{
this(data, null, null);
}

public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right)
{
this.data = data;
this.left = left;
this.right = right;
this.height = 0;
}

  
public T getData()
{
return data;
}

  
public void setData(T data)
{
this.data = data;
}

public BinaryNode<T> getLeft()
{
return left;
}

public void setLeft(BinaryNode<T> left)
{
this.left = left;
}

public BinaryNode<T> getRight()
{
return right;
}

public void setRight(BinaryNode<T> right)
{
this.right = right;
}

public int getHeight()
{
return height;
}

public void setHeight(int height)
{
this.height = height;
}
}

**************************************************************************TREEPRINTER*************************************************************************************************

public class TreePrinter
{
private static final int MAX_LEVELS = 6;
  
private BinarySearchTree<Integer> tree; // the tree
private int height; // its height
  
// Powers of 2
private static int POWERS_OF_2[] = new int[MAX_LEVELS+2];
static {
int power = 1;
for (int i = 0; i < MAX_LEVELS + 2; i++) {
POWERS_OF_2[i] = power;
power *= 2;   
}
}
  
/**
* Constructor
* @param tree the tree to print.
*/
public TreePrinter(BinarySearchTree<Integer> tree)
{
this.tree = tree;
this.height = tree.height();
}
  
/**
* Print the tree using a level-order traversal.
* @param label the label to print before the tree.
*/
public void print(String label)
{
System.out.println(label);

// Queue of nodes at this level.
BinaryNode<Integer> thisLevelNodes[] =
(BinaryNode<Integer>[]) new BinaryNode[1];
  
int offset = POWERS_OF_2[(height+1)]-1;
  
thisLevelNodes[0] = tree.getRoot();
  
// Loop to print each level of nodes.
for (int level = 0; level <= height; level++) {
if (level > MAX_LEVELS) {
System.out.println("*** Too many levels to print. ***");
break;
}
  
// Print node data.
printData(level, offset, thisLevelNodes);
  
if (level != height) {
  
// Print outgoing pointers / from each parent node.
printOutgoingPointers(level, offset, thisLevelNodes);
  
offset = POWERS_OF_2[height - level] - 1;
  
// Print connecting dashes ----
if (level < height-1) {
printConnectingDashes(level, offset, thisLevelNodes);
}
  
// Print incoming pointers / and to each child node.
printIncomingPointers(level, offset, thisLevelNodes);
  
// Prepare the next level of nodes.
thisLevelNodes = nextLevel(level, thisLevelNodes);
}
}
}
  
/**
* Print node data.
* @param level the current level
* @param offset the current offset
* @param levelNodes the current level of nodes
*/
private void printData(int level, int offset,
BinaryNode<Integer> levelNodes[])
{
printSpaces(offset);
  
int k = POWERS_OF_2[level];
for (int i = 0; i < k; i++) {
BinaryNode<Integer> node = levelNodes[i];
  
if (node != null) {
System.out.printf("%3d ", node.getData());
}
else {
System.out.print(" ");
}
  
// Space over to the next node in this level.
if (i < k-1) printSpaces(2*offset - 2);
}
  
System.out.println();
}
  
/**
* Print outgoing pointers / from each non-null parent node.
* @param level the current level
* @param offset the current offset
* @param levelNodes the current level of nodes
*/
private void printOutgoingPointers(int level, int offset,
BinaryNode<Integer> levelNodes[])
{
printSpaces(offset);
  
int k = POWERS_OF_2[level];
for (int i = 0; i < k; i++) {
BinaryNode<Integer> node = levelNodes[i];
  
// Has left child: print /
if ((node != null) && (node.getLeft() != null)) {
System.out.print(" /");
}
  
// No left child: print space
else {
System.out.print(" ");
}
  
// Has right child: print
if ((node != null) && (node.getRight() != null)) {
System.out.print("\ ");
}
  
// No right child: print space
else {
System.out.print(" ");
}
  
// Space over to the next node in this level.
if (i < k-1) printSpaces(2*offset-2);
}
  
System.out.println();
}
  
/**
* Print the connecting dashes between
* an outgoing pointer and an incoming pointer.
* @param level the current level
* @param offset the current offset
* @param levelNodes the current level of nodes
*/
private void printConnectingDashes(int level, int offset,
BinaryNode<Integer> levelNodes[])
{
if (offset > 1) printSpaces(offset);
  
int k = POWERS_OF_2[level];
for (int i = 0; i < k; i++) {
BinaryNode<Integer> node = levelNodes[i];
  
// Has left child: print dashes
if ((node != null) && (node.getLeft() != null)) {
printSpaces(3);
printDashes(offset-1);
}
  
// No left child: print spaces
else {
printSpaces(offset+2);
}
  
// Has right child: print dashes
if ((node != null) && (node.getRight() != null)) {
printSpaces(2);
printDashes(offset-1);
}
  
// No right child: print spaces
else {
printSpaces(offset+1);
}
  
// Space over to the next node in this level.
if (i < k-1) printSpaces(2*offset+1);
}
  
System.out.println();
}
  
/**
* Print incoming pointers / or to each non-null child node.
* @param level the current level
* @param offset the current offset
* @param levelNodes the current level of nodes
*/
private void printIncomingPointers(int level, int offset,
BinaryNode<Integer> levelNodes[])
{
printSpaces(offset);
  
int k = POWERS_OF_2[level];
for (int i = 0; i < k; i++) {
BinaryNode<Integer> node = levelNodes[i];
  
// Left child: print /
if ((node != null) && (node.getLeft() != null)) {
System.out.print(" /");
}
  
// No left child: print spaces
else {
printSpaces(3);
}
  
// Right child: print
if ((node != null) && (node.getRight() != null)) {
printSpaces(2*offset);
System.out.print("\");
}
  
// No right child: print spaces
else {
printSpaces(2*offset+1);
}
  
// Space over to the next node in this level.
if (i < k-1) printSpaces(2*offset);
}
  
System.out.println();
}
  
/**
* Prepare the next level of nodes.
* @param level the current level
* @param levelNodes the current level of nodes
* @return the next level of nodes.
*/
private BinaryNode<Integer>[] nextLevel(int level,
BinaryNode<Integer> levelNodes[])
{
BinaryNode<Integer> nextLevel[] =
(BinaryNode<Integer>[]) new BinaryNode[POWERS_OF_2[level+1]];
  
for (int i = 0; i < POWERS_OF_2[level]; i++) {
BinaryNode<Integer> node = levelNodes[i];
  
// Queue the left child nodes of each non-null parent node.
nextLevel[2*i] = (node != null) && (node.getLeft() != null)
? node.getLeft() : null;
  
// Queue the right child nodes of each non-null parent node.
nextLevel[2*i+1] = (node != null) && (node.getRight() != null)
? node.getRight() : null;
}
  
return nextLevel;
}
  
/**
* Print spaces.
* @param count the number of spaces.
*/
private void printSpaces(int count)
{
for (int i = 0; i < count; i++)
System.out.print(" ");
}
  
/**
* Print dashes.
* @param count the number of dashes.
*/
private void printDashes(int count)
{
for (int i = 0; i < count; i++) System.out.print("-");
}
}

Thanks!!

Explanation / Answer

public class Tetser {

   publc static void main(String args[]) {

       BinarySearchTree<Integer> bt = new BinarySearchTree<Integer>();

       AVLTree<Integer> avl = new AVLTree<Integer>();

       Random rand = new Random();

       System.out.println("Is the binary search tree empty? : " + bt.isEmpty());

       for(int i=0; i<20; i++) {

           bt.insert(rand.nextInt(100));

       }

       System.out.println("Does the binary search tree contain 50? : " + bt.contains(50));

       System.out.println("Maximum value : " + bt.findMax());

       System.out.println("Minimum value : " + bt.findMin());

       bt.remove(50);

       bt.printTree();

       System.out.println("Is the AVL search tree empty? : " + avl.isEmpty());

       for(int i=0; i<20; i++) {

           avl.insert(rand.nextInt(100), avl.getRoot());

       }

       System.out.println("Does the AVL search tree contain 50? : " + avl.contains(50));

       System.out.println("Maximum value : " + avl.findMax());

       System.out.println("Minimum value : " + avl.findMin());

       avl.remove(50);

       avl.printTree();

   }

}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.