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

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

2023-06-30 17:32:02 深夜i -- --

C++ 二叉树层序遍历实现数据结构

二叉树是一种常用的树形数据结构，它由节点和指向其左、右子节点的指针组成。在二叉树中，每个节点最多有两个子节点，分别称为左子节点和右子节点。层序遍历是一种常用的二叉树遍历方式，它按照从上到下、从左到右的顺序遍历二叉树的所有节点。

C++ 作为一种高效的编程语言，提供了丰富的数据结构和算法库，可以方便地实现二叉树的层序遍历。下面，我们将介绍 C++ 实现二叉树的层序遍历的具体方法。

首先，我们需要定义一个二叉树节点的结构体，它包含节点的值、左子节点和右子节点，示例如下：


struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

接下来，我们可以使用队列数据结构来实现二叉树的层序遍历。具体来说，我们从根节点开始，将根节点入队列，然后通过循环，依次遍历队列中的节点，将它们的左子节点和右子节点分别入队列。代码实现如下：


vector<vector<int>> levelOrder(TreeNode* root) {
  vector<vector<int>> res;
  if (root == NULL)
    return res;
  
  queue<TreeNode*> q;
  q.push(root);
  while (!q.empty()) {
    int size = q.size();
    vector<int> level;
    for (int i = 0; i < size; i++) {
      TreeNode* cur = q.front();
      q.pop();
      level.push_back(cur->val);
      if (cur->left != NULL) {
        q.push(cur->left);
      }
      if (cur->right != NULL) {
        q.push(cur->right);
      }
    }
    res.push_back(level);
  }
  return res;
}

在上面的代码中，我们首先创建一个队列 q，用于存储待遍历的节点。然后，将根节点 root 入队列，并通过 while 循环依次遍历队列中的节点。在每一层遍历之前，我们使用 size 记录当前队列的长度，以便知道当前层有多少个节点。然后，我们从队列中依次取出节点，并将其左右子节点入队列，然后将当前层的节点值存储到 level 中，最后将 level 加入结果 res。通过这种方式，我们可以从上到下、从左到右遍历二叉树的所有节点。

总的来说，C++ 实现二叉树的层序遍历相对简单，只需要采用队列这一数据结构，使用循环遍历每一层的节点，即可完成层序遍历操作。以上就是 C++ 实现二叉树的层序遍历的具体方法，希望对大家有所帮助。

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

下一篇: C++中的void main函数

评论区

()

相似文章