The definition for binary search tree should be the one used in class Class definition:                                                                       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 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  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_ma #ifndef BT_NODE_H #define BT_NODE_H struct btNode {    int data;    btNode* left;    btNode* right; }; // 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 // 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 void portToArrayInOrder(btNode* bst_root, int* portArray); void portToArrayInOrderAux(btNode* bst_root, int* portArray, int& portIndex); // 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) // post: 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 // pre:  bst_root is root pointer of a binary search tree (may be 0 for //       empty tree) // post: 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. // write prototype for bst_remove here // pre:  bst_root is root pointer of a non-empty binary search tree // post: 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 #endif

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...
icon
Related questions
Question

The definition for binary search tree should be the one used in class

Class definition:                                                                  

    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 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 
In btNode.h: provide prototypes for bst_insertbst_remove and bst_remove_max.
  In btNode.cpp: provide definition (implementation) for bst_insertbst_remove and bst_remove_ma

#ifndef BT_NODE_H
#define BT_NODE_H

struct btNode
{
   int data;
   btNode* left;
   btNode* right;
};
// 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
// 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
void portToArrayInOrder(btNode* bst_root, int* portArray);
void portToArrayInOrderAux(btNode* bst_root, int* portArray, int& portIndex);

// 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)
// post: 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
// pre:  bst_root is root pointer of a binary search tree (may be 0 for
//       empty tree)
// post: 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.

// write prototype for bst_remove here
// pre:  bst_root is root pointer of a non-empty binary search tree
// post: 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

#endif

int bst_size(btNode* bst_root)
{
}
if (bst_root == 0) return 0;
return 1 + bst_size(bst_root->left) + bst_size(bst_root->right);
Transcribed Image Text:int bst_size(btNode* bst_root) { } if (bst_root == 0) return 0; return 1 + bst_size(bst_root->left) + bst_size(bst_root->right);
1 #include "btNode.h"
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// write definition for bst_insert here
// write definition for bst_remove here
// write definition for bst_remove_max here
void portToArrayInOrder (btNode* bst_root, int* portArray)
{
if (bst_root == 0) return;
int portIndex = 0;
portToArrayInOrder Aux (bst_root, portArray, portIndex);
}
void portToArrayInOrder Aux (btNode* bst_root, int* portArray, int& portIndex)
{
}
if (bst_root
0) return;
portToArrayInOrder Aux (bst_root->left, portArray, portIndex);
portArray[portIndex++] = 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;
Transcribed Image Text:1 #include "btNode.h" 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 // write definition for bst_insert here // write definition for bst_remove here // write definition for bst_remove_max here void portToArrayInOrder (btNode* bst_root, int* portArray) { if (bst_root == 0) return; int portIndex = 0; portToArrayInOrder Aux (bst_root, portArray, portIndex); } void portToArrayInOrder Aux (btNode* bst_root, int* portArray, int& portIndex) { } if (bst_root 0) return; portToArrayInOrder Aux (bst_root->left, portArray, portIndex); portArray[portIndex++] = 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;
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps

Blurred answer
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
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 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)
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
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY