Для класса нас попросили создать двоичное дерево поиска. Небольшая проблема заключается в том, что наши вспомогательные функции не являются частью класса заголовка, и поэтому, когда я пытаюсь использовать вспомогательные функции, которые я создал, для добавления в дерево или для обхода дерева, это всегда приводит к ошибке сегментации или неправильному вывод. Код для класса заголовка просто создает класс структуры для узлов
struct MovieNode{
int ranking;
string title;
int year;
float rating;
MovieNode* left = NULL;
MovieNode* right = NULL;
MovieNode(int rank, string t, int y, float r) {
title = t;
ranking = rank;
year = y;
rating = r;
}
};
Файл исходного кода содержит все классы из файла заголовка, а также вспомогательные функции, которые я создал для того, чтобы помочь с заданием.
#include "MovieTree.hpp"
#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
using namespace std;
// MovieNode: node struct that will be stored in the MovieTree BST
MovieTree::MovieTree() {
this -> root = NULL;
}
MovieTree::~MovieTree() {
// delete every node and then set the root to NULL
}
Я лично не знаю, как работают деструкторы. Мои всегда получают ошибки сегментации.
// helper function to printMovieInventory()
void inorderTraverse(MovieNode* node) {
inorderTraverse(node -> left);
cout << "Movie: " << node -> title << " " << node -> rating << endl;
inorderTraverse(node -> right);
}
void MovieTree::printMovieInventory() {
// using inorder traversal
if (root == NULL) {
cout << "Tree is Empty. Cannot print" << endl;
}
else if (root != NULL) {
inorderTraverse(root);
}
}
Эта функция используется для обхода заказа, чтобы распечатать все фильмы вместе с их рейтингом. На самом деле происходит ошибка сегментации.
// helper function to addMovieNode()
void insert(MovieNode* root, int ranking, string title, int year, float rating) {
if (root == NULL) {
root = new MovieNode(ranking, title, year, rating);
}
if (title < root -> title) {
insert(root -> left, ranking, title, year, rating);
}
else if (title > root -> title) {
insert(root -> right, ranking, title, year, rating);
}
}
void MovieTree::addMovieNode(int ranking, string title, int year, float rating) {
if (root == NULL) {
root = new MovieNode(ranking, title, year, rating);
}
else if (root != NULL) {
insert(root, ranking, title, year, rating);
}
}
Эта функция меня смутила больше всего. Большинство функций, которые я видел, чтобы вставить новый узел в дерево, требуют указателя на узел Node* node и затем данных, которые будут go в узел. Поэтому, когда я запускаю эту функцию, она вставляет только первый узел (root), а затем в дерево ничего не вставляется.
// helper function to findMovie()
MovieNode* compare(string title, MovieNode* root) {
if (root == NULL) {
return NULL;
}
else {
if (title.compare(root -> title) < 0) {
compare(title, root -> left);
}
else if (title.compare(root -> title) > 0) {
compare(title, root -> right);
}
else if (title.compare(root -> title) == 0) {
return root;
}
}
}
void MovieTree::findMovie(string title) {
if (root == NULL) {
cout << "Movie not found." << endl;
}
else {
MovieNode* foundMovie = compare(title, root);
if (foundMovie == NULL) {
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 << "rating :" << foundMovie -> rating << endl;
}
}
}
Эта функция сравнивает названия фильмов, а затем Обход дерева, чтобы найти mov ie, который соответствует ему. Если его нет в дереве, то возвращается, что mov ie не может быть найден. Этот выводит странные значения в рейтинге, году и рейтинге. Даже если mov ie не найден, он выводит для него некоторые случайные значения.
// helper functino to queryMovies()
void preorderTraverse(MovieNode* node, int rating, int year) {
if (node -> rating >= rating && node -> year < year) {
cout << node -> title << "(" << node -> year << ") " << node -> rating << endl;
}
else {
preorderTraverse(node -> left, rating, year);
preorderTraverse(node -> right, rating, year);
}
}
void MovieTree::queryMovies(float rating, int year) {
if (root == NULL) {
cout << "Tree is Empty. Cannot query Movies" << endl;
}
else if (root != NULL) {
cout << "Movies that came out after " << year << " with rating at least " << rating << endl;
preorderTraverse(root, rating, year);
}
}
Эта функция аналогична findMovie(), за исключением того, что сравнивает год и рейтинг, а затем распечатывает все фильмы, вышедшие после года и имеющие рейтинг, превышающий или равный рейтингу. Это происходит не в определенном порядке, поэтому я прошел по дереву, используя предварительный порядок. Он также получает ошибку сегментации.
// helper function to averageRating()
int average(MovieNode* node, int sum) {
sum += node -> rating;
average(node -> left, sum);
average(node -> right, sum);
return sum;
}
void MovieTree::averageRating() {
if (root == NULL) {
cout << "Average rating:0.0" << endl;
}
else if (root != NULL) {
int avg = 0;
avg += average(root, avg);
cout << "Average rating:" << avg << endl;
}
}
Как видно из названия, эта функция суммирует все оценки и делит на количество узлов, чтобы получить среднее значение. Над этим я все еще работаю, так что я знаю, что он полон ошибок.
// helper function to printLevelNodes()
void getLevel(MovieNode* node, int level) {
if (node != NULL) {
if (level == 0) {
cout << "Movie: " << node -> title << " " << node -> rating << endl;
}
else if (level != 0) {
getLevel(node -> left, level - 1);
getLevel(node -> right, level - 1);
}
}
}
// helper function to printLevelNodes()
int maxLevel(MovieNode* node) {
if (node == NULL) {
return 0;
}
else {
int leftD = maxLevel(node -> left);
int rightD = maxLevel(node -> right);
if (leftD > rightD) {
return (leftD + 1);
}
else {
return (rightD + 1);
}
}
}
void MovieTree::printLevelNodes(int level) {
int max = maxLevel(root);
if (level <= max) {
getLevel(root, level);
}
}
Забавно, последняя функция - единственная, которая работает. Это не имеет смысла для меня, потому что я моделировал вспомогательные функции друг за другом, но некоторые из них просто не работают. Есть ли способ получить доступ к дереву из вспомогательных функций, даже если они не являются частью файла заголовка? Если нет, то как работают некоторые вспомогательные функции, а другие нет?