In Java: In Java: -binary-search-tree-task *Create a class called MySearchTree.
ID: 3844781 • Letter: I
Question
In Java:
In Java: -binary-search-tree-task *Create a class called MySearchTree. -It will implement a binary search tree. -It will be a generic class storing a value of the generic type. The following methods will be implemented: *The methods should all operate on the object making the call (none are static) * *All of the methods should use recursion (except for main) * add Adds a node to the tree containing the passed value. find Returns true if the value passed is in the tree. leafCount Returns the count of all of the leaves in the tree. parentCount Returns the count of all of the parents in the tree. height Returns the height of the tree. isPerfect Returns true if the tree is a perfect tree. (A perfect tree is filled at every level). ancestors Returns the ancestor values of the passed value inOrderPrint Prints node values using an inorder traversal. preOrderPrint Prints node values using a preorder traversal.Explanation / Answer
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.LinkedList;
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Sam
* @param <T>
*/
public class BST<T> {
class Node {
T data;
Node left;
Node right;
Node(T data){
this.data = data;
left= right = null;
}
}
Node root;
BST(){
root = null;
}
public void add(T data){
Comparable comparable = (Comparable)data;
Node newNode = new Node(data);
if (root == null)
root = newNode;
else {
Node tempNode = root;
Node tempParent = null;
while (tempNode!=null){
tempParent = tempNode;
if (comparable.compareTo(tempNode.data)<0)
tempNode = tempNode.left;
else
tempNode = tempNode.right;
}
if (comparable.compareTo(tempNode.data)<0)
tempNode.left = newNode;
else
tempNode.right = newNode;
}
}
public boolean find(T data){
Comparable comparable = (Comparable)data;
if (root == null)
return false;
else {
Node tempNode = root;
while (tempNode!=null){
if (tempNode.data.equals(data))
return true;
if (comparable.compareTo(tempNode.data)<0)
tempNode = tempNode.left;
else
tempNode = tempNode.right;
}
}
return false;
}
public int leafCount(){
return leafCount(root);
}
private int leafCount(Node tree){
if(tree == null)
return 0;
if (tree.left == null && tree.right == null)
return 1;
return leafCount(tree.left)+ leafCount(tree.left);
}
public int parentCount(){
return parentCount(root);
}
private int parentCount(Node tree){
if(tree == null)
return 0;
if (tree.left == null && tree.right == null)
return 0;
return parentCount(tree.left)+ parentCount(tree.left)+1;
}
public int height(){
return height(root);
}
private int height(Node tree){
if(tree == null)
return 0;
return Math.max(height(tree.left), height(tree.right))+1;
}
public boolean isPerfect(){
return (Math.pow(2,height())-1) == (leafCount()+parentCount());
}
public java.util.List<T> ansestors(T data){
java.util.List<T> list = new LinkedList<>();
Comparable comparable = (Comparable)data;
if (root == null)
return null;
else {
Node tempNode = root;
while (tempNode!=null){
if (tempNode.data.equals(data))
return list;
list.add(tempNode.data);
if (comparable.compareTo(tempNode.data)<0)
tempNode = tempNode.left;
else
tempNode = tempNode.right;
}
}
return null;
}
public void printInOrder(){
System.out.print("| ");
printInOrder(root);
}
private void printInOrder(Node tree){
printInOrder(tree.left);
System.out.print(tree.data.toString()+" | ");
printInOrder(tree.right);
}
public void printPreOrder(){
System.out.print("| ");
printPreOrder(root);
}
private void printPreOrder(Node tree){
System.out.print(tree.data.toString()+" | ");
printPreOrder(tree.left);
printPreOrder(tree.right);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.