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 ============================== 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 ==============================
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 |
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
==============================
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
==============================
Step by step
Solved in 5 steps with 2 images