我的二进制树程序是否达到溢出/递归最大值

Question

#include <iostream>
using namespace std;
struct Node{
bool flag;
char letter;
Node* left;
Node* right;
};
typedef Node* Nodeptr;
int stop = 0;
void splitString(string sequence, Nodeptr branch){
//cout << sequence << " ";
//cout << sequence.size() << endl;
if(stop == 20) return;
else stop++;
if(sequence.size() == 1){
branch->flag = true;
branch->letter = sequence[0];
}
else{
int half = sequence.size()/2;
Node* left = new Node;
Node* right = new Node;
branch->flag = false;
branch->left = left;
branch->right = right;
splitString(sequence.substr(0, half), left);
splitString(sequence.substr(half), right);
}
return;
}
void print(Nodeptr root){
if(root->flag)
cout << root->letter;
else{
print(root->left);
print(root->right);
}
return;
}
int main() {
std::cout << "Hello World!n";
Nodeptr tree = new Node;
splitString("Heaven on ", tree);
print(tree);
//the above two lines run fine
Nodeptr tree2 = new Node;
splitString("Heaven on E", tree2); //this code will run fine
//print(tree2); //this code will give me an EXITED, SEGMENTATION FAULT error 
}

考虑到两条线：

splitString("Heaven on ", tree);
print(tree);

运行良好，但这些没有：

splitString("Heaven on E", tree2);
//print(tree2); //this code will give me an EXITED, SEGMENTATION FAULT error 

我开始认为我已经达到了最大递归深度。我查看了构建和遍历二进制树的代码，但没有发现任何问题。错误的原因是什么？谢谢

Answer 1

原因有二：

1. 您正在使用全局，这是一种非常糟糕的做法，例如，在这种情况下，您在第一个splitString之后没有重置它
2. 您没有以正确的方式管理字符串大小为0的情况

这是splitString的一种可能实现，它可以工作(没有全局(：

void splitString(string sequence, Nodeptr branch){
if(sequence.size() == 1){
branch->flag = true;
branch->letter = sequence[0];
}
else if (sequence.size() > 1){
int half = sequence.size()/2;
Node* left = new Node;
Node* right = new Node;
branch->flag = false;
branch->left = left;
branch->right = right;
splitString(sequence.substr(0, half), left);
splitString(sequence.substr(half), right);
}
else {
branch->flag = true;
branch->letter = '';
}
}

当然有更好的方法可以做到这一点，我鼓励您更改数据结构以实现这一点(例如，不要使用flag来标记树的叶子，只需检查是否设置了left或nullptr(