c++ - 如何使此搜索功能非递归？

Question

我正在尝试将此递归函数转换为非递归函数。这是一个来自二叉搜索树的搜索函数。我知道使它递归是很自然的，但出于学习目的，我想让它成为非递归的。我怎么能这样做？提前致谢!

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

}

Answer 1

这是使递归算法成为非递归算法的机械方法。

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** 包含在内。

这不是必需的，所以我不会费心去做。