数据结构递归与非递归

非递归DFS是使用堆栈（stack）实现的深度优先搜索算法。首先，将起始节点压入堆栈中，然后进入循环，直到堆栈为空。在循环中，取出堆栈顶部的节点，遍历其所有的邻居节点，并将邻居节点压入堆栈中。同时，输出当前节点的值。这样就能按照深度优先的方式遍历整个图或树结构。

递归DFS则是通过递归函数实现的深度优先搜索算法。首先，从起始节点开始，遍历其所有的邻居节点，并对每个邻居节点递归调用DFS函数。在DFS函数中，再次遍历当前节点的邻居节点，并进行递归调用。不断递归下去，直到没有未访问的邻居节点为止。在递归的过程中，输出每个节点的值。

非递归DFS和递归DFS都是常用的图遍历方法，用于解决一些与图相关的问题。

相关问题

数据结构递归和非递归遍历二叉树的报告

二叉树是一种非常基础和重要的数据结构，对于理解递归和非递归的遍历方式也有很大的帮助。本文将介绍二叉树的前序、中序、后序的递归和非递归遍历方式，并对它们进行比较和分析。

### 前序遍历

前序遍历的顺序是：先遍历根节点，然后遍历左子树，最后遍历右子树。递归方式的代码如下：

def preorder_recursive(root):
    if not root:
        return
    print(root.val)
    preorder_recursive(root.left)
    preorder_recursive(root.right)

非递归方式的代码如下：

def preorder_iterative(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)

可以看出，非递归方式使用了一个栈来模拟递归过程。首先把根节点入栈，然后每次取出栈顶元素，并打印它的值。如果有右孩子，就把右孩子入栈；如果有左孩子，就把左孩子入栈。这样，就能保证在遍历到一个节点时，它的左子树已经全部遍历完了。

### 中序遍历

中序遍历的顺序是：先遍历左子树，然后遍历根节点，最后遍历右子树。递归方式的代码如下：

def inorder_recursive(root):
    if not root:
        return
    inorder_recursive(root.left)
    print(root.val)
    inorder_recursive(root.right)

非递归方式的代码如下：

def inorder_iterative(root):
    if not root:
        return
    stack = []
    node = root
    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            node = stack.pop()
            print(node.val)
            node = node.right

可以看出，非递归方式同样使用了一个栈来模拟递归过程。首先把根节点入栈，并把指针指向左子树的最底层。然后每次取出栈顶元素，并打印它的值。如果有右孩子，就把右孩子入栈；如果没有右孩子，就返回到它的父节点。

### 后序遍历

后序遍历的顺序是：先遍历左子树，然后遍历右子树，最后遍历根节点。递归方式的代码如下：

def postorder_recursive(root):
    if not root:
        return
    postorder_recursive(root.left)
    postorder_recursive(root.right)
    print(root.val)

非递归方式的代码如下：

def postorder_iterative(root):
    if not root:
        return
    stack = [root]
    res = []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return res[::-1]

可以看出，非递归方式同样使用了一个栈来模拟递归过程。首先把根节点入栈，在遍历完左子树和右子树之后，把它的值加入到结果列表中。最后，把结果列表翻转，就得到了后序遍历的结果。

### 比较和分析

递归和非递归遍历方式的时间复杂度都是 O(n)，空间复杂度也都是 O(n)。但是，非递归方式需要使用一个栈来模拟递归过程，所以空间复杂度比递归方式要高。而且，非递归方式的代码比较难理解和实现，需要仔细分析。

另外，对于前序和后序遍历，非递归方式的代码比递归方式要复杂一些，需要添加一些特判来保证遍历顺序的正确性。而中序遍历的非递归方式比较简单，只需要一个栈和一个指针即可。

总的来说，递归方式比较简洁和易于理解，但是可能会因为递归深度过大而导致栈溢出。非递归方式虽然可以避免这个问题，但是代码比较复杂，需要一定的实现技巧和思维难度。所以，在实际应用中，根据具体情况选择合适的遍历方式比较重要。

图的深度优先遍历非递归 数据结构

图的深度优先遍历非递归的数据结构通常使用栈来保存中间变量。栈是一种后进先出（LIFO）的数据结构，它可以保存当前节点的信息以便后续处理。在深度优先遍历中，我们首先将起始节点入栈，然后依次将与当前节点相连的未访问过的节点入栈，直到没有未访问的相邻节点。此时，我们将栈顶节点出栈，并将其作为当前节点继续遍历。重复这个过程，直到栈为空为止。

具体实现时，我们可以使用一个辅助栈来保存未访问的节点。每次从栈中弹出一个节点时，我们将其标记为已访问，并将其未访问的相邻节点入栈。这样，我们就可以按照深度优先的顺序遍历图中的所有节点。

需要注意的是，为了避免重复遍历已经访问过的节点，我们需要在节点被访问时将其标记为已访问。这可以通过一个额外的布尔数组或哈希表来实现。

综上所述，图的深度优先遍历非递归的数据结构是栈。我们可以使用栈来保存未访问的节点，并按照深度优先的顺序遍历图中的所有节点。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [二叉树的深度优先遍历非递归深度解析](https://blog.csdn.net/zhanghuaichao/article/details/124243582)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]