如何使这个搜索功能非递归？

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**在带有标签的代码中包含返回状态的位置.

这不是必需的,所以我不打算这样做.