21xrx.com
2024-12-23 01:24:26 Monday
登录
文章检索 我的文章 写文章
C++实现二叉树层次遍历算法
2023-07-05 08:48:58 深夜i     --     --
C++ 二叉树 层次遍历算法 数据结构 树节点

二叉树是一种重要的数据结构,其遍历算法可用于许多应用中。其中,层次遍历算法是一种广泛应用的算法,其采用队列数据结构实现,可用于搜索等方面。

C++语言是一个广泛应用于编程领域的语言,其作为一种高级语言,能够方便地实现二叉树的层次遍历算法。

在C++中实现二叉树的层次遍历算法时,需要先定义二叉树节点的结构体,包括左子树、右子树、值等属性。


struct Node {

  int val;

  Node* left;

  Node* right;

  Node(int x) : val(x), left(NULL), right(NULL) {}

};

定义好节点结构体后,使用队列来实现层次遍历算法。具体实现过程如下:


vector<vector<int>> levelOrder(Node* root) {

  vector<vector<int>> res;

  if (!root) return res;

  queue<Node*> q{{root}};

  while (!q.empty()) {

    vector<int> tmp;

    for (int i = q.size(); i > 0; --i) {

      auto t = q.front(); q.pop();

      tmp.push_back(t->val);

      if (t->left) q.push(t->left);

      if (t->right) q.push(t->right);

    }

    res.push_back(tmp);

  }

  return res;

}

上述代码中,首先定义了一个二维vector数组res,用于存储遍历结果,同时判断根节点是否为空,如果是则返回空数组。然后定义一个队列,将根节点放入队列中。

在while循环中,先初始化一个空的vector,用于存储当前层的遍历结果。然后遍历当前队列中的所有节点,将节点的val值存入tmp数组中,并将节点的左右子树节点依次入队,直到该层所有节点遍历完毕。

将tmp数组存入res数组中,继续遍历下一层的节点,直到所有层的节点被遍历完成。最后返回res数组,即可得到二叉树的层次遍历结果。

以上就是C++实现二叉树层次遍历算法的具体过程。该算法具有广泛应用性,可用于判断树是否为完全二叉树、计算二叉树最大非叶子结点个数等方面。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复