You are to design a Java program to perform the following tasks: * read a sequen
ID: 652978 • Letter: Y
Question
You are to design a Java program to perform the following tasks:
* read a sequence of integers, 60, 20, 100, 35, 15, 200, 75,
* 150, 6, 17, and 40, and construct a binary search tree,
called T1.
* use the inorder procedure to print the nodes
* count the number of leaf nodes of T1.
* swap the nodes of T1 to construct a new tree, called T2.
* use the postorder function to print the nodes of T2.
* use the function compare to see if T1 is identical to T2.
* read another sequence of integers, 60, 100, 20, 15, 35, 75,
200, 6, 17,
40, 150, and construct another tree, called T3.
* use the function Compare to see if T1 is identical to T3.
* Delete the node containing 15 from the tree T3
* Use the inorder to display the nodes after deletion
* Display the 5th node of the tree T3 using INORDER
You may need to design the following functions:
1. Function Build: read a sequence of integers and construct a binary search tree.
2. Function Inorder: based on the BST tree built, conduct the "INORDER" traversal and print the value of each node when visited.
3. Function Postorder: based on the BST tree built, conduct the "POSTORDER" traversal and print the value of each node when visited.
4. Function Count: write a function that counts the number of leaf nodes in the tree and return the count. Do not use unnecessary local variables and parameters.
5. Function Swap: swap the left and right children(subtree) recursively of every node of the given tree.
6. Function Compare: return TRUE if the two given trees are identical.
7. Using appropriate messages to explain each output described above.
Comments:
You are not allowed to use the built_in tree class available in Java.
Submit your program and the output which should show every function in your program works.
Explanation / Answer
Program code:
/* Class BSTNode */
public class BSearchTreeNode
{
BSearchTreeNode left, right;
int data;
/* Constructor */
public BSearchTreeNode()
{
left = null;
right = null;
data = 0;
}
/* Constructor */
public BSearchTreeNode(int d)
{
left = null;
right = null;
data = d;
}
/* Function to set left node */
public void setLeft(BSearchTreeNode n)
{
left = n;
}
/* Function to set right node */
public void setRight(BSearchTreeNode n)
{
right = n;
}
/* Function to get left node */
public BSearchTreeNode getLeft()
{
return left;
}
/* Function to get right node */
public BSearchTreeNode 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 */
public class BSearchTree
{
private BSearchTreeNode root;
int count=0;
// Constructor
public BSearchTree()
{
root = null;
}
// isEmpty function to check the tree is empty or not
public boolean isEmpty()
{
return root == null;
}
// insert function
public void insert(int data)
{
root = insert(root, data);
}
// recursive insert function
private BSearchTreeNode insert(BSearchTreeNode node, int data)
{
if (node == null)
node = new BSearchTreeNode(data);
else
{
if (data < node.getData())
node.left = insert(node.left, data);
else
node.right = insert(node.right, data);
}
return node;
}
// delete function
public void delete(int k)
{
if (isEmpty())
System.out.println("Tree Empty");
else if (search(k) == false)
System.out.println("Sorry " + k + " is not present");
else
{
root = delete(root, k);
System.out.println(k + " deleted from the tree");
}
}
private BSearchTreeNode delete(BSearchTreeNode root, int k)
{
BSearchTreeNode p1node, p2node, pnode;
if (root.getData() == k)
{
System.out.println("True");
BSearchTreeNode lt, rt;
lt = root.getLeft();
rt = root.getRight();
if (lt == null && rt == null)
return null;
else if (lt == null)
{
p1node = rt;
return p1node;
} else if (rt == null)
{
p1node = lt;
return p1node;
} else
{
p2node = rt;
p1node = rt;
while (p1node.getLeft() != null)
p1node = p1node.getLeft();
p1node.setLeft(lt);
return p2node;
}
}
else if (k > root.getData())
{
pnode = delete(root.getLeft(), k);
root.setLeft(pnode);
}
else
{
pnode = delete(root.getRight(), k);
root.setRight(pnode);
}
return root;
}
// countNodes function to count the nodes
public int countNodes()
{
return countNodes(root);
}
// countNodes function by passing the root
private int countNodes(BSearchTreeNode r)
{
if (r == null)
return 0;
else
{
int count = 1;
count += countNodes(r.getLeft());
count += countNodes(r.getRight());
return count;
}
}
// search function
public boolean search(int val)
{
return search(root, val);
}
// search function to search for an element recursively
private boolean search(BSearchTreeNode 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 = search(r, val);
}
return found;
}
// inorder traversal function
public void inorder()
{
inorder(root);
}
// inorder traversal function recursively
private void inorder(BSearchTreeNode r)
{
if (r != null)
{
inorder(r.getLeft());
System.out.print(r.getData() + " ");
inorder(r.getRight());
}
}
public BSearchTreeNode getNode()
{
return root;
}
// preorder traversal function
public void preorder()
{
preorder(root);
}
// preorder traversal function recursively
private void preorder(BSearchTreeNode r)
{
if (r != null)
{
System.out.print(r.getData() + " ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
// preorder traversal function
public void postorder()
{
postorder(root);
}
// postorder traversal function recursively
private void postorder(BSearchTreeNode r)
{
if (r != null)
{
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() + " ");
}
}
// swap the elements in the tree
void swap()
{
swap(root);
}
void swap(BSearchTreeNode root)
{
if (root == null)
return;
else
{
BSearchTreeNode temp;
// construct the subtrees
swap(root.left);
swap(root.right);
// swap the pointers in this node
temp = root.left;
root.left = root.right;
root.right = temp;
}
}
public boolean compare(BSearchTree bst1, BSearchTree bst2)
{
boolean flag = compare(bst1.getNode(), bst2.getNode());
return flag;
}
public boolean compare(BSearchTreeNode root1, BSearchTreeNode root2)
{
boolean rootEqual = false;
boolean lEqual = false;
boolean rEqual = false;
if (root1 != null && root2 != null)
{
rootEqual = (root1.getData() == (root2.getData()));
if (root1.getLeft() != null && root2.getLeft() != null)
{
// compare the left
lEqual = compare(root1.getLeft(), root2.getLeft());
} else if (root1.getLeft() == null && root2.getLeft() == null)
{
lEqual = true;
}
if (root1.getRight() != null && root2.getRight() != null)
{
// compare the right
rEqual = compare(root1.getRight(), root2.getRight());
} else if (root1.getRight() == null && root2.getRight() == null)
{
rEqual = true;
}
return (rootEqual && lEqual && rEqual);
}
return false;
}
void displayInorder(int nodePosition)
{
int count = 0;
displayInorder(root, nodePosition);
}
// inorder traversal function recursively
private void displayInorder(BSearchTreeNode r, int position)
{
if (r != null)
{
if (count == position)
{
System.out.println("The value at " + position + " is: " + r.getData());
return;
}
displayInorder(r.getLeft(), position);
count++;
displayInorder(r.getRight(), position);
}
}
}
import java.util.Scanner;
import java.util.*;
public class BinarySearchTreeImpleIntegers
{
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
int values[];
int size;
int delValue;
BSearchTree T1 = new BSearchTree();
BSearchTree T2 = new BSearchTree();
System.out.println("Enter the number of elements you want insert: ");
size = in.nextInt();
values = new int[size];
System.out.println("Enter the elements: ");
// Prompt the user to insert elements
for (int i = 0; i < values.length; i++)
{
System.out.print(" Enter the value at " + (1 + i) + ": ");
values[i] = in.nextInt();
}
System.out.println();
// insert the elements into Tree T1
for (int i = 0; i < values.length; i++)
{
T1.insert(values[i]);
}
// call the inorder order function
System.out.println(" The list of list of values in inorder is: ");
T1.inorder();
// call the count method to print the number of nodes
// in the Tree T1
System.out.println(" Count the number of leaf nodes in T1: " + T1.countNodes());
T1.swap();
System.out.println("Swap the elements in the Tree T1 and assing it to T2");
// copy the swapped tree into new Tree T2
T2 = T1;
// Trace back the tree T1 to its normal position.
T1.swap();
// call the post order function on the
System.out.println(" The list of values in T2 tree is: ");
T2.postorder();
// call the post order method
System.out.println(" The list of names in postorder is: ");
T1.preorder();
System.out.print(" T1 is identical to T2: ");
if (T1.compare(T1, T2))
System.out.println("true");
else
System.out.println("false");
BSearchTree T3 = new BSearchTree();
System.out.println("Enter the number of elements you want insert: ");
size = in.nextInt();
values = new int[size];
System.out.println("Enter the elements: ");
// Prompt the user to insert elements
for (int i = 0; i < values.length; i++)
{
System.out.print(" Enter the value at " + (1 + i) + ": ");
values[i] = in.nextInt();
}
System.out.println();
// insert the elements into Tree T1
for (int i = 0; i < values.length; i++)
{
T3.insert(values[i]);
}
System.out.print(" T1 is identical to T3: ");
if (T1.compare(T1, T3))
System.out.println("true");
else
System.out.println("false");
// call the displayInorder to display the specified position
T3.displayInorder(5);
// delete 15 from the list
/*
* System.out.println(" Enter an element to delete:");
* delValue=in.nextInt(); T3.delete(delValue);
*/
// call the inorder order function
System.out.println(" The list of list of values in inorder is: ");
T3.inorder();
}
}
Sample Output:
Enter the number of elements you want insert:
11
Enter the elements:
Enter the value at 1: 60
Enter the value at 2: 20
Enter the value at 3: 100
Enter the value at 4: 35
Enter the value at 5: 15
Enter the value at 6: 200
Enter the value at 7: 75
Enter the value at 8: 150
Enter the value at 9: 6
Enter the value at 10: 17
Enter the value at 11: 40
The list of list of values in inorder is:
6 15 17 20 35 40 60 75 100 150 200
Count the number of leaf nodes in T1: 11
Swap the elements in the Tree T1 and assing it to T2
The list of values in T2 tree is:
6 17 15 40 35 20 75 150 200 100 60
The list of names in postorder are:
60 20 15 6 17 35 40 100 75 200 150
T1 is identical to T2: true
Enter the number of elements you want insert:
11
Enter the elements:
Enter the value at 1: 60
Enter the value at 2: 100
Enter the value at 3: 20
Enter the value at 4: 15
Enter the value at 5: 35
Enter the value at 6: 75
Enter the value at 7: 200
Enter the value at 8: 6
Enter the value at 9: 17
Enter the value at 10: 40
Enter the value at 11: 150
T1 is identical to T3: true
The value at 5 is: 40
The list of values in inorder is:
6 15 17 20 35 40 60 75 100 150 200
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.