*************************************************PLEASE USE AN ARRAY AND NOT A P

ID: 3919580 • Letter: #

Question

*************************************************PLEASE USE AN ARRAY AND NOT A POINTER*****************************************************

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 lefi 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: 3) (8 =|538| 1 4 -119 1) (4 9 Staring with array index "l” For any node, to find its parent's index: If the node's index is even numberindex/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<conio.h>

#include<stdlib.h>

using namespace std;

void Insert(int,int );

void Delete(int);

void Print_BST(int);

int Find_max();

int Find_min();

int Search(int);

int Search1(int,int);

int BST[1000],t=1,s,x,i;

//max size of BST 1000

main()

{

int ch,y;

for(i=0;i<=1000;i++)

BST[i]=-1;

while(1)

{

cout <<" 1.Insert 2.DELETE 3.Print_BST 4.Search 5.Find_max 6.Find_min 7.EXIT Enter your choice:";

cin >> ch;

switch(ch)

{

case 1:

cout <<"Enter element to Insert:";

cin >> ch;

Insert(1,ch);

break;

case 2:

cout <<"Enterelement to delete:";

cin >>x;

y=Search(1);

if(y!=-1) Delete(y);

else cout<<"no such element in BST";

break;

case 3:

Print_BST(1);

break;

case 4:

cout <<"Enter the element to Search:";

cin >> x;

y=Search(1);

if(y == -1) cout <<"no such element in BST";

else cout <<x << "is in" <<y <<"position";

break;

case 5:

cout<<"Max is:"<<Find_max()<<endl;

break;

case 6:

cout<<"Min is:"<<Find_min()<<endl;

break;

case 7:

exit(0);

}

void Insert(int s,int ch )

{

int x;

if(t==1)

{

BST[t++]=ch;

return;

}

x=Search1(s,ch);

if(BST[x]>ch)

BST[2*x]=ch;

else

BST[2*x+1]=ch;

t++;

}

void Delete(int x)

{

if( BST[2*x]==-1 && BST[2*x+1]==-1)

BST[x]=-1;

else if(BST[2*x]==-1)

{ BST[x]=BST[2*x+1];

BST[2*x+1]=-1;

}

else if(BST[2*x+1]==-1)

{ BST[x]=BST[2*x];

BST[2*x]=-1;

}

else

{

BST[x]=BST[2*x];

Delete(2*x);

}

t--;

}

int Search(int s)

{

if(t==1)

{

cout <<"no element in BST";

return -1;

}

if(BST[s]==-1)

return BST[s];

if(BST[s]>x)

Search(2*s);

else if(BST[s]<x)

Search(2*s+1);

else

return s;

}

void Print_BST(int s)

{

if(t==1)

{cout <<"no element in BST:";

return;}

for(int i=1;i<1000;i++)

if(BST[i]==-1)

cout <<" ";

else cout <<BST[i];

return ;

}

int Search1(int s,int ch)

{

if(t==1)

{

cout <<"no element in BST";

return -1;

}

if(BST[s]==-1)

return s/2;

if(BST[s] > ch)

Search1(2*s,ch);

else Search1(2*s+1,ch);

}

int Find_min()

{

if(t==1)

{

cout <<"no element in BST";

return -1;

}

int i=0;

int min = 1000000;

while(i<1000)

{

if(BST[i]!=-1)

if(BST[i]<min)

min = BST[i];

// cout<<BST[i]<<endl;

i++;

}

return min;//returning min

}

int Find_max()

{

if(t==1)

{

cout <<"no element in BST";

return -1;

}

int i=0;

int max = BST[0];

while(i<1000)

{

if(BST[i]!=-1)

if(BST[i]>max)max = BST[i];

i++;

}

return max;//returning min

}

output:

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:1
Enter element to Insert:5

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:1
Enter element to Insert:8

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:1
Enter element to Insert:3

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:1
Enter element to Insert:1

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:1
Enter element to Insert:4

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:1
Enter element to Insert:9

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:1
Enter element to Insert:18

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:1
Enter element to Insert:20

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:1
Enter element to Insert:19

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:1
Enter element to Insert:2

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:3
53814 9 2 18 20 19

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:5
Max is:20

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:6
Min is:1

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:4
Enter the element to Search:3
3is in2position

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:4
Enter the element to Search:18
18is in15position

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:4
Enter the element to Search:19
19is in62position

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:2
Enterelement to delete:19

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:2
Enterelement to delete:2

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:2
Enterelement to delete:8

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:2
Enterelement to delete:3

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:2
Enterelement to delete:5

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:3
149 18 20

1.Insert
2.DELETE
3.Print_BST
4.Search
5.Find_max
6.Find_min
7.EXIT
Enter your choice:7

Process exited normally.
Press any key to continue . . .

Navigate

****************************************************Personal, Dependency exempti

************************************************I HAVE TO USE APPLET, NOT JFRAME

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

*************************************************PLEASE USE AN ARRAY AND NOT A P

Question

Explanation / Answer

Related Questions

Navigate