public class BinaryTree {
class TreeNode {
int key, height;
TreeNode left, right;
TreeNode(int d) {
key = d;
height = 1;
}
}
TreeNode root;
BinaryTree() {
root = null;
}
int height(TreeNode N) {
if (N == null)
return 0;
return N.height;
}
TreeNode RR(TreeNode y) {
TreeNode x = y.left;
TreeNode T2 = x.right;
// Perform rotation
x.right = y;
y.left = T2;
// Update heights
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
// Return new root
return x;
}
TreeNode LL(TreeNode x) {
TreeNode y = x.right;
TreeNode T2 = y.left;
y.left = x;
x.right = T2;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
int getBalanceFactor(TreeNode N) {
if (N == null)
return 0;
return height(N.left) - height(N.right);
}
TreeNode add(TreeNode root, int data) {
if (root == null)
return (new TreeNode(data));
if (data < root.key)
root.left = add(root.left, data);
else if (data > root.key)
root.right = add(root.right, data);
else
return root;
root.height = 1 + Math.max(height(root.left), height(root.right));
int bal = getBalanceFactor(root);
if (bal > 1 && data < root.left.key)
return RR(root);
if (bal < -1 && data > root.right.key)
return LL(root);
if (bal > 1 && data > root.left.key) {
root.left = LL(root.left);
return RR(root);
}
if (bal < -1 && data < root.right.key) {
root.right = RR(root.right);
return LL(root);
}
return root;
}
TreeNode minimumValue(TreeNode node) {
TreeNode curr = node;
while (curr.left != null)
curr = curr.left;
return curr;
}
TreeNode remove(TreeNode root, int data) {
if (root == null)
return root;
if (data < root.key)
root.left = remove(root.left, data);
else if (data > root.key)
root.right = remove(root.right, data);
else {
if ((root.left == null) || (root.right == null)) {
TreeNode temp = null;
if (temp == root.left)
temp = root.right;
else
temp = root.left;
if (temp == null) {
temp = root;
root = null;
} else
root = temp;
} else {
TreeNode temp = minimumValue(root.right);
root.key = temp.key;
root.right = remove(root.right, temp.key);
}
}
if (root == null)
return root;
root.height = Math.max(height(root.left), height(root.right)) + 1;
int bal = getBalanceFactor(root);
if (bal > 1 && getBalanceFactor(root.left) >= 0)
return RR(root);
if (bal > 1 && getBalanceFactor(root.left) < 0) {
root.left = LL(root.left);
return RR(root);
}
if (bal < -1 && getBalanceFactor(root.right) <= 0)
return LL(root);
if (bal < -1 && getBalanceFactor(root.right) > 0) {
root.right = RR(root.right);
return LL(root);
}
return root;
}
void inOrder(TreeNode node) {
if (node != null) {
inOrder(node.left);
System.out.print(node.key + " ");
inOrder(node.right);
}
}
public TreeNode Find(TreeNode root, int data)
{
if (root==null || root.key==data)
return root;
if (root.key > data)
return Find(root.left, data);
return Find(root.right, data);
}
public static void main(String[] args) {
BinaryTree aVLTree = new BinaryTree();
for (int i = 1; i <= 5; ++i) {
aVLTree.root = aVLTree.add(aVLTree.root, i);
}
System.out.println("Original Tree");
aVLTree.inOrder(aVLTree.root);
aVLTree.root = aVLTree.remove(aVLTree.root, 4);
System.out.println("\nAfter Removing 4");
aVLTree.inOrder(aVLTree.root);
if(aVLTree.Find(aVLTree.root, 5) != null)
System.out.println("\nNode with value 5 is found");
else
System.out.println("\nNode with value 5 is NOT found");
}
}
===========================
See Output
Thanks, PLEASE UPVOTE if helpful
java Description You are to create a class named BinaryTree. This will simulate a balanced and...
I need to do a tree sort method but the treesortMethod is not working /****Binarytree class****\ package Tree; public class BinaryTree { private TreeNode root; // head of the list //constructor - create an empty binary tree public BinaryTree() { root = null; } //isEmpty() - return true if tree is empty, false otherwise public boolean isEmpty() { return (root == null); } //deleteTree() - remove all items from tree public void deleteList() { root =...
BST JAVA FILE import java.util.*; public class BST <E extends Comparable <E>> { private TreeNode<E> overallRoot; public BST() { overallRoot = null; } // ************ ADD ************ // public void add(E addThis) { if (overallRoot == null) { overallRoot = new TreeNode<>(addThis); } else { add(overallRoot, addThis); } } private TreeNode<E> add(TreeNode<E> node, E addThis) { if...
In java, create class BNode(T), which implements the interface TreeNode(T) interface methods: void setRight(TreeNode(T) right) - sets right side of node, where right is the node to the right of this node void setRight(TreeNode(T) left) - sets left side of node, where left is the node to the left of this node TreeNode getRight() - gets the right node TreeNode getLeft() - gets the left node T getData() - gets the data within the node THEN, create class BT(E), which...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to completely test every method in the BST class to ensure the class meets all its requirements. You should read the Listing 25.5: TestBST.java for an idea of what your program should look like. Listing 25.4 BST.java public class BST> extends AbstractTree { protected TreeNode...
please do this lab in Java in given instructions by tomorrow morning. TkA CHRI - TREE UTH A HEAPOF PRESDNS CENETH CSC 236-Lab 6 (2 programs) trees 1. Given the two binary trees below: 14 18 16) Write a method called swapSubtrees, which swaps all of the left and right subtrees in the above binary trees. Add this method to the class BinaryTree and create a program to test this method for these 2 trees. Show the original trees and...
in java ..write all complete program from a- e 1. Given the two binary trees below: 14 16 Write a method called swapSubtrees, which swaps all of the left and right subtrees in the above binary trees. Add this method to the class BinaryTree and create a program to test this method for these 2 trees. Show the original trees and the resulting trees. Note: To test your algorithm, first create a binary search tree. Write a method called singleParent,...
java language please. thank you T-Mobile 9:00 AM For this assignment, create a Java class named "MyRectangle3d" Your class must have the following attributes or variables · x (the x coordinate of the rectangle, an integer) * y (the y coordinate of the rectangle, an integer) * length (the length of the rectangle, an integer) * width (the width of the rectangle, an integer) * height (the height of the rectangle, an integer) * color( the color of the rectangle,...
Create a basic math quiz program that creates a set of 10 randomly generated math questions for the following operations:AdditionSubtractionMultiplicationDivisionModuloExponentThe following source files are already complete and CANNOT be changed:MathQuiz.java (contains the main() method)OperationType.java (defines an enumeration for valid math operations and related functionality)The following source files are incomplete and need to be coded to meet the indicated requirements:MathQuestionable.javaA Random object called RANDOM has already been declared and assigned, and you must not change this assignment in any way.Declare and assign an interface integer called MAX_SMALL and assign it the...
Part I: Create a doubly linked circular list class named LinkedItemList that implements the following interface: /** * An ordered list of items. */ public interface ItemList<E> { /** * Append an item to the end of the list * * @param item – item to be appended */ public void append(E item); /** * Insert an item at a specified index position * * @param item – item to be...
Java Create a class named OrderedList. It will use a LinkedList of integers as its attribute. The constructor will simply create an empty list. This will be a different LinkedList, as all of the items will be in ascending numerical order. That means items will not necessarily be placed at the end of the list, but placed where it should be located. Note that the iterator simply uses the next() method, so if you use the iterator to find the...