Using the following c++ header file near the bottom for context, fill in the "TODO" commented parts of the following function to finish the function implementation for the following DeleteVertex function: FUNCTION: // PURPOSE: Deletes a vertex that has E as its element. // PARAM: element E to be removed // ALGORITHM: First we must find the vertex then call Remove void BST::DeleteVertex(el_t E) { cout << "Trying to delete " << E << endl; Vertex *V; // the current vertex Vertex *Parent; // Parent will always point to V's parent // case 1: Lonely Root -------------------- if ((E == root->elem) && (root->left == NULL) && (root->right == NULL)) { cout << "...deleting the lonely root" << endl; delete root; root = NULL; return; } // only the Root was there and deleted it // case 2: One Substree Root ---------------- // if what you want to delete is the root if (/*TODO*/) { cout << "... deleting the root with just one child" << endl; if (/*TODO*/) { // TODO if it has only the left subtree // change the root to the left child and return // making sure the old root has been deleted and the new root's UP is NULL } else if (/*TODO*/) { // if it has only the right subtree // TODO change the root to the right child and return // making sure the old root has been deleted and the new root's UP is NULL } }// end of deleting the root with one subtree // ---- Otherwise deleting something else -------------- V = root; // start with the root to look for E Parent = NULL; // above the V so does not point to anything yet // going down the tree looking for E while (V != NULL) { if (E == V->elem) { // found it cout << "...removing " << V->elem << endl; // TODO call remove here to remove V return; } else if (E < V->elem) { cout << "...going to the left" << endl; // TODO update Parent and V here to go down } else { cout << "...going to the right" << endl; // TODO update Parent and V here to go down } }// end of while // reached NULL -- did not find it cout << "Did not find the key in the tree." << endl; }// end of DeleteVertex ----------------------------------------------------------------------------------------------------------- HEADER FILE:// tree element type is int for nowtypedef int el_t; // el_t is hidden from the client // definition of what a Vertex is - also hidden from the clientstruct Vertex{ Vertex *up; // points to the parent node Vertex *left; el_t elem; Vertex *right; int height; int balance;}; // this is set up to be inherited by another classclass BST {public: BST(); // intializes Root ~BST(); // destructor calls dtraverse to destroy the dynamic tree // PURPOSE: these will show the vertices in IN order // TO CALL: No parameter but provide a pointer to // the root vertex in calling INorderTraversal void Display(); void InOrderTraversal(Vertex*); // recursive // PURPOSE: these will search in PRE order - same as Depth First // TO CALL: provide the element to search for; provide a pointer to // the root vertex in calling PREorderSearch bool Search(el_t); bool PreOrderSearch(Vertex*, el_t); // recursive
Types of Linked List
A sequence of data elements connected through links is called a linked list (LL). The elements of a linked list are nodes containing data and a reference to the next node in the list. In a linked list, the elements are stored in a non-contiguous manner and the linear order in maintained by means of a pointer associated with each node in the list which is used to point to the subsequent node in the list.
Linked List
When a set of items is organized sequentially, it is termed as list. Linked list is a list whose order is given by links from one item to the next. It contains a link to the structure containing the next item so we can say that it is a completely different way to represent a list. In linked list, each structure of the list is known as node and it consists of two fields (one for containing the item and other one is for containing the next item address).
Using the following c++ header file near the bottom for context, fill in the "TODO" commented parts of the following function to finish the function implementation for the following DeleteVertex function:
FUNCTION:
// PURPOSE: Deletes a vertex that has E as its element.
-----------------------------------------------------------------------------------------------------------
HEADER FILE:
// tree element type is int for now
typedef int el_t; // el_t is hidden from the client
// definition of what a Vertex is - also hidden from the client
struct Vertex
{
Vertex *up; // points to the parent node
Vertex *left;
el_t elem;
Vertex *right;
int height;
int balance;
};
// this is set up to be inherited by another class
class BST {
public:
BST(); // intializes Root
~BST(); // destructor calls dtraverse to destroy the dynamic tree
// PURPOSE: these will show the vertices in IN order
// TO CALL: No parameter but provide a pointer to
// the root vertex in calling INorderTraversal
void Display();
void InOrderTraversal(Vertex*); // recursive
// PURPOSE: these will search in PRE order - same as Depth First
// TO CALL: provide the element to search for; provide a pointer to
// the root vertex in calling PREorderSearch
bool Search(el_t);
bool PreOrderSearch(Vertex*, el_t); // recursive
AI-generated content may present inaccurate or offensive content that does not represent bartleby’s views.
Unlock instant AI solutions
Tap the button
to generate a solution
