I\'ve posted some C++ code below that I understan partially. Please go through c

Question

I've posted some C++ code below that I understan partially. Please go through code and thorougly comment the code explaining whats going on. Only the implementation part.

#ifndef MOVIETREE_H
#define MOVIETREE_H

#include

struct MovieNode{
int ranking;
std::string title;
int year;
int quantity;
MovieNode *parent;
MovieNode *leftChild;
MovieNode *rightChild;

MovieNode(){};

MovieNode(int in_ranking, std::string in_title, int in_year, int in_quantity)
{
ranking = in_ranking;
title = in_title;
year = in_year;
quantity = in_quantity;
parent = NULL;
leftChild = NULL;
rightChild = NULL;
}

};

class MovieTree
{

public:
MovieTree();
~MovieTree();
void printMovieInventory();
int countMovieNodes();
void deleteMovieNode(std::string title);
void addMovieNode(int ranking, std::string title, int releaseYear, int quantity);
void findMovie(std::string title);
void rentMovie(std::string title);

protected:

private:
void DeleteAll(MovieNode * node); //use this for the post-order traversal deletion of the tree
void printMovieInventory(MovieNode * node);
void countMovieNodes(MovieNode *node, int *c);
MovieNode* search(std::string title);
MovieNode* searchRecursive(MovieNode *node, std::string value);
MovieNode* treeMinimum(MovieNode *node);
MovieNode *root;
};

#endif // MOVIETREE

#include "MovieTree.h"

#include

using namespace std;

MovieTree::MovieTree() {
root = nullptr;
}

MovieTree::~MovieTree() {
DeleteAll(root);
}

void MovieTree::printMovieInventory() {
printMovieInventory(root);
}

int MovieTree::countMovieNodes() {
int count = 0;
countMovieNodes(root, &count);
return count;
}

void MovieTree::deleteMovieNode(std::string title) {
auto node = search(title);
if (!node) {
//If movie not found in tree
cout << "Movie not found." << endl;
return;
}

// movie found. delete it.

// case 1: node has no children.
if (!node->leftChild && !node->rightChild) {
// check if parent is availble.
if (node->parent) {
// check where the node is present relative to it's parent.
if (node->parent->leftChild == node) {
node->parent->leftChild = nullptr;
} else {
node->parent->rightChild = nullptr;
}
} else {
// If not, then it's a root. If it's root with no left/ right
// child, then delete it.
root = nullptr;
}

delete node;
return;
}

// case 2: node has only 1 child
if (node->leftChild && !node->rightChild) {
node->leftChild->parent = node->parent;
//see if there's a parent.
if (node->parent) {
// check where the node is present relative to it's parent.
if (node->parent->leftChild == node) {
node->parent->leftChild = node->leftChild;
} else {
node->parent->rightChild = node->leftChild;
}
} else {
// root with only left child
root = root->leftChild;
}
delete node;
return;
}

if (!node->leftChild && node->rightChild) {
node->rightChild->parent = node->parent;
//see if there's a parent.
if (node->parent) {
// check where the node is present relative to it's parent.
if (node->parent->leftChild == node) {
node->parent->leftChild = node->rightChild;
} else {
node->parent->rightChild = node->rightChild;
}
} else {
// root with only right child
root = root->rightChild;
}
delete node;
return;
}

// case 3: node has both left and right child
// pick the min value from the right subtree
auto minNode = treeMinimum(node->rightChild);

// It would be easier to copy value from minNode to node and delete minNode.
// Rather than swapping the node with minNode and update a bunch of links!
node->title = minNode->title;
node->ranking = minNode->ranking;
node->quantity = minNode->quantity;
node->year = minNode->year;

// Set the minNode right's parent
if (minNode->rightChild)
minNode->parent->rightChild = minNode->parent;

// Is the minNode directly attached to right side of the node.
if (node->rightChild == minNode) {
node->rightChild = minNode->rightChild;
delete minNode;
return;
}

// If not present directly on the right.
minNode->parent->leftChild = minNode->rightChild;
delete minNode;
}

void MovieTree::addMovieNode(int ranking, std::string title, int releaseYear, int quantity) {
auto node = new MovieNode(ranking, title, releaseYear, quantity);
if (!root) {
// no root.
root = node;
return;
}

// string comparision uses std::lexicographical_compare.
// So i can directly comapare titles.

auto *temp = root;
MovieNode* parent = nullptr;

while(temp) {
parent = temp;
if (title > temp->title)
temp = temp->rightChild;
else
temp = temp->leftChild;
}

// parent shouldn't be nullptr at this point.

node->parent = parent;
if (title > parent->title)
parent->rightChild = node;
else
parent->leftChild = node;
}

void MovieTree::findMovie(std::string title) {
auto foundMovie = search(title);
if (!foundMovie) {
//If movie not found in tree
cout << "Movie not found." << endl;
} else {
cout << "Movie Info:" << endl;
cout << "===========" << endl;
cout << "Ranking:" << foundMovie->ranking << endl;
cout << "Title:" << foundMovie->title << endl;
cout << "Year:" << foundMovie->year << endl;
cout << "Quantity:" << foundMovie->quantity << endl;
}
}

void MovieTree::rentMovie(std::string title) {
auto foundMovie = search(title);
if (!foundMovie) {
//If movie not found in tree
cout << "Movie not found." << endl;
return;
}

//If movie is in stock
if (foundMovie->quantity > 0) {
// rent the movie.
foundMovie->quantity--;

cout << "Movie has been rented." << endl;
cout << "Movie Info:" << endl;
cout << "===========" << endl;
cout << "Ranking:" << foundMovie->ranking << endl;
cout << "Title:" << foundMovie->title << endl;
cout << "Year:" << foundMovie->year << endl;
cout << "Quantity:" << foundMovie->quantity << endl;
}

// If movie quantity is zero, delete it from movie tree.
if (foundMovie->quantity <= 0) {
deleteMovieNode(foundMovie->title);
// At this point foundMovie is invalid. Don't use foundMovie.
foundMovie = nullptr;
}
}

void MovieTree::DeleteAll(MovieNode * node) { //use this for the post-order traversal deletion of the tree
if (!node) {
// no node to delete.
return;
}

DeleteAll(node->leftChild);
DeleteAll(node->rightChild);

//For all movies in tree
cout << "Deleting: " << node->title << endl;

delete node;
node = nullptr;
}

void MovieTree::printMovieInventory(MovieNode * node) {
if (!node) {
return;
}

printMovieInventory(node->leftChild);

// For all movies in tree
cout << "Movie: " << node->title << " " << node->quantity << endl;

printMovieInventory(node->rightChild);
}

void MovieTree::countMovieNodes(MovieNode *node, int *c) {
if (!node) {
// node is empty. nothing to count.
return;
}

countMovieNodes(node->leftChild, c);
(*c)++;
countMovieNodes(node->rightChild, c);
}

MovieNode* MovieTree::search(std::string title) {
return searchRecursive(root, title);
}

MovieNode* MovieTree::searchRecursive(MovieNode *node, std::string value) {
if (!node) {
return nullptr;
}

if (node->title == value) {
return node;
}

if (value > node->title)
//If value is greater continue search down right tree of tile
return searchRecursive(node->rightChild, value);
else
//If value is less continue search down right tree of tile
return searchRecursive(node->leftChild, value);
}

MovieNode* MovieTree::treeMinimum(MovieNode *node) {
if (!node) {
return nullptr;
}

while(node->leftChild) {
node = node->leftChild;
}

return node;
}

Explanation / Answer

Hi please find the code with the comments of explanation , please have a handson to the structure and how to call values of structure your understanding to the cide will be 100 its only the structures of c++ and how we can retrive values from struture objects .

Have a nice day

the code

#ifndef MOVIETREE_H
#define MOVIETREE_H
#include
struct MovieNode{
int ranking;
std::string title;
int year;
int quantity;
MovieNode *parent;
MovieNode *leftChild;
MovieNode *rightChild;
MovieNode(){};
MovieNode(int in_ranking, std::string in_title, int in_year, int in_quantity)
{
ranking = in_ranking;
title = in_title;
year = in_year;
quantity = in_quantity;
parent = NULL;
leftChild = NULL;
rightChild = NULL;
}
};
class MovieTree
{
public:
MovieTree(); //creating a movietree constructor
~MovieTree(); // destroying the constructor
void printMovieInventory(); // method declaration printMovieInventory to print data of movie inventory
int countMovieNodes(); // method declaration to count movie nodes
void deleteMovieNode(std::string title); // method declaration to delete movie node
void addMovieNode(int ranking, std::string title, int releaseYear, int quantity); // to add a movie node method declaration
void findMovie(std::string title); // declared method for finding movie
void rentMovie(std::string title); // to rent a movie method declaration
protected:
private:
void DeleteAll(MovieNode * node); //use this for the post-order traversal deletion of the tree
void printMovieInventory(MovieNode * node); // parametrized method for inventory method passing node to start traversing from the input node
void countMovieNodes(MovieNode *node, int *c); //count movie nodes
MovieNode* search(std::string title); // search from title passed title name string
MovieNode* searchRecursive(MovieNode *node, std::string value); // recursive search using node and value
MovieNode* treeMinimum(MovieNode *node); // find tree minimum
MovieNode *root;
};
#endif // MOVIETREE




#include "MovieTree.h"
#include
using namespace std;
MovieTree::MovieTree() {
root = nullptr; // set root value as null
}
MovieTree::~MovieTree() {
DeleteAll(root); // calling delete all values with passing root value
}
void MovieTree::printMovieInventory() {
printMovieInventory(root); // calling print inventory with passing root value
}
int MovieTree::countMovieNodes() {
int count = 0; // initialize count to be 0 in initial
countMovieNodes(root, &count); // call method with root node to start couting
return count; // return count value
}
void MovieTree::deleteMovieNode(std::string title) {
auto node = search(title); // search title from nodes
if (!node) { //if node is null then movie is not found in search
//If movie not found in tree
cout << "Movie not found." << endl;
return;
}
// movie found. delete it. delete the movie if found
// case 1: node has no children. // check node have chidren or not
if (!node->leftChild && !node->rightChild) {
// check if parent is availble.
if (node->parent) {
// check where the node is present relative to it's parent.
if (node->parent->leftChild == node) {
node->parent->leftChild = nullptr;
} else {
node->parent->rightChild = nullptr;
}
} else {
// If not, then it's a root. If it's root with no left/ right
// child, then delete it.
root = nullptr;
}
delete node;
return;
}
// case 2: node has only 1 child -------- one child scenario
if (node->leftChild && !node->rightChild) {
node->leftChild->parent = node->parent;
//see if there's a parent.
if (node->parent) {
// check where the node is present relative to it's parent.
if (node->parent->leftChild == node) {
node->parent->leftChild = node->leftChild;
} else {
node->parent->rightChild = node->leftChild;
}
} else {
// root with only left child
root = root->leftChild;
}
delete node;
return;
}
// condition for only right child of node
if (!node->leftChild && node->rightChild) {
node->rightChild->parent = node->parent;
//see if there's a parent.
if (node->parent) {
// check where the node is present relative to it's parent.
if (node->parent->leftChild == node) {
node->parent->leftChild = node->rightChild;
} else {
node->parent->rightChild = node->rightChild;
}
} else {
// root with only right child
root = root->rightChild;
}
delete node;
return;
}
// case 3: node has both left and right child
// pick the min value from the right subtree
auto minNode = treeMinimum(node->rightChild);
// It would be easier to copy value from minNode to node and delete minNode.
// Rather than swapping the node with minNode and update a bunch of links!
node->title = minNode->title; // setting value from treemin object value
node->ranking = minNode->ranking; //setting value from treemin object value
node->quantity = minNode->quantity; //setting value from treemin object value
node->year = minNode->year; //setting value from treemin object value
// Set the minNode right's parent
if (minNode->rightChild)
minNode->parent->rightChild = minNode->parent;
// Is the minNode directly attached to right side of the node.
if (node->rightChild == minNode) {
node->rightChild = minNode->rightChild;
delete minNode;
return;
}
// If not present directly on the right.
minNode->parent->leftChild = minNode->rightChild;
delete minNode;
}
void MovieTree::addMovieNode(int ranking, std::string title, int releaseYear, int quantity) {
auto node = new MovieNode(ranking, title, releaseYear, quantity);
if (!root) {
// no root. put value of node in root
root = node;
return;
}
// string comparision uses std::lexicographical_compare.
// So i can directly comapare titles.
auto *temp = root;
MovieNode* parent = nullptr;
while(temp) {
parent = temp;
if (title > temp->title)
temp = temp->rightChild;
else
temp = temp->leftChild;
}
// parent shouldn't be nullptr at this point.
node->parent = parent;
if (title > parent->title)
parent->rightChild = node;
else
parent->leftChild = node;
}
void MovieTree::findMovie(std::string title) {
auto foundMovie = search(title); // search title of movie
if (!foundMovie) { //if found
//If movie not found in tree
cout << "Movie not found." << endl;
} else {
cout << "Movie Info:" << endl;
cout << "===========" << endl;
cout << "Ranking:" << foundMovie->ranking << endl; // rinting value of foundmovie ranking
cout << "Title:" << foundMovie->title << endl;
cout << "Year:" << foundMovie->year << endl;
cout << "Quantity:" << foundMovie->quantity << endl;
}
}
void MovieTree::rentMovie(std::string title) {
auto foundMovie = search(title);
if (!foundMovie) {
//If movie not found in tree
cout << "Movie not found." << endl;
return;
}
//If movie is in stock
if (foundMovie->quantity > 0) {
// rent the movie.
foundMovie->quantity--;
cout << "Movie has been rented." << endl;
cout << "Movie Info:" << endl;
cout << "===========" << endl;
cout << "Ranking:" << foundMovie->ranking << endl;
cout << "Title:" << foundMovie->title << endl;
cout << "Year:" << foundMovie->year << endl;
cout << "Quantity:" << foundMovie->quantity << endl;
}
// If movie quantity is zero, delete it from movie tree.
if (foundMovie->quantity <= 0) {
deleteMovieNode(foundMovie->title);
// At this point foundMovie is invalid. Don't use foundMovie.
foundMovie = nullptr;
}
}
void MovieTree::DeleteAll(MovieNode * node) { //use this for the post-order traversal deletion of the tree
if (!node) {
// no node to delete.
return;
}
DeleteAll(node->leftChild);
DeleteAll(node->rightChild);
//For all movies in tree
cout << "Deleting: " << node->title << endl;
delete node;
node = nullptr;
}
void MovieTree::printMovieInventory(MovieNode * node) {
if (!node) {
return;
}
printMovieInventory(node->leftChild);
// For all movies in tree
cout << "Movie: " << node->title << " " << node->quantity << endl;
printMovieInventory(node->rightChild);
}
void MovieTree::countMovieNodes(MovieNode *node, int *c) {
if (!node) {
// node is empty. nothing to count.
return;
}// count to the left side
countMovieNodes(node->leftChild, c);
(*c)++; // count to the right side
countMovieNodes(node->rightChild, c);
}
MovieNode* MovieTree::search(std::string title) {
return searchRecursive(root, title);
}
MovieNode* MovieTree::searchRecursive(MovieNode *node, std::string value) {
if (!node) { // if no node return null
return nullptr;
}//if node title is matched with value provided return node value
if (node->title == value) {
return node;
}
if (value > node->title)
//If value is greater continue search down right tree of tile
return searchRecursive(node->rightChild, value);
else
//If value is less continue search down right tree of tile
return searchRecursive(node->leftChild, value);
}
MovieNode* MovieTree::treeMinimum(MovieNode *node) {
if (!node) { // if node value null return null pointer value
return nullptr;
}
while(node->leftChild) { //check node is having left child value if true
node = node->leftChild; // set node value as node left child value
}
return node;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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