Как сделать эту функцию поиска нерекурсивной?

Я пытаюсь превратить эту рекурсивную функцию в нерекурсивную. Это функция поиска из двоичного дерева поиска. Я знаю, что естественно сделать его рекурсивным, но в учебных целях я хотел бы сделать его нерекурсивным. Как я мог это сделать? Заранее спасибо!

    bool Search(BstNode* root, string data) {

    if (root == NULL) return false;
    else if (root->data == data) return true;
    else if (data <= root->data) return Search(root->left, data);
    else return Search(root->right, data);

}

c++ recursion binary-tree binary-search-tree non-recursive
person Adam Bunch    schedule 11.10.2016    source источник
comment
Настройте переменную вверху для корня. Превратите его в петлю. Обновите корень до root->left или root->right перед следующей итерацией.   -  person BoBTFish    schedule 11.10.2016

Ответы (2)


arrow_upward
5
arrow_downward

Вот механический способ сделать рекурсивный алгоритм нерекурсивным.

bool Search(BstNode* root, string data) {
  if (root == NULL) return false;
  else if (root->data == data) return true;
  else if (data <= root->data) return Search(root->left, data);
  else return Search(root->right, data);
}

Объедините состояние (аргументы и локальные переменные):

bool Search(BstNode* root, string data) {
  struct State {
    BstNode* root;
    string data;
  };
  State state{root, data};

  if (state.root == NULL) return false;
  else if (state.root->data == state.data) return true;
  else if (data <= state.root->data) return Search(state.root->left, state.data);
  else return Search(state.root->right, state.data);
}

завернуть тело в цикл:

bool Search(BstNode* root, string data) {
  struct State {
    BstNode* root;
    string data;
  };
  State state{root, data};

  while(true) {
    if (state.root == NULL) return false;
    else if (state.root->data == state.data) return true;
    else if (data <= state.root->data) return Search(state.root->left, data);
    else return Search(state.root->right, data);
  }
}

Замените случай, когда вы завершаете рекурсию (возвращаете recursive_call) с изменением состояния и продолжаете:

bool Search(BstNode* root, string data) {
  struct State {
    BstNode* root;
    string data;
  };
  State state{root, data};

  while(true) {
    if (state.root == NULL) return false;
    else if (state.root->data == state.data) return true;
    else if (data <= state.root->data) {
      state = {state.root->left, state.data};
      continue;
    } else  {
      state = {state.root->right, state.data};
      continue;
    }
  }
}

Теперь, если есть еще какие-либо рекурсивные вызовы, которые не являются return recursive_call, добавьте ручной стек состояния и нажмите/вытолкните его вместо изменения обратно. Включите расположение состояния возврата в виде void** в код с метками.

Здесь это не требуется, поэтому я не буду этого делать.

person Yakk - Adam Nevraumont    schedule 11.10.2016
comment
Это действительно ломает его и делает его простым для меня. Благодарю вас! - person Adam Bunch; 11.10.2016

arrow_upward
1
arrow_downward

Обычно вы можете сделать рекурсивную функцию в целом итеративной, по существу «поместив» рекурсивные вызовы в стек, а затем используя

while !stack.is_empty() do stack.pop() типа того

поскольку это, по сути, то, что будет делать компилятор, учитывая, что рекурсия не происходит на уровне машинного кода.

person Alex D    schedule 11.10.2016