深度优先遍历类似于二叉树的什么遍历

一、前言

深度优先遍历（Depth First Search）是图论中的经典算法之一。在遍历图或树时，深度优先遍历通过递归的方式首先访问最深的节点，然后回溯访问其他节点。深度优先遍历类似于二叉树的前序、中序和后序遍历，它们都是通过递归的方式访问节点的。本篇文章将主要介绍如何使用深度优先遍历来遍历类似于二叉树的数据结构。

二、深度优先遍历原理

深度优先遍历的原理非常简单，它通过递归的方式遍历树的节点，先访问节点的根节点，然后再遍历它的左子树和右子树。这样就会对整个树进行深度遍历，所以叫做深度优先遍历。

void dfs(Node node) {
    if (node == null) {
        return;
    }
    visit(node);
    dfs(node.left);
    dfs(node.right);
}

代码中的visit(node)代表访问节点的操作，dfs(node.left)和dfs(node.right)代表递归地遍历左子树和右子树。

三、类似于二叉树的数据结构

很多数据结构都类似于二叉树，它们可以视为一棵树或森林。其中比较典型的有二叉树、N叉树、图等数据结构。我们以下面的二叉树为例来介绍如何使用深度优先遍历来遍历类似于二叉树的数据结构。

   1
  / \
 2   3
/ \   \
4   5   6

对于上面的二叉树，深度优先遍历的顺序是1、2、4、5、3、6。接下来我们将分别介绍三种不同的深度优先遍历方法：

四、先序遍历

先序遍历是指先访问根节点，再遍历左子树和右子树的顺序。对于上面的二叉树，先序遍历的顺序是1、2、4、5、3、6。先序遍历可以用递归或非递归的方式实现。

void preOrder(Node node) {
    if (node == null) {
        return;
    }
    visit(node);
    preOrder(node.left);
    preOrder(node.right);
}

递归实现方式非常简单，代码中的visit(node)代表访问节点的操作，preOrder(node.left)和preOrder(node.right)代表递归地遍历左子树和右子树。

非递归实现方式需要使用栈（Stack）来保存节点，具体实现方式如下：

void preOrderNonRecursive(Node node) {
    if (node == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    stack.push(node);
    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        visit(cur);
        if (cur.right != null) {
            stack.push(cur.right);
        }
        if (cur.left != null) {
            stack.push(cur.left);
        }
    }
}

代码中使用栈来模拟递归实现的过程，所有未访问的节点都被压入栈中，每次从栈中弹出一个节点并访问，然后将其右子节点和左子节点依次压入栈中。由于栈的先进后出特性，所以在访问左子树时会优先访问。

五、中序遍历

中序遍历是指先遍历左子树，再访问根节点，最后遍历右子树的顺序。对于上面的二叉树，中序遍历的顺序是4、2、5、1、3、6。中序遍历的递归实现方式和先序遍历很类似。

void inOrder(Node node) {
    if (node == null) {
        return;
    }
    inOrder(node.left);
    visit(node);
    inOrder(node.right);
}

非递归实现方式需要使用栈（Stack）来保存节点，具体实现方式如下：

void inOrderNonRecursive(Node node) {
    if (node == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    Node cur = node;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        visit(cur);
        cur = cur.right;
    }
}

代码中使用栈来模拟递归实现的过程，所有左子树都会被压入栈中，每次从栈中弹出一个节点并访问，然后将右子节点赋值给当前节点，并进入下一次循环。

六、后序遍历

后序遍历是指先遍历左子树，再遍历右子树，最后访问根节点的顺序。对于上面的二叉树，后序遍历的顺序是4、5、2、6、3、1。后序遍历的递归实现方式和先序遍历和中序遍历有所区别。

void postOrder(Node node) {
    if (node == null) {
        return;
    }
    postOrder(node.left);
    postOrder(node.right);
    visit(node);
}

非递归实现方式需要使用栈（Stack）来保存节点，具体实现方式如下：

void postOrderNonRecursive(Node node) {
    if (node == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    Node cur = node;
    Node lastVisit = null;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.peek();
        if (cur.right == null || cur.right == lastVisit) {
            visit(cur);
            stack.pop();
            lastVisit = cur;
            cur = null;
        } else {
            cur = cur.right;
        }
    }
}

代码中使用栈来模拟递归实现的过程，所有左子树都会被压入栈中，当没有右子节点时，说明这个节点的左右子树都已经访问完毕，可以访问当前节点。然后将当前节点标记为上一个访问的节点，并将其弹出栈。如果当前节点有右子结点，则将其赋值给当前节点，并进入下一次循环。

七、总结

深度优先遍历是图论中的经典算法之一，可以通过递归或非递归的方式使用。类似于二叉树的数据结构也可以通过深度优先遍历来遍历，具体实现方式包括先序遍历、中序遍历和后序遍历。使用不同的遍历方式可以得到不同的结果，根据具体的需求来选择合适的遍历方式是很重要的。