Достигает ли моя двоичная программа переполнения / рекурсивного максимума?

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 = '\0';
    }
}

Конечно, есть лучший способ сделать это, и я рекомендую вам изменить структуру данных, чтобы это произошло (например, не используйте flag, чтобы пометить листья дерево, просто проверьте, установлено ли left или nullptr)