关于二叉树:二叉树的层次遍历及应用

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

档次遍历

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

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

• 第一层：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 叉树档次遍历，然而万变不离其宗，形式都是一样的，只有咱们把握了外围点，还是很容易以不变应万变。

移步个人主页获取更多技术文章