C++实现二叉树的层序遍历代码 |21xrx.com

C++实现二叉树的层序遍历代码

2023-07-10 06:46:50 深夜i 24 0

C++ 二叉树层序遍历代码

二叉树是数据结构中经典的数据结构之一，它具有良好的性能和灵活的使用。在实际开发中，我们经常需要对二叉树进行遍历操作。C++语言提供了丰富的函数库和工具，使得二叉树操作十分便捷。

层序遍历是二叉树遍历的一种常用方法，它按照二叉树节点的层级来遍历整个树。在C++语言中，我们可以通过递归或者循环来实现二叉树的层序遍历。

以下是C++实现二叉树的层序遍历代码：

#include <queue>
#include <iostream>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<vector<int>> levelOrder(TreeNode* root) {
  if(!root) return {};
  queue<TreeNode*> q{{root}};
  vector<vector<int>> res;
  while(!q.empty()) {
    vector<int> v;
    for(int i=q.size(); i>0; i--) {
      TreeNode* t = q.front(); q.pop();
      v.push_back(t->val);
      if(t->left) q.push(t->left);
      if(t->right) q.push(t->right);
    }
    res.push_back(v);
  }
  return res;
}
int main() {
  TreeNode* root = new TreeNode(3);
  root->left = new TreeNode(9);
  root->right = new TreeNode(20);
  root->right->left = new TreeNode(15);
  root->right->right = new TreeNode(7);
  vector<vector<int>> res = levelOrder(root);
  for(auto v:res) {
    for(auto i:v)
      cout<<i<<" ";
    
    cout<<endl;
  }
  return 0;
}

在上述代码中，我们定义了一个结构体`TreeNode`，它包括节点值`val`和左右子树指针`left`和`right`。我们还定义了一个`levelOrder`函数来实现二叉树的层序遍历操作。

在`levelOrder`函数中，我们首先判断二叉树的根节点是否为空，若为空，则返回一个空的`vector`。否则，我们先将根节点加入到队列`q`中。我们对队列进行循环，让每次循环取出队列中当前元素的所有子节点，将子节点的值加入到当前层级`v`中，并将子节点加入队列。循环结束后，我们将当前层级`v`加入到最终结果`res`中，直到队列为空。

在主函数中，我们创建了一个二叉树，并调用`levelOrder`函数对其进行层序遍历，最后输出结果。

总的来说，C++提供了丰富的函数库和语法结构，可以轻松实现二叉树的层序遍历操作。通过使用队列等数据结构，实现层序遍历变得十分简单。

上一篇: idea打包java可执行jar包

下一篇: C++ 如何使用循环语句退出循环？

评论区

相似文章