The definition for binary search tree should be the one used in class (which is different from that adopted by the suggested-book authors). ► Class definition: Suggested-book definition: A BST is a binary tree that (if not empty) also follows two storage rules regarding its nodes’ items: A BST is a binary tree that (if not empty) also follows two storage rules regarding its nodes’ items: ♯ For any node n of the tree, every item in n’s left subtree (LST), if not empty, is less than the item in n ♯ For any node n of the tree, every item in n’s left subtree (LST), if not empty, is less than or equal the item in n ♯ For any node n of the tree, every item in n’s right subtree (RST), if not empty, is greater than the item in n ♯ For any node n of the tree, every item in n’s right subtree (RST), if not empty, is greater than the item in n ● bst_insert must be iterative (NOT recursive). ● bst_remove and bst_remove_max must use the algorithm described by the suggested book authors, appropriately adapted for the difference in tree definition above In btNode.h: provide prototypes for bst_insert, bst_remove and bst_remove_max. ● In btNode.cpp: provide definition (implementation) for bst_insert, bst_remove and bst_remove_max. Here is what the test output is suppose to look like: ============================== test case 1 of 990000 attempt to remove 5 values below: (sequential order) -2 8 -4 0 1 (value-sort order) -4 -2 0 1 8 from 8 values below: -8 -7 -6 -2 -1 0 1 2 gives (with 3 values successfully removed) -8 -7 -6 -1 2 ============================== test case 2 of 990000 attempt to remove 7 values below: (sequential order) 8 -3 -5 -4 5 6 4 (value-sort order) -5 -4 -3 4 5 6 8 from 6 values below: -8 -5 -4 -3 -2 3 gives (with 3 values successfully removed) -8 -2 3 ============================== test case 3 of 990000 attempt to remove 5 values below: (sequential order) 4 -6 -4 -1 6 (value-sort order) -6 -4 -1 4 6 from 11 values below: -8 -7 -6 -5 -4 -2 -1 0 5 6 7 gives (with 4 values successfully removed) -8 -7 -5 -2 0 5 7 ============================== test case 4 of 990000 attempt to remove 1 values below: (sequential order) 8 (value-sort order) 8 from 12 values below: -9 -8 -7 -6 -4 -3 -1 1 3 4 5 9 gives (with 0 values successfully removed) -9 -8 -7 -6 -4 -3 -1 1 3 4 5 9 ============================== test case 5 of 990000 attempt to remove 8 values below: (sequential order) 4 -6 4 2 -9 7 -7 5 (value-sort order) -9 -7 -6 2 4 4 5 7 from 9 values below: -8 -5 -4 -2 1 2 3 8 9 gives (with 1 values successfully removed) -8 -5 -4 -2 1 3 8 9 ============================== test case 66000 of 990000 attempt to remove 3 values below: (sequential order) 1 -1 7 (value-sort order) -1 1 7 from 4 values below: -5 -3 0 8 gives (with 0 values successfully removed) -5 -3 0 8 ============================== test case 132000 of 990000 attempt to remove 8 val
The definition for binary search tree should be the one used in class (which is different from that adopted by the suggested-book authors). ► Class definition: Suggested-book definition: A BST is a binary tree that (if not empty) also follows two storage rules regarding its nodes’ items: A BST is a binary tree that (if not empty) also follows two storage rules regarding its nodes’ items: ♯ For any node n of the tree, every item in n’s left subtree (LST), if not empty, is less than the item in n ♯ For any node n of the tree, every item in n’s left subtree (LST), if not empty, is less than or equal the item in n ♯ For any node n of the tree, every item in n’s right subtree (RST), if not empty, is greater than the item in n ♯ For any node n of the tree, every item in n’s right subtree (RST), if not empty, is greater than the item in n ● bst_insert must be iterative (NOT recursive). ● bst_remove and bst_remove_max must use the algorithm described by the suggested book authors, appropriately adapted for the difference in tree definition above In btNode.h: provide prototypes for bst_insert, bst_remove and bst_remove_max. ● In btNode.cpp: provide definition (implementation) for bst_insert, bst_remove and bst_remove_max. Here is what the test output is suppose to look like: ============================== test case 1 of 990000 attempt to remove 5 values below: (sequential order) -2 8 -4 0 1 (value-sort order) -4 -2 0 1 8 from 8 values below: -8 -7 -6 -2 -1 0 1 2 gives (with 3 values successfully removed) -8 -7 -6 -1 2 ============================== test case 2 of 990000 attempt to remove 7 values below: (sequential order) 8 -3 -5 -4 5 6 4 (value-sort order) -5 -4 -3 4 5 6 8 from 6 values below: -8 -5 -4 -3 -2 3 gives (with 3 values successfully removed) -8 -2 3 ============================== test case 3 of 990000 attempt to remove 5 values below: (sequential order) 4 -6 -4 -1 6 (value-sort order) -6 -4 -1 4 6 from 11 values below: -8 -7 -6 -5 -4 -2 -1 0 5 6 7 gives (with 4 values successfully removed) -8 -7 -5 -2 0 5 7 ============================== test case 4 of 990000 attempt to remove 1 values below: (sequential order) 8 (value-sort order) 8 from 12 values below: -9 -8 -7 -6 -4 -3 -1 1 3 4 5 9 gives (with 0 values successfully removed) -9 -8 -7 -6 -4 -3 -1 1 3 4 5 9 ============================== test case 5 of 990000 attempt to remove 8 values below: (sequential order) 4 -6 4 2 -9 7 -7 5 (value-sort order) -9 -7 -6 2 4 4 5 7 from 9 values below: -8 -5 -4 -2 1 2 3 8 9 gives (with 1 values successfully removed) -8 -5 -4 -2 1 3 8 9 ============================== test case 66000 of 990000 attempt to remove 3 values below: (sequential order) 1 -1 7 (value-sort order) -1 1 7 from 4 values below: -5 -3 0 8 gives (with 0 values successfully removed) -5 -3 0 8 ============================== test case 132000 of 990000 attempt to remove 8 val
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
|
| In btNode.h: provide prototypes for bst_insert, bst_remove and bst_remove_max. |
| ● | In btNode.cpp: provide definition (implementation) for bst_insert, bst_remove and bst_remove_max. |
Here is what the test output is suppose to look like:
==============================
test case 1 of 990000
attempt to remove 5 values below:
(sequential order) -2 8 -4 0 1
(value-sort order) -4 -2 0 1 8
from 8 values below:
-8 -7 -6 -2 -1 0 1 2
gives (with 3 values successfully removed)
-8 -7 -6 -1 2
==============================
test case 2 of 990000
attempt to remove 7 values below:
(sequential order) 8 -3 -5 -4 5 6 4
(value-sort order) -5 -4 -3 4 5 6 8
from 6 values below:
-8 -5 -4 -3 -2 3
gives (with 3 values successfully removed)
-8 -2 3
==============================
test case 3 of 990000
attempt to remove 5 values below:
(sequential order) 4 -6 -4 -1 6
(value-sort order) -6 -4 -1 4 6
from 11 values below:
-8 -7 -6 -5 -4 -2 -1 0 5 6 7
gives (with 4 values successfully removed)
-8 -7 -5 -2 0 5 7
==============================
test case 4 of 990000
attempt to remove 1 values below:
(sequential order) 8
(value-sort order) 8
from 12 values below:
-9 -8 -7 -6 -4 -3 -1 1 3 4 5 9
gives (with 0 values successfully removed)
-9 -8 -7 -6 -4 -3 -1 1 3 4 5 9
==============================
test case 5 of 990000
attempt to remove 8 values below:
(sequential order) 4 -6 4 2 -9 7 -7 5
(value-sort order) -9 -7 -6 2 4 4 5 7
from 9 values below:
-8 -5 -4 -2 1 2 3 8 9
gives (with 1 values successfully removed)
-8 -5 -4 -2 1 3 8 9
==============================
test case 66000 of 990000
attempt to remove 3 values below:
(sequential order) 1 -1 7
(value-sort order) -1 1 7
from 4 values below:
-5 -3 0 8
gives (with 0 values successfully removed)
-5 -3 0 8
==============================
test case 132000 of 990000
attempt to remove 8 values below:
(sequential order) 7 6 -3 5 -1 -4 2 1
(value-sort order) -4 -3 -1 1 2 5 6 7
from 13 values below:
-8 -7 -6 -5 -4 -3 -2 -1 0 1 4 6 7
gives (with 6 values successfully removed)
-8 -7 -6 -5 -2 0 4
![[*]btNode.h X
12345678981234567898122342525278293812345拓劲89812BU456F8498152够弘556刃8 59 =
10
ddddddd□ENN~~~ ~ ~ NO
20
30
40
च च च
50
#ifndef BT_NODE_H
#define BT_NODE_H
struct btNode
{
};
// pre:
int data;
btNode* left;
btNode* right;
// post: The binary search tree has been traversed in-order and the data
values are written (as they are encountered) to portArray in
increasing positional order starting from the first element
portToArrayInOrder (btNode* bst_root, int* portArray);
portToArrayInOrder
Aux (btNode* bst_root, int* portArray, int& portIndex);
void
void
//
// pre: (none)
// post: dynamic memory of all the nodes of the tree rooted at root has been
freed up (returned back to heap/freestore) and the tree is now empty
(root pointer contains the null address)
void tree_clear (btNode*& root);
// pre: (none)
// post: # of nodes contained in tree rooted at root is returned
int bst_size(btNode* bst_root);
//
// pre:
//
bst_root is root pointer of a binary search tree (may be 0 for
empty tree) and portArray has the base address of an array Large
enough to hold all the data items in the binary search tree
bst_root is root pointer of a binary search tree (may be for
empty tree)
If no node in the binary search tree has data equals insInt, a
node with data insInt has been created and inserted at the proper
Location in the tree to maintain binary search tree property.
If a node with data equals insInt is found, the node's data field
has been overwritten with insInt; no new node has been created.
(Latter case seems odd but it's to mimick update of key-associated
data that exists in more general/real-world situations.)
write prototype for bst_insert here
bst_root is root pointer of a binary search tree (may be for
empty tree)
If remInt was in the tree, then remInt has been removed, bst_root
now points to the root of the new (smaller) binary search tree,
and the function returns true. Otherwise, if remInt was not in the
tree, then the tree is unchanged, and the function returns false.
post:
// pre:
// post:
// write prototype for bst_remove here
// pre:
// post:
60 #endif
bst_root is root pointer of a non-empty binary search tree
The Largest item in the binary search tree has been removed, and
bst_root now points to the root of the new (smaller) binary search
tree. The reference parameter, removed, has been set to a copy of
the removed item.
// write prototype for bst_remove_max here](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fb51b654d-3a22-424d-90a5-d3d04b635cc6%2F8488883b-da78-4706-8a60-e1bf5836331a%2Fzzba9g5_processed.png&w=3840&q=75)
Transcribed Image Text:[*]btNode.h X
12345678981234567898122342525278293812345拓劲89812BU456F8498152够弘556刃8 59 =
10
ddddddd□ENN~~~ ~ ~ NO
20
30
40
च च च
50
#ifndef BT_NODE_H
#define BT_NODE_H
struct btNode
{
};
// pre:
int data;
btNode* left;
btNode* right;
// post: The binary search tree has been traversed in-order and the data
values are written (as they are encountered) to portArray in
increasing positional order starting from the first element
portToArrayInOrder (btNode* bst_root, int* portArray);
portToArrayInOrder
Aux (btNode* bst_root, int* portArray, int& portIndex);
void
void
//
// pre: (none)
// post: dynamic memory of all the nodes of the tree rooted at root has been
freed up (returned back to heap/freestore) and the tree is now empty
(root pointer contains the null address)
void tree_clear (btNode*& root);
// pre: (none)
// post: # of nodes contained in tree rooted at root is returned
int bst_size(btNode* bst_root);
//
// pre:
//
bst_root is root pointer of a binary search tree (may be 0 for
empty tree) and portArray has the base address of an array Large
enough to hold all the data items in the binary search tree
bst_root is root pointer of a binary search tree (may be for
empty tree)
If no node in the binary search tree has data equals insInt, a
node with data insInt has been created and inserted at the proper
Location in the tree to maintain binary search tree property.
If a node with data equals insInt is found, the node's data field
has been overwritten with insInt; no new node has been created.
(Latter case seems odd but it's to mimick update of key-associated
data that exists in more general/real-world situations.)
write prototype for bst_insert here
bst_root is root pointer of a binary search tree (may be for
empty tree)
If remInt was in the tree, then remInt has been removed, bst_root
now points to the root of the new (smaller) binary search tree,
and the function returns true. Otherwise, if remInt was not in the
tree, then the tree is unchanged, and the function returns false.
post:
// pre:
// post:
// write prototype for bst_remove here
// pre:
// post:
60 #endif
bst_root is root pointer of a non-empty binary search tree
The Largest item in the binary search tree has been removed, and
bst_root now points to the root of the new (smaller) binary search
tree. The reference parameter, removed, has been set to a copy of
the removed item.
// write prototype for bst_remove_max here
![1
Hamin A GỌNng
2
3
// write definition for bst_insert here
// write definition for bst_remove here
7 // write definition for bst_remove_max here
4
5
6
8
9
10 void portToArrayInOrder (btNode* bst_root, int* portArray)
11 {
12
13
14
15 }
16
17
18
19
20
21
22
23
24
25
22
#include "btNode.h"
26
27
28
29
30
31
32
33
34
35
36
37
38
39
if (bst_root == 0) return;
int portIndex = 0;
portToArrayInOrderAux (bst_root, portArray, portIndex);
void portToArrayInOrderAux (btNode* bst_root, int* portArray, int& portIndex)
{
if (bst_root == 0) return;
portToArrayInOrderAux (bst_root->left, portArray, portIndex);
portArray[port Index++] = bst_root->data;
portToArrayInOrderAux(bst_root->right, portArray, portIndex);
void tree_clear (btNode* & root)
{
if (root == 0) return;
tree_clear (root->left);
tree_clear (root->right);
delete root;
root = 0;
int bst_size(btNode* bst_root)
{
if (bst_root == 0) return 0;
return 1 + bst_size(bst_root->left) + bst_size(bst_root->right);](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fb51b654d-3a22-424d-90a5-d3d04b635cc6%2F8488883b-da78-4706-8a60-e1bf5836331a%2F37wl2s_processed.png&w=3840&q=75)
Transcribed Image Text:1
Hamin A GỌNng
2
3
// write definition for bst_insert here
// write definition for bst_remove here
7 // write definition for bst_remove_max here
4
5
6
8
9
10 void portToArrayInOrder (btNode* bst_root, int* portArray)
11 {
12
13
14
15 }
16
17
18
19
20
21
22
23
24
25
22
#include "btNode.h"
26
27
28
29
30
31
32
33
34
35
36
37
38
39
if (bst_root == 0) return;
int portIndex = 0;
portToArrayInOrderAux (bst_root, portArray, portIndex);
void portToArrayInOrderAux (btNode* bst_root, int* portArray, int& portIndex)
{
if (bst_root == 0) return;
portToArrayInOrderAux (bst_root->left, portArray, portIndex);
portArray[port Index++] = bst_root->data;
portToArrayInOrderAux(bst_root->right, portArray, portIndex);
void tree_clear (btNode* & root)
{
if (root == 0) return;
tree_clear (root->left);
tree_clear (root->right);
delete root;
root = 0;
int bst_size(btNode* bst_root)
{
if (bst_root == 0) return 0;
return 1 + bst_size(bst_root->left) + bst_size(bst_root->right);
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 5 steps with 1 images
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY