深度優先遍歷類似於二叉樹的什麼遍歷

一、前言

深度優先遍歷（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;
        }
    }
}

代碼中使用棧來模擬遞歸實現的過程，所有左子樹都會被壓入棧中，當沒有右子節點時，說明這個節點的左右子樹都已經訪問完畢，可以訪問當前節點。然後將當前節點標記為上一個訪問的節點，並將其彈出棧。如果當前節點有右子結點，則將其賦值給當前節點，並進入下一次循環。

七、總結

深度優先遍歷是圖論中的經典算法之一，可以通過遞歸或非遞歸的方式使用。類似於二叉樹的數據結構也可以通過深度優先遍歷來遍歷，具體實現方式包括先序遍歷、中序遍歷和後序遍歷。使用不同的遍歷方式可以得到不同的結果，根據具體的需求來選擇合適的遍歷方式是很重要的。