Hello, I am taking Data Structures & Algorithms in Java this semester and we wer
ID: 3706016 • Letter: H
Question
Hello,
I am taking Data Structures & Algorithms in Java this semester and we were just introduced to Trees & Binary Trees. We were assigned an assignment a few days ago and I need a lot of help with it. I have provided the assignment sheet, the code I have done so far, and a hint from the professor regarding the assignment.
Thank you!
Assignment Sheet:
Comment from the professor:
When you solve the question 1 -- nodeCount(), you should define a recursive method to count how many nodes in a binary search tree. DO NOT directly return the numItems. Even though the BST class provided has a data member "numItems" for tracking the number of nodes in the tree, we have known that this data member is not necessary in Binary Tree or Binary Search Tree class. Thus, I would like you to write a method to find out how many nodes in a binary search tree suppose that there is no data member defined for the number of nodes in the tree.
Sample Code:
public class IntTreeNode {
int key; //store this node's key value
IntTreeNode leftChild; //store the reference
// to this node's left child
IntTreeNode rightChild; //store the reference
// to this node's right child
//constructor
public IntTreeNode(int key)
{
this.key = key;
this.leftChild = null;
this.rightChild = null;
}
public IntTreeNode(int key, IntTreeNode left, IntTreeNode right)
{
this.key = key;
this.leftChild = left;
this.rightChild = right;
}
//display itself
public void display()
{
System.out.print("(" + key + ")");
}
//remove a node from the subtree
public IntTreeNode remove(int delKey, IntTreeNode parent)
{
if (delKey < this.key){
if (leftChild != null)
return leftChild.remove(delKey, this);
else
return null;
}
else if (delKey > this.key) {
if (rightChild != null)
return rightChild.remove(delKey, this);
else
return null;
}
else { //find the node
if (leftChild != null && rightChild != null) {
IntTreeNode min = rightChild.minRightSubTree();
this.key = min.key;
return rightChild.remove(this.key, this);
}
else if (this == parent.leftChild) {
parent.leftChild = (leftChild != null) ? leftChild : rightChild;
return this;
}
else if (this == parent.rightChild) {
parent.rightChild = (leftChild != null) ? leftChild : rightChild;
return this;
}
}
return null;
}
//find a minimum value in the right subtree
public IntTreeNode minRightSubTree()
{
if (this.leftChild == null)
return this;
else
return leftChild.minRightSubTree();
}
}
public class IntBinarySearchTree {
private IntTreeNode root; //first node of the tree
private int numItems; //number of nodes in the tree
//constructor
public IntBinarySearchTree()
{
root = null;
numItems = 0;
}
//getters
public IntTreeNode getRoot() {
return root;
}
public int getNumItems() {
return numItems;
}
//check whether this binary tree is a binary search tree
public boolean isBST()
{
return isBST(root);
}
//helper method: recursive check isBST
private boolean isBST(IntTreeNode root)
{
if(root == null)
return true;
if( isSubTreeLess(root.leftChild, root.key) &&
isSubTreeGreater(root.rightChild, root.key) &&
isBST (root.leftChild) &&
isBST (root.rightChild) )
return true;
else
return false;
}
//helper for isBST(IntTreeNode)
private boolean isSubTreeLess(IntTreeNode subRoot, int value)
{
if(subRoot == null)
return true;
if(subRoot.key < value &&
isSubTreeLess(subRoot.leftChild, value) &&
isSubTreeLess(subRoot.rightChild, value))
return true;
else
return false;
}
//helper for isBST(IntTreeNode)
private boolean isSubTreeGreater(IntTreeNode subRoot, int value)
{
if(subRoot == null)
return true;
if(subRoot.key >= value &&
isSubTreeGreater(subRoot.leftChild, value) &&
isSubTreeGreater(subRoot.rightChild, value))
return true;
else
return false;
}
//insert a node into this binary search tree
public void addBST(int newKey)
{
root = addBST(newKey, root);
numItems++;
}
//helper method: recursive insert
private IntTreeNode addBST(int newKey, IntTreeNode subTreeRoot)
{
if (subTreeRoot==null)
{
//create a new node
subTreeRoot = new IntTreeNode(newKey);
}
else if (newKey < subTreeRoot.key)
subTreeRoot.leftChild = addBST(newKey, subTreeRoot.leftChild);
else
subTreeRoot.rightChild = addBST(newKey, subTreeRoot.rightChild);
return subTreeRoot;
}
//search a node in this binary search tree
public IntTreeNode inBST(int searchKey)
{
return inBST(searchKey, root);
}
//helper method: recursive search
private IntTreeNode inBST(int searchKey, IntTreeNode subTreeRoot)
{
if (subTreeRoot == null)
{
return null;
}
else
{
if (searchKey == subTreeRoot.key)
return subTreeRoot;
else if (searchKey < subTreeRoot.key)
{
return inBST(searchKey, subTreeRoot.leftChild);
}
else
{
return inBST(searchKey, subTreeRoot.rightChild);
}
}
}
//traverse this binary search tree in different ways
public void traverse(int traverseType)
{
switch(traverseType)
{
case 1: System.out.print(" Preorder traversal: ");
preOrder(root);
break;
case 2: System.out.print(" Inorder traversal: ");
inOrder(root);
break;
case 3: System.out.print(" Postorder traversal: ");
postOrder(root);
break;
}
System.out.println();
}
//helper method: recursive preorder traverse
private void preOrder(IntTreeNode subTreeRoot)
{
if(subTreeRoot != null)
{
subTreeRoot.display();
preOrder(subTreeRoot.leftChild);
preOrder(subTreeRoot.rightChild);
}
}
//helper method: recursive inorder traverse
private void inOrder(IntTreeNode subTreeRoot)
{
if(subTreeRoot != null)
{
inOrder(subTreeRoot.leftChild);
subTreeRoot.display();
inOrder(subTreeRoot.rightChild);
}
}
//helper method: recursive postorder traverse
private void postOrder(IntTreeNode subTreeRoot)
{
if(subTreeRoot != null)
{
postOrder(subTreeRoot.leftChild);
postOrder(subTreeRoot.rightChild);
subTreeRoot.display();
}
}
//remove a node from this binary search tree
public boolean remove(int delKey)
{
if (root == null)
return false;
else {
if (delKey == root.key) {
IntTreeNode auxRoot = new IntTreeNode(0); //dummy root
auxRoot.leftChild = root;
IntTreeNode removedNode = root.remove(delKey, auxRoot);
root = auxRoot.leftChild;
if (removedNode != null) {
removedNode = null;
numItems--;
return true;
}
else
return false;
}
else {
IntTreeNode removedNode = root.remove(delKey, null);
if (removedNode != null) {
removedNode = null;
numItems--;
return true;
}
else
return false;
}
}
}
}
public class TestBinarySearchTree {
public static void main(String[] args) {
// TODO Auto-generated method stub
IntBinarySearchTree myBST = new IntBinarySearchTree();
//Test insert method
myBST.addBST(35);
myBST.addBST(18);
myBST.addBST(9);
myBST.addBST(24);
myBST.addBST(20);
myBST.addBST(64);
myBST.addBST(86);
myBST.addBST(41);
myBST.addBST(30);
//Test traverse method
myBST.traverse(2);
//Test search method
myBST.inBST(30).display();
//Test remove method
if(myBST.remove(18))
{
myBST.traverse(2);
}
else
{
System.out.println("Cannot find the key!");
}
}
}
1. Add a method nodeCount () to the IntBinarysearchTree class, which returns the number of nodes in the binary search tree. Add some code in the main) of TestBinarySearchTree.java to test these methods 2. Add a method leavesCount () to the IntBinarySearchTree class, which returns the number of leaves in the binary search tree. Add some code in the main() of TestBinarySearchTree.java to test these methods 3. Add a method heightCount () to the IntBinarysearchTree class, which returns the height of the binary search tree. Add some code in the main() of TestBinarySearchTree.java to test these methods For example, if we start with an empty binary search tree (BST) and insert the sequence of values: 50, 70, 30, 80, 34, 32, 9, 47, and 18. Then we get the BST: 50 70 34 80 32 47 Calling nodecount () on this BST should return 9 Calling leavesCount () on this BST should return 4 Calling heightcount ) on this BST should return 4 Submission Rule: If you do not follow the submission rule for this assignment and following assignments, penalty will be given. All your code should be in one project called "CS237 Assignment 5_your name". The code related to all three problems should be in ONE package called "problems123", which has updated IntBinarySearchTree.java and updated TestBinarySearchTree.java. Each java file should begin with a "header comment" with a brief description of what the file is for, your name, the date you made the last change, and updates you have made. For exampleExplanation / Answer
public class IntBinarySearchTree {
private IntTreeNode root; //first node of the tree
private int numItems; //number of nodes in the tree
//constructor
public IntBinarySearchTree()
{
root = null;
numItems = 0;
}
//getters
public IntTreeNode getRoot() {
return root;
}
public int getNumItems() {
return numItems;
}
//check whether this binary tree is a binary search tree
public boolean isBST()
{
return isBST(root);
}
//helper method: recursive check isBST
private boolean isBST(IntTreeNode root)
{
if(root == null)
return true;
if( isSubTreeLess(root.leftChild, root.key) &&
isSubTreeGreater(root.rightChild, root.key) &&
isBST (root.leftChild) &&
isBST (root.rightChild) )
return true;
else
return false;
}
//helper for isBST(IntTreeNode)
private boolean isSubTreeLess(IntTreeNode subRoot, int value)
{
if(subRoot == null)
return true;
if(subRoot.key < value &&
isSubTreeLess(subRoot.leftChild, value) &&
isSubTreeLess(subRoot.rightChild, value))
return true;
else
return false;
}
//helper for isBST(IntTreeNode)
private boolean isSubTreeGreater(IntTreeNode subRoot, int value)
{
if(subRoot == null)
return true;
if(subRoot.key >= value &&
isSubTreeGreater(subRoot.leftChild, value) &&
isSubTreeGreater(subRoot.rightChild, value))
return true;
else
return false;
}
//insert a node into this binary search tree
public void addBST(int newKey)
{
root = addBST(newKey, root);
numItems++;
}
//helper method: recursive insert
private IntTreeNode addBST(int newKey, IntTreeNode subTreeRoot)
{
if (subTreeRoot==null)
{
//create a new node
subTreeRoot = new IntTreeNode(newKey);
}
else if (newKey < subTreeRoot.key)
subTreeRoot.leftChild = addBST(newKey, subTreeRoot.leftChild);
else
subTreeRoot.rightChild = addBST(newKey, subTreeRoot.rightChild);
return subTreeRoot;
}
//search a node in this binary search tree
public IntTreeNode inBST(int searchKey)
{
return inBST(searchKey, root);
}
//helper method: recursive search
private IntTreeNode inBST(int searchKey, IntTreeNode subTreeRoot)
{
if (subTreeRoot == null)
{
return null;
}
else
{
if (searchKey == subTreeRoot.key)
return subTreeRoot;
else if (searchKey < subTreeRoot.key)
{
return inBST(searchKey, subTreeRoot.leftChild);
}
else
{
return inBST(searchKey, subTreeRoot.rightChild);
}
}
}
public int nodeCount(IntTreeNode subTreeRoot){
int count = 1;
if (subTreeRoot == null)
return 0;
else
{
count += nodeCount(subTreeRoot.leftChild);
count += nodeCount(subTreeRoot.rightChild);
return count;
}
}
int heightCount(IntTreeNode subTreeRoot)
{
if (subTreeRoot == null)
return 0;
else
{
int leftCount = heightCount(subTreeRoot.leftChild);
int rightCount = heightCount(subTreeRoot.rightChild);
// To return larger count
if (leftCount > rightCount)
return (leftCount + 1);
else
return (rightCount + 1);
}
}
public int leavesCount(IntTreeNode subTreeRoot)
{
if (subTreeRoot == null)
return 0;
if (subTreeRoot.leftChild == null && subTreeRoot.rightChild == null)
return 1;
else
return leavesCount(subTreeRoot.leftChild) + leavesCount(subTreeRoot.rightChild);
}
//traverse this binary search tree in different ways
public void traverse(int traverseType)
{
switch(traverseType)
{
case 1: System.out.print(" Preorder traversal: ");
preOrder(root);
break;
case 2: System.out.print(" Inorder traversal: ");
inOrder(root);
break;
case 3: System.out.print(" Postorder traversal: ");
postOrder(root);
break;
}
System.out.println();
}
//helper method: recursive preorder traverse
private void preOrder(IntTreeNode subTreeRoot)
{
if(subTreeRoot != null)
{
subTreeRoot.display();
preOrder(subTreeRoot.leftChild);
preOrder(subTreeRoot.rightChild);
}
}
//helper method: recursive inorder traverse
private void inOrder(IntTreeNode subTreeRoot)
{
if(subTreeRoot != null)
{
inOrder(subTreeRoot.leftChild);
subTreeRoot.display();
inOrder(subTreeRoot.rightChild);
}
}
//helper method: recursive postorder traverse
private void postOrder(IntTreeNode subTreeRoot)
{
if(subTreeRoot != null)
{
postOrder(subTreeRoot.leftChild);
postOrder(subTreeRoot.rightChild);
subTreeRoot.display();
}
}
//remove a node from this binary search tree
public boolean remove(int delKey)
{
if (root == null)
return false;
else {
if (delKey == root.key) {
IntTreeNode auxRoot = new IntTreeNode(0); //dummy root
auxRoot.leftChild = root;
IntTreeNode removedNode = root.remove(delKey, auxRoot);
root = auxRoot.leftChild;
if (removedNode != null) {
removedNode = null;
numItems--;
return true;
}
else
return false;
}
else {
IntTreeNode removedNode = root.remove(delKey, null);
if (removedNode != null) {
removedNode = null;
numItems--;
return true;
}
else
return false;
}
}
}
}
/*************************************
*
* Output
Inorder traversal: (9)(18)(20)(24)(30)(35)(41)(64)(86)
(30)Cannot find the key!
Number of Nodes: 9
Number of leaf Nodes: 5
Height of BST: 4
********************************************/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.