非递归深度优先遍历代码

非递归深度优先遍历（Non-recursive depth-first traversal）可以借助栈（stack）来实现，以下是基于栈实现的非递归深度优先遍历代码：
def dfs_non_recursive(root):
if not root:
return

stack = [root]
while stack:
node = stack.pop()
print(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
登录后复制
解析：

首先判断根节点是否为空，若为空则返回。
创建一个栈，并将根节点放入栈中。
当栈不为空时，弹出栈顶元素（即当前节点），并输出当前节点的值。
如果当前节点有右子节点，则将右子节点入栈。
如果当前节点有左子节点，则将左子节点入栈。
重复步骤 3-5，直到栈为空。

需要注意的是，此处的代码是针对二叉树的深度优先遍历，对于其他类型的图或树，需要根据实际情况进行修改。

相关问题

c++非递归深度优先遍历代码

下面是C++实现非递归深度优先遍历的代码：
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

// 定义节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<int> dfs(TreeNode* root) {
vector<int> res;
if (!root) {
return res;
}

stack<TreeNode*> s;
s.push(root);

while (!s.empty()) {
TreeNode* cur = s.top();
s.pop();
res.push_back(cur->val);

if (cur->right) {
s.push(cur->right);
}

if (cur->left) {
s.push(cur->left);
}
}

return res;
}

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);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);

vector<int> res = dfs(root);
for (auto val : res) {
cout << val << " ";
}

return 0;
}
登录后复制
这里我们使用了一个栈来保存节点，从而实现了非递归的深度优先遍历。具体的实现细节可以参考代码中的注释。

树的非递归深度优先遍历算法伪代码

树结构非递归深度优先遍历算法伪代码
为了实现树的非递归深度优先遍历，通常会使用显式的栈数据结构来模拟递归过程。下面是一个详细的非递归深度优先搜索（DFS）伪代码：
def iterative_DFS(root):
if root is None:
return

stack = [] # 初始化一个空栈
stack.append(root) # 将根节点压入栈中

while stack:
node = stack.pop() # 取出并移除栈顶元素

visit(node) # 访问当前节点
mark node as visited # 标记该节点已访问

for child in reversed(node.children): # 假设 children 是子节点列表
if not is_visited(child): # 如果子节点未被访问过
stack.append(child) # 将其压入栈中等待后续处理
登录后复制
在这个过程中，程序通过维护一个栈来保存待访问的节点，并按照后进先出的原则依次弹出栈顶元素进行访问[^1]。
对于每个取出的节点，首先标记为已访问状态以防止重复访问；接着将其所有尚未访问过的子节点按逆序加入栈中——这是因为栈具有后进先出特性，在这里采用逆序可以使得实际执行顺序是从左至右逐层深入地遍历整棵树[^5]。