简记二叉树的遍历

本文简记二叉树的遍历,笔记目的。

深度优先 dfs

深度优先遍历二叉树,可分为:前序(先序)、中序 和 后序 三种情况。

前中后序遍历

前中后序的遍历效果,一图以蔽之,见下方,快捷的记忆方式可以有两种:

  1. 节点边上小红点的位置,各自代表一种遍历序。
  2. 遍历序就是节点映射到蓝色数轴上的顺序,只是数轴的方向和摆放位置不同。

    特殊地,二叉搜索树的中序遍历是有序的(下图中的就是二叉搜索树)。

递归写法:

二叉树前中后序的递归写法 - C++
// 先序遍历/前序遍历 (递归)
void PreOrder(Node* root, vector<int>& ans) {
    if (root == nullptr) return;
    ans.push_back(root->val);
    PreOrder(root->left, ans);
    PreOrder(root->right, ans);
}

// 中序遍历 (递归)
void InOrder(Node* root, vector<int>& ans) {
    if (root == nullptr) return;
    InOrder(root->left, ans);
    ans.push_back(root->val);
    InOrder(root->right, ans);
}

// 后序遍历 (递归)
void PostOrder(Node* root, vector<int>& ans) {
    if (root == nullptr) return;
    PostOrder(root->left, ans);
    PostOrder(root->right, ans);
    ans.push_back(root->val);
}

非递归写法

建立一个栈来模拟递归,存储两个信息:

  1. node - 等待处理的节点
  2. visited - 此节点是否访问过

每个节点会入栈两次:先访问,再处理

下方是对前序遍历的一部分过程的栈模拟示意图,其中黄色表示第一次访问、绿色表示第二次访问(即 visitedtrue 的情况):

统一的非递归写法来描述前中后三种遍历序,不同点仅在于父子节点入栈的顺序

二叉树前中后序的非递归写法 - C++
// 先序遍历/前序遍历 (非递归)
vector<int> PreOrder(Node* root) {
    if (root == nullptr) return {};
    vector<int> ans;
    stack<pair<Node*, bool>> s;
    s.push({root, false});

    while (!s.empty()) {
        auto [node, visited] = s.top();
        s.pop();
        if (node == nullptr) continue;
        if (!visited) {
            // 最后再访问孩子
            s.push({node->right, false});
            s.push({node->left, false});
            // 先处理父节点
            s.push({node, true});
        } else {
            // 第二次访问时执行处理
            ans.push_back(node->val);
        }
    }
    return ans;
}

// 中序遍历 (非递归)
vector<int> InOrder(Node* root) {
    if (root == nullptr) return {};
    vector<int> ans;
    stack<pair<Node*, bool>> s;
    s.push({root, false});

    while (!s.empty()) {
        auto [node, visited] = s.top();
        s.pop();
        if (node == nullptr) continue;
        if (!visited) {
            // 最后访问右孩子
            s.push({node->right, false});
            // 再处理父节点
            s.push({node, true});
            // 先访问左孩子
            s.push({node->left, false});
        } else {
            // 第二次访问时执行处理
            ans.push_back(node->val);
        }
    }
    return ans;
}

// 后序遍历 (非递归)
vector<int> PostOrder(Node* root) {
    if (root == nullptr) return {};
    vector<int> ans;
    stack<pair<Node*, bool>> s;
    s.push({root, false});

    while (!s.empty()) {
        auto [node, visited] = s.top();
        s.pop();
        if (node == nullptr) continue;
        if (!visited) {
            // 最后处理父节点
            s.push({node, true});
            // 再访问右孩子
            s.push({node->right, false});
            // 先访问左孩子
            s.push({node->left, false});
        } else {
            // 第二次访问时执行处理
            ans.push_back(node->val);
        }
    }
    return ans;
}

广度优先 bfs

和图一样,广度优先要借助一个队列来实现,是一种自顶向下逐层遍历的过程

处理完当前节点后,弹出它,并把其孩子节点顺序加入队尾。

是一种 边消费、边生产 的过程。

二叉树的广度优先遍历 - C++
vector<int> BFS(Node* root) {
    vector<int> ans;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        if (node == nullptr) continue;
        ans.push_back(node->val);
        // 处理下一层
        q.push(node->left);
        q.push(node->right);
    }
    return ans;
}

层序遍历

要求输出一个二维数组,把每一层的节点放在一起,然后返回所有层作为答案。

例如,下图的二叉树的层序遍历结果是 [[4], [2,6], [1,3,5,7]]

在广度优先遍历基础上,拆一层子循环,每当消费完上一层的节点后,新开一层

二叉树的层序遍历 - C++
vector<vector<int>> LevelOrder(Node* root) {
    if (root == nullptr) return {{}};

    vector<vector<int>> ans;
    ans.push_back({});

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        int n = q.size(); // 上一层的数量
        while (n--) {
            auto node = q.front();
            q.pop();

            if (node == nullptr) continue;

            ans.back().push_back(node->val);

            // 处理下一层
            if (node->left != nullptr) q.push(node->left);
            if (node->right != nullptr) q.push(node->right);
        }
        // 新建一层
        if (!q.empty()) ans.push_back({});
    }
    return ans;
}

本文二叉树的所有代码已放到 github:code-snippets/binary-tree

(完)

本文原始链接地址: https://writings.sh/post/binary-tree-traversal

王超 ·
微信扫码赞赏
评论 首页 | 归档 | 算法 | 订阅