Project #2 Instructions: This is an individual assignment. Answers should be you
ID: 3823441 • Letter: P
Question
Project #2 Instructions: This is an individual assignment. Answers should be your own work. You are expected to code this yourself from scratch by thinking through the requirements and design, then writing the code. However, you may use code from the author's BinarySearchTree. Introduction: In this project you will create a binary search tree. Description: Create a class called MySearchTree. MySearchTree will implement a binary search tree. MySearchTree will be a generic class storing a value of the generic type. It should have the following methods. The methods should all operate on the object making the call (none are static). All of the methods should use recursion (except for main). 10 points a) add Adds a node to the tree containing the passed value. 10 points b) find Returns true if the value passed is in the tree. 10 points c) leafCount Returns the count of all of the leaves in the tree. 10 points d) parentCount Returns the count of all of the parents in the tree. 10 points e) height Returns the height of the tree. 10 points f) isPerfect Returns true if the tree is a perfect tree. (A perfect tree is filled at every level). 10 points g) ancestors Returns the ancestor values of the passed value. 10 points h) inOrderPrint Prints node values using an inorder traversal. 10 points i) preOrderPrint Prints node values using a preorder traversal. 10 points j) Main Demonstrates all of the above methods.
Explanation / Answer
import java.util.Scanner;
class BinarySearchTreeNode {
BinarySearchTreeNode left, right;
int data;
/* Initialize Binary Search Tree Nodes with empty data */
public BinarySearchTreeNode() {
left = null;
right = null;
data = 0;
}
/* Initialize Binary Search Tree Nodes with given data */
public BinarySearchTreeNode(int n) {
left = null;
right = null;
data = n;
}
/* Set left node */
public void setLeft(BinarySearchTreeNode n) {
left = n;
}
/* Set right node */
public void setRight(BinarySearchTreeNode n) {
right = n;
}
/* Get left node */
public BinarySearchTreeNode getLeft() {
return left;
}
/* Get right node */
public BinarySearchTreeNode getRight() {
return right;
}
/* Set data to node */
public void setData(int d) {
data = d;
}
/* Get data from node */
public int getData() {
return data;
}
}
class MySearchTree {
private BinarySearchTreeNode root;
public MySearchTree() {
root = null;
}
/* Insert data */
public void insert(int data) {
root = insert(root, data);
}
/* Insert data recursively */
private BinarySearchTreeNode insert(BinarySearchTreeNode node, int data) {
if (node == null)
node = new BinarySearchTreeNode(data);
else {
if (data <= node.getData())
node.left = insert(node.left, data);
else
node.right = insert(node.right, data);
}
return node;
}
/* Count number of leaf nodes */
public int countLeafNodes() {
return countLeafNodes(root);
}
/* Count number of leaf nodes recursively */
private int countLeafNodes(BinarySearchTreeNode node) {
if (node == null)
return 0;
if (node.left == null && node.right == null) {
return 1;
} else {
return countLeafNodes(node.left) + countLeafNodes(node.right);
}
}
/* Find an element */
public boolean find(int val) {
return find(root, val);
}
/* Find an element recursively */
private boolean find(BinarySearchTreeNode 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;
}
/* Count number of parent nodes */
public int countParentNodes() {
return countParentNodes(root);
}
/* Count number of parent nodes recursively*/
private int countParentNodes(BinarySearchTreeNode node) {
if (node == null) {
return 0;
}
if (node.left == null && node.right == null) {
// not a parent node
return 0;
} else {
return countParentNodes(node.left) + countParentNodes(node.right) + 1;
}
}
}
public class BinarySearchTreeMain {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
MySearchTree bst = new MySearchTree();
System.out.println("Binary Search Tree Test ");
char ch;
do {
System.out.println(" Binary Search Tree Operations ");
System.out.println("1. add ");
System.out.println("2. find");
System.out.println("3. leaf count");
System.out.println("4. parent count");
int choice = scan.nextInt();
switch (choice) {
case 1:
System.out.println("Enter integer element to add");
bst.insert(scan.nextInt());
break;
case 2:
System.out.println("Enter integer element to find");
System.out.println("Result of Find : " + bst.find(scan.nextInt()));
break;
case 3:
System.out.println("Total Leaf count : " + bst.countLeafNodes());
break;
case 4:
System.out.println("Parent Count = " + bst.countParentNodes());
break;
default:
System.out.println("Wrong Entry ");
break;
}
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y' || ch == 'y');
}
}
Only first 4 options are solved with recursion. Description is given in comments.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.