Please Write in C++ Construct Binary Search Tree by Array Executive Summary: A b

Question

Please Write in C++

Construct Binary Search Tree by Array Executive Summary: A binary search tree is a binary tree in which every node satisfies the following: the key of every node in the left subtree is smaller than the key of this node e the key of every node in the right subtree is larger than the key of this node It is possible to construct BST with pointers. A single dimension array is also good enough to construct a BST. One example is like following: 5 index 3) (8 5 3814-1 9 Staring with array index “1” For any node, to find its parent's index: If the node's index is even number -- index/2 If the node's index is odd number (index-1)/2 For any node, to find its left side child's index - index *2 For any node, to find its right side child's index -- index*2+ 1 Project Objective: in completing this project, you will Understand the details of BST, including search, insert, delete, find max, find min Familiar with the links between array and BST

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;

}

BST* deleteNode(BST* root, int val)

{

if (root == NULL)

return root; //if root is null return null

if (val < root->data)

root->left = deleteNode(root->left, val); //if search val is less than root, then traverse left subtree

else if (val > root->data)

root->right = deleteNode(root->right, val); //if search val is greater than root, then traverse right subtree

else

{

if (root->left == NULL) //swaps the root->right with current node

{

BST *temp = root->right;

free(root);

return temp;

}

else if (root->right == NULL) //swaps root->left with current node

{

BST *temp = root->left;

free(root);

return temp;

}

BST* temp = root->right;

while (temp->left != NULL)

temp = temp->left;

root->data = temp->data;

root->right = deleteNode(root->right, temp->data);

}

return root;

}

int findMin(BST* root)

{

BST *temp = root;

while(temp->left)

temp = temp->left;

return temp->data;

}

int findMax(BST* root)

{

BST *temp = root;

while(temp->right)

temp = temp->right;

return temp->data;

}

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(5); //adding root element

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

nodeInsert(root,3);

nodeInsert(root,1);

nodeInsert(root,4);

nodeInsert(root,9);

nodeInsert(root,18);

nodeInsert(root,20);

nodeInsert(root,19);

nodeInsert(root,2);

cout << "INORDER : ";

printInorder(root);

cout << endl;

int min = findMin(root);

int max = findMax(root);

cout << "Minimum element is : " << min << endl;

cout << "Maximum element is : " << max << endl;

if(search(root, 3))

cout << "Found" << endl;

else

cout << "Not found" << endl;

if(search(root, 18))

cout << "Found" << endl;

else

cout << "Not found" << endl;

if(search(root, 19))

cout << "Found" << endl;

else

cout << "Not found" << endl;

root = deleteNode(root, 19);

printInorder(root);

cout << endl;

root = deleteNode(root, 2);

printInorder(root);

cout << endl;

root = deleteNode(root, 8);

printInorder(root);

cout << endl;

root = deleteNode(root, 3);

printInorder(root);

cout << endl;

root = deleteNode(root, 5);

printInorder(root);

cout << endl;

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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