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

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

2023-06-24 14:07:59 深夜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 levelSize = q.size();
    vector<int> levelVec;
    for (int i = 0; i < levelSize; i++) {
      TreeNode* curr = q.front();
      q.pop();
      levelVec.push_back(curr->val);
      if (curr->left != NULL) {
        q.push(curr->left);
      }
      if (curr->right != NULL) {
        q.push(curr->right);
      }
    }
    res.push_back(levelVec);
  }
  return res;
}

这个函数使用了一个队列来实现层序遍历。在遍历的过程中，我们通过循环统计该层节点数并将该层节点的值存入 levelVec 向量中。然后，我们将向量 levelVec 添加到结果的 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 i : res) {
    for (auto j : i)
      cout << j << " ";
    
    cout << endl;
  }
  return 0;
}

这段代码将输出以下二叉树及其层序遍历的结果：

3 / \ 9 20 / \ 15 7 Output: 3 9 20 15 7

这里我们可以看到 res 向量中包含三个向量，每个向量分别表示二叉树的第一、二、三层节点值。具体来说，第一层包含节点值 3，第二层包含节点值 9 和 20，并在第三层中包含节点值 15 和 7。

结论

本文介绍了如何使用 C++ 实现二叉树的层序遍历。我们使用一个队列和一个向量列表，按层次顺序遍历并返回每层节点的值。该方法对于许多算法和数据分析都是非常有用的。如果您想进行二叉树的分析或操作，层序遍历函数是非常重要且实用的工具之一。

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

下一篇: Java如何调用C程序？

评论区

()

相似文章