Question: Code to construct a binary search tree using a sorted randomly generated array of integers: import java.io.*; import java.util.*; class BTNode{ private int nodeid; private
Code to construct a binary search tree using a sorted randomly generated array of integers:
import java.io.*;
import java.util.*;
class BTNode{
private int nodeid;
private int data;
private int levelNum;
private BTNode leftChildPtr;
private BTNode rightChildPtr;
public BTNode(){}
public void setNodeId(int id){
nodeid = id;
}
public int getNodeId(){
return nodeid;
}
public void setData(int d){
data = d;
}
public int getData(){
return data;
}
public void setLevelNum(int level){
levelNum = level;
}
public int getLevelNum(){
return levelNum;
}
public void setLeftChildPtr(BTNode ptr){
leftChildPtr = ptr;
}
public void setRightChildPtr(BTNode ptr){
rightChildPtr = ptr;
}
public BTNode getLeftChildPtr(){
return leftChildPtr;
}
public BTNode getRightChildPtr(){
return rightChildPtr;
}
public int getLeftChildID(){
if (leftChildPtr == null)
return -1;
return leftChildPtr.getNodeId();
}
public int getRightChildID(){
if (rightChildPtr == null)
return -1;
return rightChildPtr.getNodeId();
}
}
class BinarySearchTree{
private int numNodes;
private BTNode[] arrayOfBTNodes;
private int rootNodeID;
public BinarySearchTree(int n){
numNodes = n;
arrayOfBTNodes = new BTNode[numNodes];
for (int index = 0; index
arrayOfBTNodes[index] = new BTNode();
arrayOfBTNodes[index].setNodeId(index);
arrayOfBTNodes[index].setLeftChildPtr(null);
arrayOfBTNodes[index].setRightChildPtr(null);
arrayOfBTNodes[index].setLevelNum(-1);
}
}
public void setLeftLink(int upstreamNodeID, int downstreamNodeID){
arrayOfBTNodes[upstreamNodeID].setLeftChildPtr(arrayOfBTNodes[downstreamNodeID]);
}
public void setRightLink(int upstreamNodeID, int downstreamNodeID){
arrayOfBTNodes[upstreamNodeID].setRightChildPtr(arrayOfBTNodes[downstreamNodeID]);
}
public void selectionSort(int array[], int arraySize){
for (int iterationNum = 0; iterationNum
int minIndex = iterationNum;
for (int j = iterationNum+1; j
if (array[j]
minIndex = j;
}
// swap array[minIndex] with array[iterationNum]
int temp = array[minIndex];
array[minIndex] = array[iterationNum];
array[iterationNum] = temp;
}
}
public void constructBSTree(int[] array){
int leftIndex = 0;
int rightIndex = numNodes-1;
int middleIndex = (leftIndex + rightIndex)/2;
rootNodeID = middleIndex;
arrayOfBTNodes[middleIndex].setData(array[middleIndex]);
ChainNodes(array, middleIndex, leftIndex, rightIndex);
}
public void ChainNodes(int[] array, int middleIndex, int leftIndex, int rightIndex){
if (leftIndex
int rootIDLeftSubtree = (leftIndex + middleIndex-1)/2;
setLeftLink(middleIndex, rootIDLeftSubtree);
arrayOfBTNodes[rootIDLeftSubtree].setData(array[rootIDLeftSubtree]);
ChainNodes(array, rootIDLeftSubtree, leftIndex, middleIndex-1);
}
if (rightIndex > middleIndex){
int rootIDRightSubtree = (rightIndex + middleIndex + 1)/2;
setRightLink(middleIndex, rootIDRightSubtree);
arrayOfBTNodes[rootIDRightSubtree].setData(array[rootIDRightSubtree]);
ChainNodes(array, rootIDRightSubtree, middleIndex+1, rightIndex);
}
}
public void printLeafNodes(){
for (int id = 0; id
if (arrayOfBTNodes[id].getLeftChildPtr() == null && arrayOfBTNodes[id].getRightChildPtr() == null)
System.out.print(arrayOfBTNodes[id].getData() + " ");
}
System.out.println();
}
public void InOrderTraversal(int nodeid){
if (nodeid == -1)
return;
InOrderTraversal(arrayOfBTNodes[nodeid].getLeftChildID());
System.out.print(arrayOfBTNodes[nodeid].getData() + " ");
InOrderTraversal(arrayOfBTNodes[nodeid].getRightChildID());
}
public void PrintInOrderTraversal(){
InOrderTraversal(rootNodeID);
System.out.println();
}
}
class BSTRandomArraySortedInputs{
public static void selectionSort(int array[], int arraySize){
for (int iterationNum = 0; iterationNum
int minIndex = iterationNum;
for (int j = iterationNum+1; j
if (array[j]
minIndex = j;
}
// swap array[minIndex] with array[iterationNum]
int temp = array[minIndex];
array[minIndex] = array[iterationNum];
array[iterationNum] = temp;
}
}
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int numElements;
System.out.print("Enter the number of elements: ");
numElements = input.nextInt();
int array[] = new int[numElements];
int maxValue;
System.out.print("Enter the maximum value for an element: ");
maxValue = input.nextInt();
Random randGen = new Random(System.currentTimeMillis());
System.out.print("Array Generated: ");
for (int index = 0; index
array[index] = randGen.nextInt(maxValue);
System.out.print(array[index] +" ");
}
System.out.println();
selectionSort(array, numElements);
BinarySearchTree bsTree = new BinarySearchTree(numElements);
bsTree.constructBSTree(array);
System.out.println("Inorder Traversal: ");
bsTree.PrintInOrderTraversal();
System.out.print("Leaf nodes: ");
bsTree.printLeafNodes();
System.out.println();
}
}
(2) Code to determine the depth (level numbers) of the vertices in a binary tree:
import java.io.*;
import java.util.*;
class BTNode{
private int nodeid;
private int data;
private int levelNum;
private BTNode leftChildPtr;
private BTNode rightChildPtr;
public BTNode(){}
public void setNodeId(int id){
nodeid = id;
}
public int getNodeId(){
return nodeid;
}
public void setData(int d){
data = d;
}
public int getData(){
return data;
}
public void setLevelNum(int level){
levelNum = level;
}
public int getLevelNum(){
return levelNum;
}
public void setLeftChildPtr(BTNode ptr){
leftChildPtr = ptr;
}
public void setRightChildPtr(BTNode ptr){
rightChildPtr = ptr;
}
public BTNode getLeftChildPtr(){
return leftChildPtr;
}
public BTNode getRightChildPtr(){
return rightChildPtr;
}
public int getLeftChildID(){
if (leftChildPtr == null)
return -1;
return leftChildPtr.getNodeId();
}
public int getRightChildID(){
if (rightChildPtr == null)
return -1;
return rightChildPtr.getNodeId();
}
}
class Node{
private int data;
private Node nextNodePtr;
private Node prevNodePtr;
public Node(){}
public void setData(int d){
data = d;
}
public int getData(){
return data;
}
public void setNextNodePtr(Node nodePtr){
nextNodePtr = nodePtr;
}
public Node getNextNodePtr(){
return nextNodePtr;
}
public void setPrevNodePtr(Node nodePtr){
prevNodePtr = nodePtr;
}
public Node getPrevNodePtr(){
return prevNodePtr;
}
}
class Queue{
private Node headPtr;
private Node tailPtr;
public Queue(){
headPtr = new Node();
tailPtr = new Node();
headPtr.setNextNodePtr(null);
tailPtr.setPrevNodePtr(null);
}
public Node getHeadPtr(){
return headPtr;
}
public Node getTailPtr(){
return tailPtr;
}
public boolean isEmpty(){
if (headPtr.getNextNodePtr() == null)
return true;
return false;
}
public void enqueue(int data){
Node newNodePtr = new Node();
newNodePtr.setData(data);
newNodePtr.setNextNodePtr(null);
Node lastNodePtr = tailPtr.getPrevNodePtr();
if (lastNodePtr == null){
headPtr.setNextNodePtr(newNodePtr);
newNodePtr.setPrevNodePtr(null);
}
else{
lastNodePtr.setNextNodePtr(newNodePtr);
newNodePtr.setPrevNodePtr(lastNodePtr);
}
tailPtr.setPrevNodePtr(newNodePtr);
}
public int dequeue(){
Node firstNodePtr = headPtr.getNextNodePtr();
Node nextNodePtr = null;
int poppedData = -100000; //empty queue
if (firstNodePtr != null){
nextNodePtr = firstNodePtr.getNextNodePtr();
poppedData = firstNodePtr.getData();
}
else
return poppedData;
if (nextNodePtr != null){
nextNodePtr.setPrevNodePtr(null);
headPtr.setNextNodePtr(nextNodePtr);
}
else{
headPtr.setNextNodePtr(null);
tailPtr.setPrevNodePtr(null);
}
return poppedData;
}
public int peek(){
Node firstNodePtr = headPtr.getNextNodePtr();
if (firstNodePtr != null)
return firstNodePtr.getData();
else
return -100000; //empty queue
}
}
class BinaryTree{
private int numNodes;
private int rootNodeID;
private BTNode arrayOfBTNodes[];
public BinaryTree(int n){
numNodes = n;
arrayOfBTNodes = new BTNode[numNodes];
rootNodeID = 0;
for (int id = 0; id
arrayOfBTNodes[id] = new BTNode();
arrayOfBTNodes[id].setNodeId(id);
arrayOfBTNodes[id].setLevelNum(-1);
arrayOfBTNodes[id].setLeftChildPtr(null);
arrayOfBTNodes[id].setRightChildPtr(null);
}
}
public void setLeftLink(int upstreamNodeID, int downstreamNodeID){
arrayOfBTNodes[upstreamNodeID].setLeftChildPtr(arrayOfBTNodes[downstreamNodeID]);
}
public void setRightLink(int upstreamNodeID, int downstreamNodeID){
arrayOfBTNodes[upstreamNodeID].setRightChildPtr(arrayOfBTNodes[downstreamNodeID]);
}
public void printLeafNodes(){
for (int id = 0; id
if (arrayOfBTNodes[id].getLeftChildPtr() == null && arrayOfBTNodes[id].getRightChildPtr() == null)
System.out.print(id + " ");
}
System.out.println();
}
public boolean isLeafNode(int nodeid){
if (arrayOfBTNodes[nodeid].getLeftChildPtr() == null && arrayOfBTNodes[nodeid].getRightChildPtr() == null)
return true;
return false;
}
public int getNodeHeight(int nodeid){
if (nodeid == -1 || isLeafNode(nodeid) )
return 0;
int leftChildID = arrayOfBTNodes[nodeid].getLeftChildID(); // -1 if not exist
int rightChildID = arrayOfBTNodes[nodeid].getRightChildID(); // -1 if not exist
return Math.max(getNodeHeight(leftChildID), getNodeHeight(rightChildID)) + 1;
}
public int getTreeHeight(){
return getNodeHeight(0);
}
public void assignLevelNumbers(){
Queue queue = new Queue();
queue.enqueue(rootNodeID);
arrayOfBTNodes[rootNodeID].setLevelNum(0);
while (!queue.isEmpty()){
int firstNodeInQueue = queue.dequeue();
int leftChildID = arrayOfBTNodes[firstNodeInQueue].getLeftChildID();
if (leftChildID != -1){
queue.enqueue(leftChildID);
arrayOfBTNodes[leftChildID].setLevelNum(arrayOfBTNodes[firstNodeInQueue].getLevelNum()+1);
}
int rightChildID = arrayOfBTNodes[firstNodeInQueue].getRightChildID();
if (rightChildID != -1){
queue.enqueue(rightChildID);
arrayOfBTNodes[rightChildID].setLevelNum(arrayOfBTNodes[firstNodeInQueue].getLevelNum()+1);
}
}
}
public int getDepth(int nodeid){
return arrayOfBTNodes[nodeid].getLevelNum();
}
}
class BinaryTreeDepth{
public static void main(String[] args){
try{
Scanner input = new Scanner(System.in);
String filename;
System.out.print("Enter a file name: ");
filename = input.next();
int numNodes;
System.out.print("Enter number of nodes: ");
numNodes = input.nextInt();
BinaryTree binaryTree = new BinaryTree(numNodes);
FileReader fr = new FileReader(filename);
BufferedReader br = new BufferedReader(fr);
String line = null;
while ( (line = br.readLine()) != null){
StringTokenizer stk = new StringTokenizer(line, ",: ");
int upstreamNodeID = Integer.parseInt(stk.nextToken());
int childIndex = 0;
while (stk.hasMoreTokens()){
int downstreamNodeID = Integer.parseInt(stk.nextToken());
if (childIndex == 0 && downstreamNodeID != -1)
binaryTree.setLeftLink(upstreamNodeID, downstreamNodeID);
if (childIndex == 1 && downstreamNodeID != -1)
binaryTree.setRightLink(upstreamNodeID, downstreamNodeID);
childIndex++;
}
}
binaryTree.assignLevelNumbers();
for (int id = 0; id
System.out.println("Depth of Node " + id + " : " + binaryTree.getDepth(id) );
}
catch(Exception e){e.printStackTrace();}
}
}
You are given the following code: (1) Code to construct a binary search tree using a sorted randomly generated array of integers (2) Code to determine the depth (level numbers) of the vertices in a binary tree Add a member function assignLevelNumbers() to the Binary Search Tree class to determine the level numbers of the vertices in a binary search tree (start Breadth First Search with the rootNodelD, which is considered to be at level 0) Add a member function getLevelNumber(int nodeid) in the Binary Search Tree class that in turn calls the getLevelNum( ) function on the BST node object corresponding to the 'nodeid' and returns the level number of node identified by its id. In the main function, first call the assignLevelNumbers() function on the object of class Binary Search Tree before determining the number of comparisons for successful search Successful search: During the lecture, we saw that the number of comparisons for the successful search of a key in a binary search tree (BST) is one more than the level number of the vertex representing the key in the BST. In the main function, write a for loop that will go through the individual vertices and extract their level numbers using the getLevelNumber(int nodeid) function called on an object of the class Binary Search Tree. Use these level numbers of the vertices to calculate the average number of comparisons for a successful search and print the same. Test your code with the following values for the number of elements in the array. 10, 100, 1000, 10000 The maximum value for an element in each case is 2500 As part of the output, you need not print the contents of the array. Just print the average number of comparisons for a successful search for each of the above four values for the number of elements in the array
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help