Write a Java program to implement a binary search tree. User must provide the nu
ID: 3702574 • Letter: W
Question
Write a Java program to implement a binary search tree. User must provide the number of nodes in the Tree (which is the size of tree) by selecting a number between 10 to 30. This program will automatically generate a binary tree of specified size by assigning random numbers between 5 to 30 to Each of its node and display final tree to user. Then after you will convert this tree to binary search tree.
For instance if i Choose 10 for size please show me the result similar look like this.
Sample Output: Enter the number of nodes in the tree: 5 The Tree before conversion of BST is 10-2 10 ->7 2->8 2-4 After converting the tree to BST 8-10 8-4 4- 2 4-7Explanation / Answer
#include <queue>
#include <iostream>
#include <queue>
using namespace std;
/* A binary tree node structure */
struct node
{
int data;
struct node *left;
struct node *right;
};
/* Utility function to create a new Binary Tree node */
struct node* newNode (int data)
{
struct node *temp = new struct node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
/*function to insert element in binary tree */
void insert(struct node* temp, int key)
{
queue <struct node*> q;
q.push(temp);
// Do level order traversal until we find
// an empty place.
while (!q.empty()) {
struct node* temp = q.front();
q.pop();
if (!temp->left) {
temp->left = newNode(key);
break;
} else
q.push(temp->left);
if (!temp->right) {
temp->right = newNode(key);
break;
} else
q.push(temp->right);
}
}
/* A helper function that stores inorder traversal of a tree rooted
with node */
void storeInorder (struct node* node, int inorder[], int *index_ptr)
{
// Base Case
if (node == NULL)
return;
/* first store the left subtree */
storeInorder (node->left, inorder, index_ptr);
/* Copy the root's data */
inorder[*index_ptr] = node->data;
(*index_ptr)++; // increase index for next entry
/* finally store the right subtree */
storeInorder (node->right, inorder, index_ptr);
}
/* A helper function to count nodes in a Binary Tree */
int countNodes (struct node* root)
{
if (root == NULL)
return 0;
return countNodes (root->left) +
countNodes (root->right) + 1;
}
// Following function is needed for library function qsort()
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
/* A helper function that copies contents of arr[] to Binary Tree.
This functon basically does Inorder traversal of Binary Tree and
one by one copy arr[] elements to Binary Tree nodes */
void arrayToBST (int *arr, struct node* root, int *index_ptr)
{
// Base Case
if (root == NULL)
return;
/* first update the left subtree */
arrayToBST (arr, root->left, index_ptr);
/* Now update root's data and increment index */
root->data = arr[*index_ptr];
(*index_ptr)++;
/* finally update the right subtree */
arrayToBST (arr, root->right, index_ptr);
}
// This function converts a given Binary Tree to BST
void binaryTreeToBST (struct node *root)
{
// base case: tree is empty
if(root == NULL)
return;
/* Count the number of nodes in Binary Tree so that
we know the size of temporary array to be created */
int n = countNodes (root);
// Create a temp array arr[] and store inorder traversal of tree in arr[]
int *arr = new int[n];
int i = 0;
storeInorder (root, arr, &i);
// Sort the array using library function for quick sort
qsort (arr, n, sizeof(arr[0]), compare);
// Copy array elements back to Binary Tree
i = 0;
arrayToBST (arr, root, &i);
// delete dynamically allocated memory to avoid meory leak
delete [] arr;
}
/* Utility function to print inorder traversal of Binary Tree */
void printInorder (struct node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder (node->left);
/* then print the data of node */
cout<<"-> "<< node->data;
/* now recur on right child */
printInorder (node->right);
}
void printpreorder (struct node* node)
{
if (node == NULL)
return;
/* then print the data of node */
cout<<"-> "<< node->data;
/* first recur on left child */
printpreorder (node->left);
/* now recur on right child */
printpreorder (node->right);
}
void printpostorder (struct node* node)
{
if (node == NULL)
return;
/* now recur on right child */
printpostorder (node->right);
/* first recur on left child */
printpostorder (node->left);
/* then print the data of node */
cout<<"-> "<< node->data;
}
/* Driver function to test above functions */
int main()
{
struct node *root = NULL;
int n=10;// number of nodes
std::cout <<" Enter number of nodes in range 10 ,30 "<< std::endl;
cin>>n;
for(int i=0; i<n;i++){
int num=rand()%30 +5;
if(i==0){
root = newNode(num);
continue;}
insert(root,num);
}
cout<<endl;
std::cout << "Inorder Traversal of binary tree" << std::endl;
printInorder (root);
// convert Binary Tree to BST
binaryTreeToBST (root);
cout<<endl;
cout<<"Following is preOrder Traversal of the converted BST: ";
printpreorder (root);
cout<<endl;
cout<<"Following is Inorder Traversal of the converted BST: ";
printInorder (root);
cout<<endl;
cout<<"Following is postorder Traversal of the converted BST: ";
printpostorder (root);
cout<<endl;
return 0;
}
Output:-
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.