使用辅助函数创建树函数

Question

对于class，我们被要求创建一个二进制搜索树。小问题是，我们的helper函数不是头类的一部分，因此当我尝试使用我创建的helper功能添加到树中或遍历树时，它总是会给我一个分段错误或错误的输出。头类的代码只是为Nodes 创建结构类

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的指针，然后是将进入该节点的数据。因此，每当我运行这个函数时，它只插入第一个节点(根(，然后没有其他节点插入到树中。

// 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;
}
}
}

此函数比较电影的标题，然后遍历树以找到与其匹配的电影。如果不在树中，则返回找不到电影。这一个在评级、年份和排名中不断输出奇怪的值。即使没有找到电影，它也会为它输出一些随机值

// 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);
}
}

有趣的是，最后一个函数是唯一有效的函数。这对我来说没有意义，因为我一个接一个地对助手函数进行建模，但其中一些函数似乎不起作用。有没有一种方法可以从辅助函数访问树，即使它们不是头文件的一部分？如果没有，那么一些helper函数是如何工作的，而另一些却不能工作呢？

Answer 1

在顺序函数后面的插入函数

此函数使用按顺序遍历打印出所有电影及其评分。实际发生的是分割错误。

分段错误的原因是您正在检查左右部分，即使它包含NULL。其中，当左部分确实存在时，只检查左部分，右部分也一样。

更改：

void inorderTraverse(MovieNode* node) {
if(node -> left)
inorderTraverse(node -> left);
cout << "Movie: " << node -> title << " " << node -> rating << endl;
if(node -> right)
inorderTraverse(node -> right);
}

这个函数是我最困惑的一个。我见过的将新节点插入树中的大多数函数都需要一个指向节点node*节点的指针，然后是将进入该节点的数据。因此，每当我运行这个函数时，它只插入第一个节点(根(，然后没有其他节点插入到树中。

由于要在确切位置添加节点，因此必须先转到该位置。然后只有您可以添加节点[或在正确位置添加引用]。

更改：

MovieNode * insert(MovieNode* root, int ranking, string title, int year, float rating) 
{
if (root == NULL) {
return new MovieNode(ranking, title, year, rating);
}
if (title < root -> title) {
root->left = insert(root -> left, ranking, title, year, rating);
}
else if (title > root -> title) {
root-> right = insert(root -> right, ranking, title, year, rating);
}
return root;
}
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) {
root = insert(root, ranking, title, year, rating);
}
}

现在，希望一切都好！这里ping，如果你在任何地方被卡住或输出错误。