21xrx.com
2025-03-24 10:43:09 Monday
文章检索 我的文章 写文章
C++实现二叉树遍历特定层节点
2023-06-23 05:17:34 深夜i     16     0
C++ 二叉树 遍历 特定层 节点

在二叉树的遍历过程中，我们通常会按照特定顺序，遍历树的每个节点。而对于特定的层节点，我们希望能够有一种方法，只遍历二叉树中那些处在特定层的节点。在C++语言中，实现这一目标可以使用递归算法。下面是一种实现方法。

首先，我们需要定义一个函数，来遍历二叉树中特定层节点。该函数需要接受三个参数：根节点、当前层和目标层。其中，根节点用来指定从哪个节点开始遍历，当前层表示当前所处的层级，目标层则代表了需要遍历的层级。

void traverse(TreeNode* root, int cur_level, int target_level);

在该函数中，我们首先需要判断节点是否为NULL，如果是，则直接返回。否则，我们需要递归地遍历该节点的左右子树。

if (root == NULL)
  return;
traverse(root->left, cur_level + 1, target_level);
traverse(root->right, cur_level + 1, target_level);

接下来，我们需要判断当前节点所在的层级是否与目标层级相等。如果相等，我们需要对该节点进行相应的处理。这里我们只是简单地输出节点的值。

if (cur_level == target_level)
  std::cout << root->val << " ";

完整的代码如下：

void traverse(TreeNode* root, int cur_level, int target_level) {
  if (root == NULL)
    return;
  
  traverse(root->left, cur_level + 1, target_level);
  traverse(root->right, cur_level + 1, target_level);
  if (cur_level == target_level)
    std::cout << root->val << " ";
  
}

使用该函数，我们可以针对任意一棵二叉树，遍历特定层的节点。例如，对于如下的二叉树：

1
   / \
  2  3
  / \
 4  5

我们可以通过调用`traverse`函数遍历第二层节点：

traverse(root, 1, 2);

该函数会输出节点2和节点3的值。

  
  

评论区