In Java: 10. ) Main Create a class called MySearchTree. -It will implement a bin

Question

In Java:

10.) Main

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 parent Count 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

create a class named inasrSearchTree and copy the code

import java.util.Scanner;

class BSTNode
{
BSTNode left, right;
int data;

/* Constructor */
public BSTNode()
{
left = null;
right = null;
data = 0;
}
/* Constructor */
public BSTNode(int n)
{
left = null;
right = null;
data = n;
}
/* Function to set left node */
public void setLeft(BSTNode n)
{
left = n;
}
/* Function to set right node */
public void setRight(BSTNode n)
{
right = n;
}
/* Function to get left node */
public BSTNode getLeft()
{
return left;
}
/* Function to get right node */
public BSTNode getRight()
{
return right;
}
/* Function to set data to node */
public void setData(int d)
{
data = d;
}
/* Function to get data from node */
public int getData()
{
return data;
}   
}
/* Class BST */
class BinarySearchTree
{
private BSTNode root;

/* Constructor */
public BinarySearchTree()
{
root = null;
}
/* Function to check if tree is empty */
public boolean isEmpty()
{
return root == null;
}
/* Functions to insert data */
public void add(int data)
{
root = add(root, data);
}
/* Function to insert data recursively */
private BSTNode add(BSTNode node, int data)
{
if (node == null)
node = new BSTNode(data);
else
{
if (data <= node.getData())
node.left = add(node.left, data);
else
node.right = add(node.right, data);
}
return node;
}
/* Functions to count number of leafs */
public int leafCount()
{
return leafCount(root);
}
/* Function to count number of nodes recursively */
private int leafCount(BSTNode r)
{
if (r == null)
return 0;
else
{
int l = 1;
l += leafCount(r.getLeft());
l += leafCount(r.getRight());
return l;
}
}
/* Functions to search for an element */
public boolean find(int val)
{
return find(root, val);
}
/* Function to search for an element recursively */
private boolean find(BSTNode r, int val)
{
boolean found = false;
while ((r != null) && !found)
{
int rval = r.getData();
if (val < rval)
r = r.getLeft();
else if (val > rval)
r = r.getRight();
else
{
found = true;
break;
}
found = find(r, val);
}
return found;
}
/* Function for inorder traversal */
public void inorderPrint()
{
   inorderPrint(root);
}
private void inorderPrint(BSTNode r)
{
if (r != null)
{
   inorderPrint(r.getLeft());
System.out.print(r.getData() +" ");
inorderPrint(r.getRight());
}
}
/* Function for preorder traversal */
public void preorderPrint()
{
   preorderPrint(root);
}
private void preorderPrint(BSTNode r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorderPrint(r.getLeft());   
preorderPrint(r.getRight());
}
}

private int parentcount () {
   return parentcount(root);
}
private int parentcount (BSTNode node) {
if(node == null) {
return 0;
}
if (node.getLeft() != null && node.getRight() != null){
return 1;
}
return parentcount(node.left)+parentcount(node.right);
}
public int findHeight(){
return findHeight(root);
  
}
private int findHeight(BSTNode Node){
int heightLeft = 0;
int heightRight = 0;
if(Node.getLeft()!=null)
heightLeft = findHeight(Node.getLeft());
if(Node.getRight()!=null)
heightRight = findHeight(Node.getRight());
if(heightLeft > heightRight){
return heightLeft+1;
}
else{
return heightRight+1;
}
}
public static void main(String[] args)
{   
Scanner scan = new Scanner(System.in);
/* Creating object of BST */
BinarySearchTree bst = new BinarySearchTree();
System.out.println("Binary Search Tree Test ");
System.out.println("1");
char ch;
bst.add( 1 );
bst.add( 3 );
bst.add( 4 );
bst.add( 2 );
bst.add( 5 );
bst.add( 6 );
bst.add( 7 );
bst.add( 8 );   
System.out.println("Search result : "+ bst.find( 11 ));
System.out.println("leafCount = "+ bst.leafCount());
System.out.println("parentcount = "+ bst.parentcount());
System.out.println("findHeight = "+ bst.findHeight());
  
System.out.print(" Pre order : ");
bst.preorderPrint();
System.out.print(" In order : ");
bst.inorderPrint();   
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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