I have post this question litterally now 6 times. Please don\'t add a portion wh
ID: 3920114 • Letter: I
Question
I have post this question litterally now 6 times. Please don't add a portion where the user has to input a choice PLEASE.
Write a program to perform the following C++ (don't use switch statements):
1) To store integers, implement a dynamic binary search tree with the insert, find, and delete operations.
2) Modify the dynamic binary search tree to embed an ordered doubly-linked list running through the tree, including modifying the insert and delete operations.
3) Implement a second find method which uses the ordered doubly-linked list information.
4) Modify the original find operations and the new find operation to count the number of data comparisons.
5) Use alternating_order.txt to fill the modified tree.
4154
8144
1674
6540
1257
6221
5876
9877
2512
6876
1701
6593
1150
6199
1326
6357
1789
6626
1883
6638
1275
6296
5492
9465
5271
8848
2293
6853
3139
7557
2525
6960
5054
8730
5457
9464
3044
7529
1108
6176
2278
6837
1565
6438
5542
9486
5797
9756
2742
7200
6157
9924
1197
6202
2886
7367
2583
7141
5397
9365
4841
8608
2979
7456
4467
8495
1916
6688
1894
6684
3429
7676
5330
8863
4328
8344
5244
8826
1068
6167
4959
8701
6147
9909
4870
8655
4839
8597
5751
9642
3411
7655
1631
6517
5616
9624
1419
6366
5122
8781
4456
8450
2759
7271
2946
7378
4371
8402
2714
7172
3627
7730
5696
9625
1573
6500
5373
9268
4646
8512
5765
9728
2308
6860
5097
8757
3420
7669
3926
8036
4146
8089
4176
8227
2947
7448
3760
7867
2497
6875
2536
6996
5605
9604
5811
9814
2884
7355
1998
6713
4274
8268
3717
7775
4106
8077
3030
7481
3509
7711
search_values.txt
7369
6960
9877
1900
6859
8399
9268
2662
8863
9758
4839
6152
8597
5751
4618
9483
7448
5054
4284
9728
8089
9604
2359
7172
8144
9814
1753
8512
8757
7170
7775
6357
2553
6167
2293
8528
5761
5765
9697
5543
2747
2950
3696
7271
5615
7441
7244
5492
5330
8716
8655
1566
8268
7367
1275
2947
8088
5538
1573
4404
9625
2714
7847
1022
7621
5373
3115
6299
9909
4959
8605
5119
5616
9527
4106
4870
1605
1883
2278
4328
6438
7200
2886
6147
8701
6573
7774
6717
1375
8670
8826
5094
6685
6948
4463
5696
1998
9239
3956
6860
8344
6698
1894
3926
5418
8745
5605
5647
6202
5255
3750
1264
1150
5362
2884
5879
7933
9756
7711
5542
7378
4847
7670
1197
1326
8227
8036
3578
6540
6655
6176
7676
3040
2742
1631
1701
4164
2536
2291
6961
7668
2512
2759
7730
3030
3411
1152
7123
7669
5797
8093
5389
7529
3509
2535
4230
3218
9902
7655
7183
8443
4467
7456
5271
1257
8077
6204
4371
1419
6500
3026
9398
6249
2736
2497
5122
7338
9821
8786
9642
3139
1674
1791
5848
2303
6875
8620
1068
5304
5728
6713
3414
6593
1885
6481
6517
1458
8051
4146
6876
4999
8730
9464
1789
8191
8835
2979
4154
9330
2525
5799
4150
7355
8848
7141
8495
3627
6996
9969
5481
8855
4841
8266
5811
4456
8463
6684
8781
5097
3875
1986
6626
7557
6688
6165
7702
9486
8608
9620
2941
6157
6638
7517
6840
1137
6199
8331
4349
6366
3420
7364
8770
6221
6863
6365
5397
1108
7481
3481
6621
1201
4274
5457
2946
9624
4885
4646
6180
6296
9915
3044
8502
1565
1916
9465
4824
8402
4176
4107
5155
1297
6428
3717
5876
7541
2814
7867
3429
3760
2270
5244
2583
6837
6514
9365
6853
6530
2308
8450
9924
7)Report the following: total number of comparisons, average number of comparisons for a successful search, and the average number of comparisons for an unsuccessful search.
PLEASE DON'T DO THE FOLLOWING:
while(1)
{
cout<<" 1.Insert The Element";
cout<<" 2.Search The Element";
cout<<" 3.Print Tree in inorder:";
cout<<" 4.Exit";
cout<<" Select your choice :";
cin>>option;
switch (option)
Explanation / Answer
#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
struct treeNode
{
int data;
treeNode *left;
treeNode *right;
};
treeNode Insert(treeNode node,int data)
{
if(node==NULL)
{
treeNode *temp;
temp=new treeNode;
//temp = (treeNode *)malloc(sizeof(treeNode));
temp -> data = data;
temp -> left = temp -> right = NULL;
return temp;
}
if(data >(node->data))
{
node->right = Insert(node->right,data);
}
else if(data < (node->data))
{
node->left = Insert(node->left,data);
}
/ Else there is nothing to do as the data is already in the tree. /
return node;
}
treeNode Find(treeNode node, int data)
{
if(node==NULL)
{
/ Element is not found /
return NULL;
}
if(data > node->data)
{
/ Search in the right sub tree. /
return Find(node->right,data);
}
else if(data < node->data)
{
/ Search in the left sub tree. /
return Find(node->left,data);
}
else
{
/ Element Found /
return node;
}
void order(treeNode *node)
{
if(node==NULL)
{
return;
}
cout<<node->data<<" ";
}
}
int main()
{
treeNode *root = NULL,*temp;
int ch;
//clrscr();
while(1)
{
cout<<" 1.Insert 2.Search 3.Print in order .Exit ";
cout<<"Enter ur choice:";
cin>>ch;
switch(ch)
{
case 1:
cout<<" Enter element to be insert:";
cin>>ch;
root = Insert(root, ch);
cout<<" Elements in BST are:";
Inorder(root);
break;
case 2:
cout<<" Enter element to be searched:";
cin>>ch;
temp = Find(root,ch);
if(temp==NULL)
{
cout<<"Element is not foundn";
}
case 3:
cout<<" Enter element :";
{
cout<<"Element in order";
}
else
{
cout<<"Element "<<temp->data<<" is Found ";
}
break;
case 4:
exit(0);
break;
default:
cout<<" Enter correct choice:";
break;
}
}
return 0;
}