使用二叉搜索树时 C++ 堆栈溢出
C++ stack overflow when using a binary search tree
我正在做一个学校项目，我需要将一些从 CSV 文件解析的项目加载到二叉搜索树对象中。当我使用包含大约 180 个项目的 CSV 文件时，它工作正常，但是当我使用包含略低于 18,000 个项目的 CSV 文件时，我收到堆栈溢出错误。我想知道是否有人可以提供帮助。这是代码（其中很多是提供给我的）...
#include <iostream>
#include <time.h>
#include "CSVparser.hpp"
using namespace std;
double strToDouble(string str, char ch);
// define a structure to hold bid information
struct Bid {
string bidId; // unique identifier
string title;
string fund;
double amount;
Bid() {
amount = 0.0;
}
};
// FIXED (1): Internal structure for tree node
struct Node {
Bid bid;
Node* left;
Node* right;
//default constructor
Node() {
left = nullptr;
right = nullptr;
}
//constructor which receives bid parameter
Node(Bid curBid) : Node() {
this->bid = curBid;
}
};
class BinarySearchTree {
private:
Node* root;
void addNode(Node* node, Bid bid);
void inOrder(Node* node);
Node* removeNode(Node* node, string bidId);
public:
BinarySearchTree();
virtual ~BinarySearchTree();
void InOrder();
void Insert(Bid bid);
void Remove(string bidId);
Bid Search(string bidId);
};
//constructor
BinarySearchTree::BinarySearchTree() {
// initialize housekeeping variables
root = nullptr;
}
//destructor
BinarySearchTree::~BinarySearchTree() {
// recurse from root deleting every node
}
//Traverse the tree in order
void BinarySearchTree::InOrder() {
this->inOrder(root);
}
//Insert a bid
void BinarySearchTree::Insert(Bid bid) {
// FIXED (2a) Implement inserting a bid into the tree
//if root is null then it gets set to new bid pointer
if (root == nullptr) {
root = new Node(bid);
}
else { //if root isn't null then adds the bid to the tree
this->addNode(root, bid);
}
}
//Remove a bid
void BinarySearchTree::Remove(string bidId) {
// FIXED (4a) Implement removing a bid from the tree
//removes requested node
this->removeNode(root, bidId);
}
//Search for a bid
Bid BinarySearchTree::Search(string bidId) {
// FIXED (3) Implement searching the tree for a bid
//initialize to root because that is where the search begins
Node* current = root;
//search through tree until bottom or until bid is found
while (current != nullptr) {
//if current bid matches search, returns it
if (bidId.compare(current->bid.bidId) == 0) {
return current->bid;
}
//bid parameter is less than current bid, continues searching to the left
if (bidId.compare(current->bid.bidId) < 0) {
current = current->left;
}
else { //bid parameter is greater than current bid, continues searching to the right
current = current->right;
}
}
//if while loop is exited without finding a match, an empty bid is created and returned
Bid bid;
return bid;
}
/**
* Add a bid to some node (recursive)
*
* @param node Current node in tree
* @param bid Bid to be added
*/
void BinarySearchTree::addNode(Node* node, Bid bid) {
// FIXED (2b) Implement inserting a bid into the tree
//if the bid parameter is less than the current node, then add to the left
if (bid.bidId.compare(node->bid.bidId) < 0) {
if (node->left == nullptr) { //if left node is null then it adds the new node here
node->left = new Node(bid);
}
else {
this->addNode(node->left, bid); //recursively calls addnode until bottom is reached
}
}
else { //add to right
if (node->right == nullptr) { //if left node is null then it adds the new node here
node->right = new Node(bid);
}
else {
this->addNode(node->right, bid); //recursively calls addnode until bottom is reached
}
}
}
void BinarySearchTree::inOrder(Node* node) {
if (node != nullptr) {
inOrder(node->left);
cout << node->bid.bidId
<< ": "
<< node->bid.title
<< " | "
<< node->bid.amount
<< " | "
<< node->bid.fund
<< endl;
inOrder(node->right);
}
}
Node* BinarySearchTree::removeNode(Node* node, string bidId) {
//if this node is null then return
if (node == nullptr) {
return node;
}
//if bid parameter is less than current node, searches left recursively
if (bidId.compare(node->bid.bidId) < 0) {
node->left = removeNode(node->left, bidId);
}
else if (bidId.compare(node->bid.bidId) > 0) { //if bid parameter is greater than current node, searches right recursively
node->right = removeNode(node->right, bidId);
}
else { //if its not < or > then its ==, so it needs to be removed since it matches the parameter bidId
//no children so node can just be removed
if ((node->left == nullptr) && (node->right == nullptr)) {
delete node;
node = nullptr;
}
//if one child to left
if ((node->left != nullptr) && (node->right == nullptr)) {
Node* temp = node;
node = node->left;
delete temp;
} //if one child to right
else if ((node->left == nullptr) && (node->right != nullptr)) {
Node* temp = node;
node = node->left;
delete temp;
} //if two children
else {
Node* temp = node;
node = node->right;
while (temp->left != nullptr) {
temp = temp->left;
}
node->bid = temp->bid;
node->right = removeNode(node->right, temp->bid.bidId);
}
}
return node;
}
//============================================================================
// Static methods used for testing
//============================================================================
/**
* Display the bid information to the console (std::out)
*
* @param bid struct containing the bid info
*/
void displayBid(Bid bid) {
cout << bid.bidId << ": " << bid.title << " | " << bid.amount << " | "
<< bid.fund << endl;
return;
}
/**
* Load a CSV file containing bids into a container
*
* @param csvPath the path to the CSV file to load
* @return a container holding all the bids read
*/
void loadBids(string csvPath, BinarySearchTree* bst) {
cout << "Loading CSV file " << csvPath << endl;
// initialize the CSV Parser using the given path
csv::Parser file = csv::Parser(csvPath);
// read and display header row - optional
vector<string> header = file.getHeader();
for (auto const& c : header) {
cout << c << " | ";
}
cout << "" << endl;
try {
// loop to read rows of a CSV file
for (unsigned int i = 0; i < file.rowCount(); i++) {
// Create a data structure and add to the collection of bids
Bid bid;
bid.bidId = file[i][1];
bid.title = file[i][0];
bid.fund = file[i][8];
bid.amount = strToDouble(file[i][4], '$');
//cout << "Item: " << bid.title << ", Fund: " << bid.fund << ", Amount: " << bid.amount << endl;
// push this bid to the end
bst->Insert(bid);
}
} catch (csv::Error &e) {
std::cerr << e.what() << std::endl;
}
}
/**
* Simple C function to convert a string to a double
* after stripping out unwanted char
*
* credit:
*
* @param ch The character to strip out
*/
double strToDouble(string str, char ch) {
str.erase(remove(str.begin(), str.end(), ch), str.end());
return atof(str.c_str());
}
/**
* The one and only main() method
*/
int main(int argc, char* argv[]) {
// process command line arguments
string csvPath, bidKey;
switch (argc) {
case 2:
csvPath = argv[1];
bidKey = "98109";
break;
case 3:
csvPath = argv[1];
bidKey = argv[2];
break;
default:
csvPath = "eBid_Monthly_Sales.csv";
bidKey = "98109";
}
// Define a timer variable
clock_t ticks;
// Define a binary search tree to hold all bids
BinarySearchTree* bst = new BinarySearchTree(); //initialized here instead in case user doesn't load bids first
Bid bid;
int choice = 0;
while (choice != 9) {
cout << "Menu:" << endl;
cout << " 1. Load Bids" << endl;
cout << " 2. Display All Bids" << endl;
cout << " 3. Find Bid" << endl;
cout << " 4. Remove Bid" << endl;
cout << " 9. Exit" << endl;
cout << "Enter choice: ";
cin >> choice;
switch (choice) {
case 1:
//bst = new BinarySearchTree(); //initialized variable when it was declared because other cases attempt
//use it when it may not be initialized (case 2)
// Initialize a timer variable before loading bids
ticks = clock();
// Complete the method call to load the bids
loadBids(csvPath, bst);
//cout << bst->Size() << " bids read" << endl;
// Calculate elapsed time and display result
ticks = clock() - ticks; // current clock ticks minus starting clock ticks
cout << "time: " << ticks << " clock ticks" << endl;
cout << "time: " << ticks * 1.0 / CLOCKS_PER_SEC << " seconds" << endl;
break;
case 2:
bst->InOrder();
break;
case 3:
ticks = clock();
bid = bst->Search(bidKey);
ticks = clock() - ticks; // current clock ticks minus starting clock ticks
if (!bid.bidId.empty()) {
displayBid(bid);
} else {
cout << "Bid Id " << bidKey << " not found." << endl;
}
cout << "time: " << ticks << " clock ticks" << endl;
cout << "time: " << ticks * 1.0 / CLOCKS_PER_SEC << " seconds" << endl;
break;
case 4:
bst->Remove(bidKey);
break;
}
}
cout << "Good bye." << endl;
return 0;
}
问题是您的二叉搜索树不是 balanced search tree。如果输入已经在bidId上排序，那么你的二叉树基本上就会变成一个很长的链表。由于您使用的是递归，这意味着它需要递归的次数与树中的项数一样多。
解决方案是使您的搜索树平衡，或者更改您的函数以使用迭代而不是递归。后者更容易，但如果你有非常不平衡的树，它仍然意味着你的性能会很差。
我正在做一个学校项目，我需要将一些从 CSV 文件解析的项目加载到二叉搜索树对象中。当我使用包含大约 180 个项目的 CSV 文件时，它工作正常，但是当我使用包含略低于 18,000 个项目的 CSV 文件时，我收到堆栈溢出错误。我想知道是否有人可以提供帮助。这是代码（其中很多是提供给我的）...
#include <iostream>
#include <time.h>
#include "CSVparser.hpp"
using namespace std;
double strToDouble(string str, char ch);
// define a structure to hold bid information
struct Bid {
string bidId; // unique identifier
string title;
string fund;
double amount;
Bid() {
amount = 0.0;
}
};
// FIXED (1): Internal structure for tree node
struct Node {
Bid bid;
Node* left;
Node* right;
//default constructor
Node() {
left = nullptr;
right = nullptr;
}
//constructor which receives bid parameter
Node(Bid curBid) : Node() {
this->bid = curBid;
}
};
class BinarySearchTree {
private:
Node* root;
void addNode(Node* node, Bid bid);
void inOrder(Node* node);
Node* removeNode(Node* node, string bidId);
public:
BinarySearchTree();
virtual ~BinarySearchTree();
void InOrder();
void Insert(Bid bid);
void Remove(string bidId);
Bid Search(string bidId);
};
//constructor
BinarySearchTree::BinarySearchTree() {
// initialize housekeeping variables
root = nullptr;
}
//destructor
BinarySearchTree::~BinarySearchTree() {
// recurse from root deleting every node
}
//Traverse the tree in order
void BinarySearchTree::InOrder() {
this->inOrder(root);
}
//Insert a bid
void BinarySearchTree::Insert(Bid bid) {
// FIXED (2a) Implement inserting a bid into the tree
//if root is null then it gets set to new bid pointer
if (root == nullptr) {
root = new Node(bid);
}
else { //if root isn't null then adds the bid to the tree
this->addNode(root, bid);
}
}
//Remove a bid
void BinarySearchTree::Remove(string bidId) {
// FIXED (4a) Implement removing a bid from the tree
//removes requested node
this->removeNode(root, bidId);
}
//Search for a bid
Bid BinarySearchTree::Search(string bidId) {
// FIXED (3) Implement searching the tree for a bid
//initialize to root because that is where the search begins
Node* current = root;
//search through tree until bottom or until bid is found
while (current != nullptr) {
//if current bid matches search, returns it
if (bidId.compare(current->bid.bidId) == 0) {
return current->bid;
}
//bid parameter is less than current bid, continues searching to the left
if (bidId.compare(current->bid.bidId) < 0) {
current = current->left;
}
else { //bid parameter is greater than current bid, continues searching to the right
current = current->right;
}
}
//if while loop is exited without finding a match, an empty bid is created and returned
Bid bid;
return bid;
}
/**
* Add a bid to some node (recursive)
*
* @param node Current node in tree
* @param bid Bid to be added
*/
void BinarySearchTree::addNode(Node* node, Bid bid) {
// FIXED (2b) Implement inserting a bid into the tree
//if the bid parameter is less than the current node, then add to the left
if (bid.bidId.compare(node->bid.bidId) < 0) {
if (node->left == nullptr) { //if left node is null then it adds the new node here
node->left = new Node(bid);
}
else {
this->addNode(node->left, bid); //recursively calls addnode until bottom is reached
}
}
else { //add to right
if (node->right == nullptr) { //if left node is null then it adds the new node here
node->right = new Node(bid);
}
else {
this->addNode(node->right, bid); //recursively calls addnode until bottom is reached
}
}
}
void BinarySearchTree::inOrder(Node* node) {
if (node != nullptr) {
inOrder(node->left);
cout << node->bid.bidId
<< ": "
<< node->bid.title
<< " | "
<< node->bid.amount
<< " | "
<< node->bid.fund
<< endl;
inOrder(node->right);
}
}
Node* BinarySearchTree::removeNode(Node* node, string bidId) {
//if this node is null then return
if (node == nullptr) {
return node;
}
//if bid parameter is less than current node, searches left recursively
if (bidId.compare(node->bid.bidId) < 0) {
node->left = removeNode(node->left, bidId);
}
else if (bidId.compare(node->bid.bidId) > 0) { //if bid parameter is greater than current node, searches right recursively
node->right = removeNode(node->right, bidId);
}
else { //if its not < or > then its ==, so it needs to be removed since it matches the parameter bidId
//no children so node can just be removed
if ((node->left == nullptr) && (node->right == nullptr)) {
delete node;
node = nullptr;
}
//if one child to left
if ((node->left != nullptr) && (node->right == nullptr)) {
Node* temp = node;
node = node->left;
delete temp;
} //if one child to right
else if ((node->left == nullptr) && (node->right != nullptr)) {
Node* temp = node;
node = node->left;
delete temp;
} //if two children
else {
Node* temp = node;
node = node->right;
while (temp->left != nullptr) {
temp = temp->left;
}
node->bid = temp->bid;
node->right = removeNode(node->right, temp->bid.bidId);
}
}
return node;
}
//============================================================================
// Static methods used for testing
//============================================================================
/**
* Display the bid information to the console (std::out)
*
* @param bid struct containing the bid info
*/
void displayBid(Bid bid) {
cout << bid.bidId << ": " << bid.title << " | " << bid.amount << " | "
<< bid.fund << endl;
return;
}
/**
* Load a CSV file containing bids into a container
*
* @param csvPath the path to the CSV file to load
* @return a container holding all the bids read
*/
void loadBids(string csvPath, BinarySearchTree* bst) {
cout << "Loading CSV file " << csvPath << endl;
// initialize the CSV Parser using the given path
csv::Parser file = csv::Parser(csvPath);
// read and display header row - optional
vector<string> header = file.getHeader();
for (auto const& c : header) {
cout << c << " | ";
}
cout << "" << endl;
try {
// loop to read rows of a CSV file
for (unsigned int i = 0; i < file.rowCount(); i++) {
// Create a data structure and add to the collection of bids
Bid bid;
bid.bidId = file[i][1];
bid.title = file[i][0];
bid.fund = file[i][8];
bid.amount = strToDouble(file[i][4], '$');
//cout << "Item: " << bid.title << ", Fund: " << bid.fund << ", Amount: " << bid.amount << endl;
// push this bid to the end
bst->Insert(bid);
}
} catch (csv::Error &e) {
std::cerr << e.what() << std::endl;
}
}
/**
* Simple C function to convert a string to a double
* after stripping out unwanted char
*
* credit:
*
* @param ch The character to strip out
*/
double strToDouble(string str, char ch) {
str.erase(remove(str.begin(), str.end(), ch), str.end());
return atof(str.c_str());
}
/**
* The one and only main() method
*/
int main(int argc, char* argv[]) {
// process command line arguments
string csvPath, bidKey;
switch (argc) {
case 2:
csvPath = argv[1];
bidKey = "98109";
break;
case 3:
csvPath = argv[1];
bidKey = argv[2];
break;
default:
csvPath = "eBid_Monthly_Sales.csv";
bidKey = "98109";
}
// Define a timer variable
clock_t ticks;
// Define a binary search tree to hold all bids
BinarySearchTree* bst = new BinarySearchTree(); //initialized here instead in case user doesn't load bids first
Bid bid;
int choice = 0;
while (choice != 9) {
cout << "Menu:" << endl;
cout << " 1. Load Bids" << endl;
cout << " 2. Display All Bids" << endl;
cout << " 3. Find Bid" << endl;
cout << " 4. Remove Bid" << endl;
cout << " 9. Exit" << endl;
cout << "Enter choice: ";
cin >> choice;
switch (choice) {
case 1:
//bst = new BinarySearchTree(); //initialized variable when it was declared because other cases attempt
//use it when it may not be initialized (case 2)
// Initialize a timer variable before loading bids
ticks = clock();
// Complete the method call to load the bids
loadBids(csvPath, bst);
//cout << bst->Size() << " bids read" << endl;
// Calculate elapsed time and display result
ticks = clock() - ticks; // current clock ticks minus starting clock ticks
cout << "time: " << ticks << " clock ticks" << endl;
cout << "time: " << ticks * 1.0 / CLOCKS_PER_SEC << " seconds" << endl;
break;
case 2:
bst->InOrder();
break;
case 3:
ticks = clock();
bid = bst->Search(bidKey);
ticks = clock() - ticks; // current clock ticks minus starting clock ticks
if (!bid.bidId.empty()) {
displayBid(bid);
} else {
cout << "Bid Id " << bidKey << " not found." << endl;
}
cout << "time: " << ticks << " clock ticks" << endl;
cout << "time: " << ticks * 1.0 / CLOCKS_PER_SEC << " seconds" << endl;
break;
case 4:
bst->Remove(bidKey);
break;
}
}
cout << "Good bye." << endl;
return 0;
}
问题是您的二叉搜索树不是 balanced search tree。如果输入已经在bidId上排序，那么你的二叉树基本上就会变成一个很长的链表。由于您使用的是递归，这意味着它需要递归的次数与树中的项数一样多。
解决方案是使您的搜索树平衡，或者更改您的函数以使用迭代而不是递归。后者更容易，但如果你有非常不平衡的树，它仍然意味着你的性能会很差。