Linked List Sorted when added : I have a linked list in a Binary search Tree. So
ID: 3911345 • Letter: L
Question
Linked List Sorted when added :
I have a linked list in a Binary search Tree. So my function successfully creates the nodes and add to the linked list however, I need to have the linked list sorted. it is not working for me and I don't know how to fix it.
I have attached my function add which is in a .cpp file and then the struct underneath is in my .h file.
(I just used another print function to see if it's in order or not)
void MovieTree::addMovieNode(int ranking, string title, int releaseYear, int quantity)
{
MovieNodeLL* movie = new MovieNodeLL(ranking, title, releaseYear, quantity);
MovieNodeBST * parenttitle;
MovieNodeBST* current ;
char littleletter =title[0];
//
if(root == NULL)//Add the root
{
root = new MovieNodeBST(title[0]);
root->head = movie;
return;
}
current = root;
while(current != NULL)
{
if (current->letter == littleletter)//found correct BST node
{
break;
}
parenttitle = current;
if (littleletter > current->letter)
{
current = current->rightChild;
}
else if (littleletter < current->letter)
{
current = current->leftChild;
}
}
if(current==NULL)// Add new node(Movie Bst node) (letter node)
{
if(parenttitle->letter
{
MovieNodeBST* newChar = new MovieNodeBST(littleletter);
parenttitle->rightChild = newChar;
newChar->parent = parenttitle;
current = newChar;
newChar->head = movie;
}
else if(parenttitle->letter>littleletter)
{
MovieNodeBST* newChar = new MovieNodeBST(littleletter);
parenttitle->leftChild = newChar;
newChar->parent = parenttitle;
current = newChar;
newChar->head = movie;
}
}
else if (current != NULL)// Add to current linked list
{
if(current->head==NULL) //Add the head;
{
current->head=movie;
return;
}
if(current->head>movie)
{
movie->next=current->head;
current->head=movie;
}
else
{
MovieNodeLL *addtolist=current->head;
while((addtolist->next) && (addtolist->next->title < movie->title))
{
addtolist=addtolist->next;
}
movie->next =addtolist->next;
addtolist->next=movie;
}
}
}
--------
In the .h File(part of it)
struct MovieNodeLL{
int ranking;
std::string title;
int year;
int quantity;
MovieNodeLL* next;
MovieNodeLL(){};
MovieNodeLL(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;
next = NULL;
};
};
struct MovieNodeBST{
char letter;
MovieNodeBST* parent;
MovieNodeBST* leftChild;
MovieNodeBST* rightChild;
MovieNodeLL* head;
MovieNodeBST(){};
MovieNodeBST(char in_letter)
{
letter = in_letter;
parent = NULL;
leftChild = NULL;
rightChild = NULL;
head = NULL;
};
};
Explanation / Answer
I have fixed the code. Please do check and rate the answer if it helped. Thank you
void MovieTree::addMovieNode(int ranking, string title, int releaseYear, int quantity)
{
MovieNodeLL* movie = new MovieNodeLL(ranking, title, releaseYear, quantity);
MovieNodeBST * parenttitle;
MovieNodeBST* current ;
char littleletter =title[0];
//
if(root == NULL)//Add the root
{
root = new MovieNodeBST(title[0]);
root->head = movie;
return;
}
current = root;
while(current != NULL)
{
if (current->letter == littleletter)//found correct BST node
{
break;
}
parenttitle = current;
if (littleletter > current->letter)
{
current = current->rightChild;
}
else if (littleletter < current->letter)
{
current = current->leftChild;
}
}
if(current==NULL)// Add new node(Movie Bst node) (letter node)
{
if(parenttitle->letter < littleletter)
{
MovieNodeBST* newChar = new MovieNodeBST(littleletter);
parenttitle->rightChild = newChar;
newChar->parent = parenttitle;
current = newChar;
newChar->head = movie;
}
else if(parenttitle->letter>littleletter)
{
MovieNodeBST* newChar = new MovieNodeBST(littleletter);
parenttitle->leftChild = newChar;
newChar->parent = parenttitle;
current = newChar;
newChar->head = movie;
}
}
else if (current != NULL)// Add to current linked list
{
if(current->head==NULL) //Add the head;
{
current->head=movie;
return;
}
MovieNodeLL* curr = current->head;
MovieNodeLL* prev = NULL;
while(curr != null && movie->title > curr->title)
{
prev = curr;
curr = curr->next;
}
movie->next = curr;
if(prev == NULL)//insert as head node in linked list
current->head = movie;
else
prev->next = movie;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.