C++二叉樹遍歷

圖 7-11   前序遍歷的遞歸過程從物理結構的角度來看，樹是一種基于鏈表的數據結構，因此其遍歷方式是通過指針逐個訪問節(jié)點。然而，樹是一種非線性數據結構，這使得遍歷樹比遍歷鏈表更加復雜，需要借助搜索算法來實現。

二叉樹常見的遍歷方式包括層序遍歷、前序遍歷、中序遍歷和后序遍歷等。

層序遍歷

如圖 7-9 所示，「層序遍歷 level-order traversal」從頂部到底部逐層遍歷二叉樹，并在每一層按照從左到右的順序訪問節(jié)點。

層序遍歷本質上屬于「廣度優(yōu)先遍歷 breadth-first traversal」，它體現了一種“一圈一圈向外擴展”的逐層遍歷方式。

圖 7-9   二叉樹的層序遍歷

1.   代碼實現

廣度優(yōu)先遍歷通常借助“隊列”來實現。隊列遵循“先進先出”的規(guī)則，而廣度優(yōu)先遍歷則遵循“逐層推進”的規(guī)則，兩者背后的思想是一致的。

binary_tree_bfs.cpp

/* 層序遍歷 */
vector<int> levelOrder(TreeNode *root) {
    // 初始化隊列，加入根節(jié)點
    queue<TreeNode *> queue;
    queue.push(root);
    // 初始化一個列表，用于保存遍歷序列
    vector<int> vec;
    while (!queue.empty()) {
        TreeNode *node = queue.front();
        queue.pop();              // 隊列出隊
        vec.push_back(node->val); // 保存節(jié)點值
        if (node->left != nullptr)
            queue.push(node->left); // 左子節(jié)點入隊
        if (node->right != nullptr)
            queue.push(node->right); // 右子節(jié)點入隊
    }
    return vec;
}

2.   復雜度分析

• 時間復雜度 O(n) ：所有節(jié)點被訪問一次，使用 O(n) 時間，其中 n 為節(jié)點數量。
• 空間復雜度 O(n) ：在最差情況下，即滿二叉樹時，遍歷到最底層之前，隊列中最多同時存在 (n+1)/2 個節(jié)點，占用 O(n) 空間。

前序、中序、后序遍歷

相應地，前序、中序和后序遍歷都屬于「深度優(yōu)先遍歷 depth-first traversal」，它體現了一種“先走到盡頭，再回溯繼續(xù)”的遍歷方式。

圖 7-10 展示了對二叉樹進行深度優(yōu)先遍歷的工作原理。深度優(yōu)先遍歷就像是繞著整個二叉樹的外圍“走”一圈，在每個節(jié)點都會遇到三個位置，分別對應前序遍歷、中序遍歷和后序遍歷。

圖 7-10   二叉搜索樹的前、中、后序遍歷

 代碼實現

深度優(yōu)先搜索通?；谶f歸實現：

binary_tree_dfs.cpp

/* 前序遍歷 */
void preOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    // 訪問優(yōu)先級：根節(jié)點 -> 左子樹 -> 右子樹
    vec.push_back(root->val);
    preOrder(root->left);
    preOrder(root->right);
}

/* 中序遍歷 */
void inOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    // 訪問優(yōu)先級：左子樹 -> 根節(jié)點 -> 右子樹
    inOrder(root->left);
    vec.push_back(root->val);
    inOrder(root->right);
}

/* 后序遍歷 */
void postOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    // 訪問優(yōu)先級：左子樹 -> 右子樹 -> 根節(jié)點
    postOrder(root->left);
    postOrder(root->right);
    vec.push_back(root->val);
}

Note

深度優(yōu)先搜索也可以基于迭代實現，有興趣的同學可以自行研究。

圖 7-11 展示了前序遍歷二叉樹的遞歸過程，其可分為“遞”和“歸”兩個逆向的部分。

1. “遞”表示開啟新方法，程序在此過程中訪問下一個節(jié)點。
2. “歸”表示函數返回，代表當前節(jié)點已經訪問完畢。

圖 7-11   前序遍歷的遞歸過程

2.   復雜度分析

• 時間復雜度 O(n) ：所有節(jié)點被訪問一次，使用 O(n) 時間。
• 空間復雜度 O(n) ：在最差情況下，即樹退化為鏈表時，遞歸深度達到 n ，系統(tǒng)占用 O(n) 棧幀空間。