Write the folllwing program in CPP Programming Language: a) Ask the user to inse

Question

Write the folllwing program in CPP Programming Language:

a) Ask the user to insert the following keys to build a B-tree (order = 5):

3,7,9,23,45,1,5,14,25,24,13,11,8,19,4,31,35,56

b) Display the tree to screen

c) Base on the Searching Algorithm provided below, search the number 31 in the above B-tree, and display the path traversed.

Searching Algorithm Let x be the input search key . Start the searching at the root If we encounter an internal node v, search (linear search or binary search) for x among the keys stored at v If x

Explanation / Answer

#include <iostream>

#include <stdlib.h>

using namespace std;

typedef struct node

{

int data;

struct node* left;

struct node* right;

}BST;

BST* insert(int val) //this function creates a node

{

BST* node = (BST*)malloc(sizeof(BST));

node->data = val;

node->left = NULL;

node->right = NULL;

return node;

}

BST* nodeInsert(BST* root, int val)

{

if(root == NULL)

return insert(val); //if root is null then creates a node

if(val < root->data)

root->left = nodeInsert(root->left, val); //creates node at left subtree if value is less than root

else

root->right = nodeInsert(root->right, val); //creates node at right subtree if value is greater than root

return root;

}

void printInorder(BST* root) //preorder traversal to print tree

{

if(root == NULL) return;

printInorder(root->left);

cout<<root->data <<" ";

printInorder(root->right);

}

int search(BST* root, int val)

{

if (root == NULL)

return 0;

if (root->data == val)

return 1;

if (root->data < val)

return search(root->right, val);

return search(root->left, val);

}

int main()

{

BST* root = NULL;

root = insert(3); //adding root element

nodeInsert(root,7); //adding element to existing tree

nodeInsert(root,9);

nodeInsert(root,23);

nodeInsert(root,45);

nodeInsert(root,1);

nodeInsert(root,5);

nodeInsert(root,14);

nodeInsert(root,25);

nodeInsert(root,24);

nodeInsert(root,13);

nodeInsert(root,11);

nodeInsert(root,8);

nodeInsert(root,19);

nodeInsert(root,4);

nodeInsert(root,31);

nodeInsert(root,35);

nodeInsert(root,56);

cout << "INORDER : ";

printInorder(root);

cout << endl;

if(search(root, 31))

cout << "Found" << endl;

else

cout << "Not found" << endl;

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.