使用非递归方法,采用c++
时间: 2024-09-10 09:16:03 浏览: 17
非递归方法是指在编程中,不使用递归调用自身的方式来解决问题,而是利用循环结构或栈等数据结构来模拟递归的过程。在C++中,非递归方法通常使用循环结构如for、while等来实现。以下是一个使用非递归方法实现的简单例子:遍历树结构。
在C++中,遍历树结构通常有三种方式:前序遍历、中序遍历和后序遍历。这里我们以二叉树的前序遍历为例,使用栈来模拟递归过程。
```cpp
#include <iostream>
#include <stack>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void preorderTraversal(TreeNode* root) {
if (root == nullptr) return;
std::stack<TreeNode*> stack;
stack.push(root);
while (!stack.empty()) {
TreeNode* node = stack.top();
stack.pop();
std::cout << node->val << " "; // 访问节点
// 注意先右后左,这样左子树会先被处理
if (node->right) stack.push(node->right);
if (node->left) stack.push(node->left);
}
}
int main() {
// 构建一个简单的测试二叉树
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// 非递归前序遍历
preorderTraversal(root);
return 0;
}
```
在这个例子中,我们创建了一个二叉树,并通过栈实现了前序遍历的非递归方法。栈中存储的是将要访问的节点,按照前序遍历的顺序,先访问根节点,然后将其右子节点和左子节点依次入栈,最后按照栈的后进先出(LIFO)的规则访问节点。