JAVA CODE Topic: BST Animation For each task, submit the source code with detail comments. Objective: javafx GUI program for BST Animation.
BSTAnimation.java, AbstractTree.java and Tree.java. Modify the BSTAnimation.java (1) Add Show Preoreder and Show Postorder button. Insert these two buttons next to the Show Inorder button to display tree in selected order. (2) Currently removing node method is to replace the removed node by the highest node on left-subtree. Modify the method by using lowest node on the right-subtree instead.
AbstractTree.java
public abstract class AbstractTree<E extends
Comparable<E>>
implements Tree<E> {
@Override /** Inorder traversal from the root*/
public void inorder() { }
@Override /** Postorder traversal from the root */
public void postorder() {}
@Override /** Preorder traversal from the root */
public void preorder() {}
@Override /** Return true if the tree is empty */
public boolean isEmpty() {
return getSize() == 0;
}
}
Please let me know if you have any doubts or you want me to modify the answer. And if you find this answer useful then don't forget to rate my answer as thumps up. Thank you! :)
import javafx.application.Application;
import javafx.geometry.Pos;
import javafx.stage.Stage;
import javafx.scene.Scene;
import javafx.scene.control.Button;
import javafx.scene.control.Label;
import javafx.scene.control.TextField;
import javafx.scene.layout.BorderPane;
import javafx.scene.layout.HBox;
public class BSTAnimation extends Application {
@Override
public void start(Stage primaryStage) {
BST<Integer> tree
= new BST<>();
BorderPane pane = new
BorderPane();
BTView view = new
BTView(tree);
pane.setCenter(view);
TextField tfKey = new
TextField();
tfKey.setPrefColumnCount(3);
tfKey.setAlignment(Pos.BASELINE_RIGHT);
Button btInsert = new
Button("Insert");
Button btDelete = new
Button("Delete");
Button btSearch = new
Button("Search");
Button btInOrder = new
Button("Inorder");
Button btPreOrder = new
Button("Preorder");
Button btPostOrder = new
Button("Postorder");
Button btBreadthFirst =
new Button("Breadth-First");
Button btHeight = new
Button("Height");
HBox hBox = new
HBox(5);
hBox.getChildren().addAll(new Label("Enter a key: "),
tfKey, btInsert, btDelete, btSearch, btInOrder, btPreOrder,
btPostOrder, btBreadthFirst, btHeight);
hBox.setAlignment(Pos.CENTER);
pane.setBottom(hBox);
btInsert.setOnAction(e -> {
int key = Integer.parseInt(tfKey.getText());
if (tree.search(key)) {
view.displayTree();
view.setStatus(key + " is already in the tree");
}
else {
tree.insert(key);
view.displayTree();
view.setStatus(key + " is inserted in the tree");
}
});
btDelete.setOnAction(e -> {
int key = Integer.parseInt(tfKey.getText());
if (!tree.search(key)) {
view.displayTree();
view.setStatus(key + " is not in the tree");
}
else {
tree.delete(key);
view.displayTree();
view.setStatus(key + " is deleted from the tree");
}
});
btSearch.setOnAction(e ->
{
int key = Integer.parseInt(tfKey.getText());
if (!tree.search(key))
{
view.displayTree();
view.setStatus(key + " is not in the tree");
}
else
{
view.searchPath(tree.path(key));
view.displayTree();
view.setStatus("Found " + key + " in the tree");
view.searchPath(null);
}
});
btInOrder.setOnAction(e ->
{
if (tree.isEmpty())
{
view.displayTree();
view.setStatus("Tree is empty");
}
else
{
view.displayTree();
view.setStatus("Inorder traversal: " +
tree.inorderList().toString());
}
});
btPreOrder.setOnAction(e ->
{
if (tree.isEmpty())
{
view.displayTree();
view.setStatus("Tree is empty");
}
else
{
view.displayTree();
view.setStatus("Preorder traversal: " +
tree.preorderList().toString());
}
});
btPostOrder.setOnAction(e ->
{
if (tree.isEmpty())
{
view.displayTree();
view.setStatus("Tree is empty");
}
else
{
view.displayTree();
view.setStatus("PostOrder traversal: " +
tree.postorderList().toString());
}
});
btBreadthFirst.setOnAction(e ->
{
if (tree.isEmpty())
{
view.displayTree();
view.setStatus("Tree is empty");
}
else
{
view.displayTree();
view.setStatus("Breadth-First Traversal: " +
tree.breadthFirstOrderList().toString());
}
});
btHeight.setOnAction(e ->
{
view.displayTree();
view.setStatus("Tree height is " + tree.height());
});
Scene scene = new
Scene(pane, 700, 250);
primaryStage.setTitle("BSTAnimation");
primaryStage.setScene(scene);
primaryStage.show();
}
public static void main(String[] args) {
launch(args);
}
}
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class BST<E extends Comparable<E>> implements
Tree<E> {
protected TreeNode<E> root;
protected int size = 0;
public BST() {
}
public BST(E[] objects) {
for (int i = 0; i <
objects.length; i++)
add(objects[i]);
}
@Override
public boolean search(E e) {
TreeNode<E>
current = root;
while (current !=
null) {
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else
return true;
}
return false;
}
@Override
public boolean insert(E e) {
if (root == null)
root = createNewNode(e);
else {
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null)
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
return false;
if (e.compareTo(parent.element) < 0)
parent.left = createNewNode(e);
else
parent.right = createNewNode(e);
}
size++;
return true;
}
protected TreeNode<E> createNewNode(E
e) {
return new
TreeNode<>(e);
}
@Override
public void inorder() {
inorder(root);
}
protected void inorder(TreeNode<E>
root) {
if (root == null)
return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
@Override
public void postorder() {
postorder(root);
}
protected void postorder(TreeNode<E>
root) {
if (root == null)
return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}
@Override
public void preorder() {
preorder(root);
}
protected void preorder(TreeNode<E>
root) {
if (root == null)
return;
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}
public static class TreeNode<E> {
protected E
element;
protected
TreeNode<E> left;
protected
TreeNode<E> right;
public TreeNode(E e)
{
element = e;
}
}
@Override
public int getSize() {
return size;
}
public TreeNode<E> getRoot() {
return root;
}
public
java.util.ArrayList<TreeNode<E>> path(E e) {
java.util.ArrayList<TreeNode<E>> list =
new java.util.ArrayList<>();
TreeNode<E>
current = root;
while (current !=
null) {
list.add(current);
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else
break;
}
return list;
}
@Override
public boolean delete(E e) {
TreeNode<E> parent
= null;
TreeNode<E>
current = root;
while (current != null)
{
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
break;
}
if (current ==
null)
return false;
if (current.left ==
null) {
if (parent == null) {
root = current.right;
}
else {
if (e.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
}
else {
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right;
}
current.element = rightMost.element;
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
parentOfRightMost.left = rightMost.left;
}
size--;
return true;
}
@Override
public java.util.Iterator<E> iterator()
{
return new
InorderIterator();
}
private class InorderIterator implements
java.util.Iterator<E> {
private
java.util.ArrayList<E> list =
new java.util.ArrayList<>();
private int current =
0;
private boolean
canRemove = false;
public
InorderIterator() {
inorder();
}
private void
inorder() {
inorder(root);
}
private void
inorder(TreeNode<E> root) {
if (root == null) return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
@Override
public boolean hasNext()
{
return current < list.size();
}
@Override
public E next() {
if (hasNext())
canRemove = true;
else
throw new java.util.NoSuchElementException();
return list.get(current++);
}
@Override
public void remove()
{
if (!canRemove)
throw new IllegalStateException();
else {
delete(list.get(--current));
canRemove = false;
}
list.clear();
inorder();
}
}
@Override
public void clear() {
root = null;
size = 0;
}
public java.util.List<E>
inorderList()
{
List<E> list = new
ArrayList<E>();
inorderList(root,
list);
return list;
}
private void inorderList(TreeNode<E> root,
List<E> list)
{
if (root == null)
return;
inorderList(root.left,
list);
list.add(root.element);
inorderList(root.right,
list);
}
public java.util.List<E>
preorderList()
{
List<E> list = new
ArrayList<E>();
preorderList(root,
list);
return list;
}
private void preorderList(TreeNode<E>
root, List<E> list)
{
if (root == null)
return;
list.add(root.element);
preorderList(root.left,
list);
preorderList(root.right,
list);
}
public java.util.List<E>
postorderList()
{
List<E> list = new
ArrayList<E>();
postorderList(root,
list);
return list;
}
private void postorderList(TreeNode<E>
root, List<E> list)
{
if (root == null)
return;
postorderList(root.left,
list);
postorderList(root.right, list);
list.add(root.element);
}
public java.util.List<E>
breadthFirstOrderList()
{
Queue<TreeNode<E>> q = new
LinkedList<TreeNode<E>>();
List<E> list = new
ArrayList<E>();
q.add(root);
while(!q.isEmpty())
{
TreeNode<E> node = q.remove();
list.add(node.element);
if (node.left != null)
q.add(node.left);
if (node.right != null)
q.add(node.right);
}
return list;
}
public int height()
{
if (size == 0)
return -1;
else if (size ==
1)
return 0;
else
{
return height(root) - 1;
}
}
public int height(TreeNode<E> root)
{
if (root == null)
return 0;
else
return 1 + Math.max(height(root.left), height(root.right));
}
}
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
import java.util.List;
import javafx.scene.layout.Pane;
import javafx.scene.paint.Color;
import javafx.scene.shape.Circle;
import javafx.scene.shape.Line;
import javafx.scene.text.Text;
public class BTView extends Pane {
private BST<Integer> tree = new
BST<>();
private double radius = 15;
private double vGap = 50;
private List<?> path;
BTView(BST<Integer> tree) {
this.tree = tree;
setStatus("Tree is
empty");
}
public <E> void
searchPath(List<E> list)
{
path = list;
}
public void setStatus(String msg) {
getChildren().add(new
Text(20, 20, msg));
}
public void displayTree() {
this.getChildren().clear();
if (tree.getRoot() !=
null) {
displayTree(tree.getRoot(), getWidth() / 2, vGap,
getWidth() / 4);
}
}
private void
displayTree(BST.TreeNode<Integer> root,
double x, double y, double hGap) {
if (root.left != null)
{
getChildren().add(new Line(x - hGap, y + vGap, x, y));
displayTree(root.left, x - hGap, y + vGap, hGap / 2);
}
if (root.right !=
null) {
getChildren().add(new Line(x + hGap, y + vGap, x, y));
displayTree(root.right, x + hGap, y + vGap, hGap / 2);
}
Circle circle = new
Circle(x, y, radius);
circle.setFill(Color.WHITE);
if(path!=null &&
!path.isEmpty())
{
if(path.contains(root))
circle.setFill(Color.ORANGE);
}
circle.setStroke(Color.BLACK);
getChildren().addAll(circle,
new Text(x - 4, y + 4, root.element + ""));
}
}
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
import java.util.Collection;
public interface Tree<E> extends
java.util.Collection<E> {
public boolean search(E e);
public boolean insert(E e);
public boolean delete(E e);
public int getSize();
public default void inorder() {
throw new
UnsupportedOperationException();
}
public default void postorder() {
}
public default void preorder() {
}
@Override
public default boolean isEmpty() {
return size() ==
0;
};
@Override
public default boolean contains(Object e)
{
return
search((E)e);
}
@Override
public default boolean add(E e) {
return insert(e);
}
@Override
public default boolean remove(Object e) {
return
delete((E)e);
}
@Override
public default int size() {
return getSize();
}
@Override
public default boolean
containsAll(Collection<?> c) {
return false;
}
@Override
public default boolean addAll(Collection<?
extends E> c) {
return false;
}
@Override
public default boolean
removeAll(Collection<?> c) {
return false;
}
@Override
public default boolean
retainAll(Collection<?> c) {
return false;
}
@Override
public default Object[] toArray() {
return null;
}
@Override
public default <T> T[] toArray(T[] array)
{
return null;
}
}
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
JAVA CODE Topic: BST Animation For each task, submit the source code with detail comments. Objective:...
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...
write a new test program called RemoveDuplicates.java. The program reads text input from keyboard or a text file and adds the words to a BST. The program then traverses the BST and prints out the words in order (based on ASCII/UNICODE order) on the screen (or to output text file). Note that you may need to make some changes to BST.java. Sample test: ----jGRASP exec: java -ea removeDuplicates Original Text: a B 2 n w C q K l 0...
QUESTION 8 In the _____ traversal, the root is processed first, before its subtrees. breadth first preorder postorder inorder 0.10000 points QUESTION 9 What kind of traversal does the following algorithm (in pseudo-code) describe? Algorithm traversal (root) if (root is not null) traversal (leftSubTree) process (root) traversal (rightSubTree) end if end traversal breadth first preorder inorder postorder 0.10000 points QUESTION 10 What kind of traversal does the following algorithm (in pseudo-code) describe? Algorithm traversal (root) if...
Im having trouble implimenting the addAll method.. import java.util.Collection; public interface Tree<E> extends Collection<E> { /** Return true if the element is in the tree */ public boolean search(E e); /** Insert element e into the binary tree * Return true if the element is inserted successfully */ public boolean insert(E e); /** Delete the specified element from the tree * Return true if the element is deleted successfully */ public boolean delete(E e); /** Get the number of...
Question - modify the code below so that for a node, the value of every node of its right subtree is less the node, and the value of each node of its left subtree is greater than the node. - create such a binary tree in the Main method, and call the following method: InOrder(Node theRoot), PreOrder(Node theRoot), PostOrder(Node theRoot), FindMin(), FindMax(), Find(int key) using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;...
using java to write,show me the output. please write some common. You CAN NOT use inbuild functions for Tree ADT operations. using code below to finsih public class Main { public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.left = new Node(6); tree.root.right.right = new Node(7); tree.root.left.left.left = new Node(8); tree.root.left.left .right= new Node(9);...
In Java. How would this method look? LinkedBinaryTree.java import java.util.Iterator; public class LinkedBinaryTree implements BinaryTreeADT { private BinaryTreeNode root; /** * Creates an empty binary tree. */ public LinkedBinaryTree() { root = null; } /** * Creates a binary tree from an existing root. */ public LinkedBinaryTree(BinaryTreeNode root) { this.root = root; } /** * Creates a binary tree with the specified element...
Can you take a look at my code that why the maxDepth function is not working? public class BinaryTree { class Node{ int key; Node left,right; public Node(int item) { key = item; left = right = null; } } Node root; public void BinaryTree(){ root = null; } void...
1) Extend the Binary Search Tree ADT to include a public method leafCount that returns the number of leaf nodes in the tree. 2) Extend the Binary Search Tree ADT to include a public method singleParent-Count that returns the number of nodes in the tree that have only one child. 3) The Binary search tree ADT is extended to include a boolean method similarTrees that receives references to two binary trees and determines whether the shapes of the trees are...
Test Data would be as follows: Using java language. Build an expression tree. • When you see a number: o you create a new node with the number as the data. o Then you push the new node to the stack. . When you see a binary operator: 0 You create a new Node for the operator. Then you pop and set the right child. Then you pop and set the left child o Then you push the new node...