树的非递归遍历：深度优先搜索（DFS）与广度优先搜索（BFS）详解

在计算机科学中，树的遍历是树数据结构的一个重要操作。常见的树遍历方法有深度优先搜索（DFS）和广度优先搜索（BFS）。这两种方法都可以用于非递归地遍历树，即不使用递归函数来访问树的节点。
一、深度优先搜索（DFS）
深度优先搜索是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
以下是使用Python实现的DFS非递归遍历二叉树的示例代码：

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def dfs_non_recursive(root):
if not root:
return []
stack, output = [root, ], []
while stack:
node = stack.pop()
output.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return output

这段代码中，我们使用一个栈来模拟递归的过程。首先将根节点放入栈中，然后在循环中不断弹出栈顶元素，并将其值加入到输出列表中。接着将该节点的右子节点和左子节点按顺序放入栈中。由于栈是后进先出的数据结构，因此在处理节点时能够保证先处理左子节点再处理右子节点，满足了DFS的先序遍历顺序。
二、广度优先搜索（BFS）
广度优先搜索是另一种树的遍历算法。它从根节点开始，然后探索所有相邻的节点，然后是它们的邻居节点，依此类推。这个过程会持续进行，直到所有可从根节点到达的节点都被访问过。与DFS不同，BFS会尽可能广地搜索树的分支。
以下是使用Python实现的BFS非递归遍历二叉树的示例代码：

from collections import deque
def bfs_non_recursive(root):
if not root:
return []
queue, output = deque([root, ]), []
while queue:
node = queue.popleft()
output.append(node.val)
if node.right:
queue.append(node.right)
if node.left:
queue.append(node.left)
return output

在这段代码中，我们使用一个双端队列来模拟递归的过程。首先将根节点放入队列中，然后在循环中不断从队列的左端弹出一个节点，并将其值加入到输出列表中。接着将该节点的右子节点和左子节点按顺序放入队列中。由于队列是先进先出的数据结构，因此在处理节点时能够保证先处理左子节点再处理右子节点，满足了BFS的先序遍历顺序。
总结：
深度优先搜索（DFS）和广度优先搜索（BFS）是两种常见的树的遍历算法。通过非递归的方式实现这两种算法，我们可以利用栈和队列这两种数据结构来模拟递归的过程。在实际应用中，我们可以根据具体的需求选择适合的遍历算法来处理树结构的问题。