C++二叉樹遍歷

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

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

層序遍歷

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

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

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

1.   代碼實(shí)現(xiàn)

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

binary_tree_bfs.cpp

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

2.   復(fù)雜度分析

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

前序、中序、后序遍歷

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

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

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

 代碼實(shí)現(xiàn)

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

binary_tree_dfs.cpp

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

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

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

Note

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

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

1. “遞”表示開啟新方法，程序在此過程中訪問下一個(gè)節(jié)點(diǎn)。
2. “歸”表示函數(shù)返回，代表當(dāng)前節(jié)點(diǎn)已經(jīng)訪問完畢。

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

2.   復(fù)雜度分析

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