C++实现递归输出二叉树所有叶子节点 |21xrx.com

C++实现递归输出二叉树所有叶子节点

2023-07-11 12:01:35 深夜i -- --

C++ 递归二叉树叶子节点输出

在计算机科学中，二叉树是一种常见的数据结构，它由节点和边组成。其中每个节点最多有两个子节点，分别称为左子节点和右子节点。在二叉树中，叶子节点是指没有子节点的节点。要想递归输出二叉树所有叶子节点，可以使用 C++ 语言编写程序实现。下面是实现思路和实现步骤。

实现思路：

1. 分别递归输出左子树和右子树节点；

2. 如果该节点是叶子节点，则输出该节点。

实现步骤：

1. 对于每一个节点，先递归输出左子树；

2. 对于每一个节点，再递归输出右子树；

3. 如果该节点是叶子节点，则输出该节点；

4. 最终输出所有叶子节点。

C++代码实现：


#include <iostream>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void printLeaf(TreeNode* root) {
  if (root == NULL) return;
  if (root->left == NULL && root->right == NULL)
    cout << root->val << " ";
    return;
  
  printLeaf(root->left);
  printLeaf(root->right);
}
int main() {
  // 二叉树
  /*
      1
      / \
     2  3
     / \
    4  5
        \
        6
  */
  TreeNode* root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->left->left = new TreeNode(4);
  root->left->right = new TreeNode(5);
  root->left->right->right = new TreeNode(6);
  // 输出二叉树所有叶子节点
  cout << "The leaf nodes of the binary tree are: ";
  printLeaf(root);
  cout << endl;
  return 0;
}

输出结果：

The leaf nodes of the binary tree are: 4 6

综上所述，使用上述 C++ 代码可以递归输出二叉树所有叶子节点。该算法时间复杂度为 O(N)，其中 N 为节点个数。因为需要遍历每一个节点，所以一般来说该算法的时间复杂度无法更低。如果要对该算法进行优化，可以考虑增加一些剪枝等操作，但是需要注意不要影响算法的正确性。

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

下一篇: Dev C++下载无法识别中文字符怎么办？

评论区

()

相似文章