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

Question

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

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

将尾端递归 (return 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 的递归调用，请添加一个手动状态堆栈并 push/pop 它而不是更改后退。在带标签的代码中将 return 状态的位置作为 void** 包括在内。

这里不需要，所以我不会费心去做。

Answer 2

您通常可以通过本质上 'putting' 对堆栈的递归调用，然后使用

使递归函数具有一般的迭代性

while !stack.is_empty() do stack.pop() 那种东西

因为如果递归不会发生在机器代码级别，这基本上就是编译器要做的事情

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

How to make this search function non-recursive?

c++

recursion

binary-tree

non-recursive

binary-search-tree