Write a program to implement a binary search tree. User will provide the number
ID: 3736958 • Letter: W
Question
Write a program to implement a binary search tree. User will provide the number of nodes in the (size of the) Tree by selecting an input 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. Later he will convert this tree to binary search tree.
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 -> 7
2) Write a program to implement a binary search tree. User provides an input between the ranges of 5 to 30. The program should automatically generate a tree having the nodes between the number 0 to N(User provided input) and display it to user(As we did in last question, each node will have a random number between 5 to 30). Finally, this tree will be converted into binary search tree. Later implement tree traversal techniques. The user should choose the type of traversal and accordingly it should display. You need to display 3 techniques. They are Inorder, Preorder and Postorder.
Explanation / 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()%25 +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.