二叉树层次遍历及应用

namelij

关注

发布于: 1 小时前

关注公众号:[虫爸说说]，回复[资料]，免费获取
添加 vx 好友:chongbashuoshuo（虫爸说说的中文拼音），一起聊架构，扯技术。

大家好，我是虫爸。在上一篇文章中一文弄懂二叉树的三种遍历方式，分别从递归和非递归的角度，讲解、分析以及实现了三种遍历方式，今天给大家分享另外一种二叉树的遍历方式**层次遍历**。

层次遍历

所谓层次遍历，顾名思义就是指从二叉树的第一层（根节点）开始，从上至下逐层遍历，在同一层中，则按照从左到右的顺序对节点逐个访问。在逐层遍历过程中，按从顶层到底层的次序访问树中元素，在同一层中，从左到右进行访问。

图一二叉树

以上图【图一】中的二叉树为例：

第一层：A
第二层：B C
第三层：D E F G 那么其层次遍历的结果，就是：A B C D E F G

非递归实现

思路：

将根节点放入队列
判断队列是否为空
获取队列大小 s，从队列头中出队 s 个元素，同时将 s 个元素的非空左右节点加入队列

根节点入队

图二根节点入队

上一层出队，其孩子节点入队

如上图所示，根节点 A 出队，其子节点 B 和 C 入队

第二层出队，其孩子节点入队

第二层节点 B C 出队，其子节点 D E F G 入队

第三层出队

图五

队列中的节点 D E F G 出队，由于其没有子节点，遍历完成。

思考点：如何判断某一层是否完全放入队列呢？那就是确保队列中的元素仅仅保存一层。

上面可能理解起来有点困难。在一开始的时候，根节点 A 入队，那么此时队列中的元素为第一层的所有节点(第一层仅有一个根节点 A)。然后判断队列是否为空，获取队列元素个数 s，从队列出弹出 s 个元素，同时将这些元素的子节点加入队列。

代码实现如下：

struct TreeNode {  TreeNode *left;  TreeNode *right;  int val;};
void LevelOrder(TreeNode *root) {  if (!root) {    return;  }    std::queue<TreeNode*> q;  q.push(root);    while (!q.empty()) {    int size = q.size();    for (int i = 0; i < size; ++i) {      auto t = q.front();      q.pop();      if (t->left) {        q.push(t->left);      }            if (t->right) {        q.push(t->right);      }            std::cout << t->val << std::endl;    }  }}

复制代码

递归实现

递归的实现，从理解上，较非递归会复杂一点。由于递归的特性，我们会一直深度优先去处理左子结点，那么势必会穿越不同的层，所以当要加入某个结点的时候，必须要知道当前的深度，所以使用一个变量 level 来标记当前的深度，初始化带入 0，表示根结点所在的深度。

由于在递归过程中，会穿越不同的层，因此，需要将每层的数据保存起来放入二维数组中，在整个递归结束的时候，在输出二维数据的元素值，即遍历了整个树。

由于一开始时由于不知道二叉树的深度，不知道有多少层，所以无法实现申请好二维数组的大小，只有在遍历的过程中不断的增加。那么什么时候该申请新的一层了呢，当 level 等于二维数组的大小的时候，为啥是等于呢，不是说要超过当前的深度么，这是因为 level 是从 0 开始的，就好比一个长度为 n 的数组 A，你访问 A[n] 是会出错的，当 level 等于数组的长度时，就已经需要新申请一层了，新建一个空层，继续往里面加数字，参见代码如下：

struct TreeNode {  TreeNode *left;  TreeNode *right;  int val;};
void Helper(TreeNode* root, int level, vector<vector<int>>& res) {        if (!node) return;        if (res.size() == level) res.push_back({});        res[level].push_back(node->val);        if (node->left) Helper(node->left, level + 1, res);        if (node->right) Helper(node->right, level + 1, res);    }    void LevelOrder(TreeNode *root) {  if (!root) {    return;  }    std::vector<std::vector<int>> res;  Helper(root, 0, res);    for (auto item : res) {    for (auto elem : ietm) {      std::cout << elem << " ";    }        std::cout << std::endl;  }  }

复制代码

扩展

树的高度

树的高度，递归方式比较简单，此处不在我们讲解范围内。我们将使用二叉树的层次遍历方式来求树的高度。代码如下：

int Height(TreeNode *root) {  if (!root) {    return 0;  }    int level = 0;  std::queue<TreeNode*> q;  q.push(root);    while (!q.empty()) {    int size = q.size();    for (int i = 0; i < size; ++i) {      auto t = q.front();      q.pop();      if (t->left) {        q.push(t->left);      }            if (t->right) {        q.push(t->right);      }    }    ++level; // 进入此处，表明已经遍历完一层  }    return level;}

复制代码

Z 字型遍历

所谓 Z 字型遍历，就是在遍历二叉树的时候，第一层从左向右，第二层从右向左，第三层又从左向右。即偶数层从左向右，奇数层从右向左遍历。

图六

如图六所示，其 Z 字型遍历结果就是 A C B D E F G

代码如下:

int ZOrder(TreeNode *root) {  if (!root) {    return 0;  }    int level = 0;  std::queue<TreeNode*> q;  q.push(root);    while (!q.empty()) {    int size = q.size();    std::vector<int> v;    for (int i = 0; i < size; ++i) {      auto t = q.front();      q.pop();      if (t->left) {        q.push(t->left);      }            if (t->right) {        q.push(t->right);      }            v.emplace_back(t->val); // 存储起来    }    if (level % 2) { // 如果是奇数层，则从右向左      for (int i = v.size() - 1; i >= 0; --i) {        std::cout << v[i] << " ";            }    } else { // 如果是偶数层，则从左向右      for (int i = 0; i < v.size(); ++i) {        std::cout << v[i] << " ";            }    }        std::cout << std::endl;    ++level;   }    return level;}

复制代码

结语

树的层次遍历，有很多变型，比如上面说的 z 字型，亦或者有 n 叉树层次遍历，但是万变不离其宗，方式都是一样的，只要我们掌握了核心点，还是很容易以不变应万变。

添加 vx 好友:chongbashuoshuo（虫爸说说的中文拼音），一起聊架构，扯技术。

个人主页:http://www.studyinfo.top

发布于: 1 小时前阅读数: 3

原文链接:【http://xie.infoq.cn/article/6344f13e9c945216e46e2af5b】。文章转载请联系作者。

namelij

关注

还未添加个人签名 2021.03.12 加入

还未添加个人简介

发布

暂无评论

创作场景

二叉树层次遍历及应用

层次遍历

非递归实现

根节点入队

上一层出队，其孩子节点入队

第二层出队，其孩子节点入队

第三层出队

递归实现

扩展

树的高度

Z 字型遍历

结语

namelij

评论