C++ QUESTION!! PLEASE HELP. Give the procedural C++ code for the recursive deall

Question

C++ QUESTION!! PLEASE HELP.

Give the procedural C++ code for the recursive deallocation of a binary search
tree, which is accomplished with the functions: void deallocate(BST *tree) and
void deallocateSubtree(TreeNode *subtree). The deallocate function should call
deallocateSubtree if the tree has a root node. The deallocateSubtree function should
recursively traverse the tree using the post-order traversal. It will delete the subtree root as
the “visit” operation.
This function MUST be recursive. Two points will be deducted if the iterative traversal is
given. Assume that the structure BST has been defined with the member variable root and
that the structure TreeNode has been defined with the member variables data, left, and
right.

Explanation / Answer

void DeleteNode(TreeNode*& tree); void Delete(TreeNode*& tree, ItemType item); void TreeType::DeleteItem(ItemType item) // Calls the recursive function Delete to delete item from tree. { Delete(root, item); } void Delete(TreeNode*& tree, ItemType item) // Deletes item from tree. // Post: item is not in tree. { if (item info) Delete(tree->left, item); // Look in left subtree. else if (item > tree->info) Delete(tree->right, item); // Look in right subtree. else DeleteNode(tree); // Node found; call DeleteNode. } void GetPredecessor(TreeNode* tree, ItemType& data); void DeleteNode(TreeNode*& tree) // Deletes the node pointed to by tree. // Post: The user's data in the node pointed to by tree is no // longer in the tree. If tree is a leaf node or has only one // non-NULL child pointer, the node pointed to by tree is // deleted; otherwise, the user's data is replaced by its // logical predecessor and the predecessor's node is deleted. { ItemType data; TreeNode* tempPtr; tempPtr = tree; if (tree->left == NULL) { tree = tree->right; delete tempPtr; } else if (tree->right == NULL) { tree = tree->left; delete tempPtr; } else { GetPredecessor(tree->left, data); tree->info = data; Delete(tree->left, data); // Delete predecessor node. } } void GetPredecessor(TreeNode* tree, ItemType& data) // Sets data to the info member of the rightmost node in tree. { while (tree->right != NULL) tree = tree->right; data = tree->info; }

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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