您的位置 首页 java

二叉树层次遍历以及应用

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

层次遍历

图一 二叉树

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

  • 第一层: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叉树层次遍历,但是万变不离其宗,方式都是一样的,只要我们掌握了核心点,还是很容易以不变应万变。


移步 获取更多文章

文章来源:智云一二三科技

文章标题:二叉树层次遍历以及应用

文章地址:https://www.zhihuclub.com/197840.shtml

关于作者: 智云科技

热门文章

网站地图