Do not use any pointers. Executive Summary: A binary search tree is a binary tre

Question

Do not use any pointers.

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
? 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:

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

Detailed Specification:
Write six basic functions for the BST: Insert, Delete, Search, Find_max,
Find_min, and Print_BST
1. Search(x): Find out the index that stores element x using binary search tree
mechanism. Print out all the elements in the search path.
2. Find_max( ): Find and print maximum value in BST
3. Find_min( ): Find and print minimum value in BST
4. Print_BST( ): Print out the BST structure in the form of array with index.
5. Insert(x): Insert a value element x into BST
6. (BOUNS) Delete(x): Delete element x in BST including ALL 3 situations
we discussed

After you finished the all functions, following are the things you need to carry out:
1. Insert(5)
2. Insert(8)
3. Insert(3)
4. Insert(1)
5. Insert(4)
6. Insert(9)
7. Insert(18)
8. Insert(20)
9. Insert(19)
10. Insert(2)
11. Perform Print_BST( )
12. Perform Find_max( )
13. Perform Find_min( )
14. Perform Search(3) in the BST
15. Perform Search(18) in the BST
16. Perform Search(19) in the BST
17. Delete(19) in the BST, perform Print_BST( ) (BOUNS)
18. Delete(2) in the BST, perform Print_BST( ) (BOUNS)
19. Delete(8) in the BST, perform Print_BST( ) (BOUNS)
20. Delete(3) in the BST, perform Print_BST( ) (BOUNS)
21. Delete(5) in the BST, perform Print_BST( ) (BOUNS)
(p.s. Although the input values are provided, your code should be able to handle random
input values.)

Do not use any pointers.

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 D
• Subjects

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