C++实现二叉树遍历和叶子节点计数 |21xrx.com

C++实现二叉树遍历和叶子节点计数

2023-07-05 15:01:48 深夜i -- --

C++ 二叉树遍历叶子节点计数

二叉树是一种常见的数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。在对二叉树进行操作时，常常需要把它遍历一遍，也需要计算二叉树中的叶子节点数量。本文将介绍如何使用C++实现二叉树遍历和叶子节点计数。

首先，我们需要定义一个二叉树节点的结构体。


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

这个结构体包含一个整数val，表示节点的值，和左右子节点的指针。我们还为该结构体定义了一个构造函数，方便创建新节点。

接下来，我们可以使用递归的方式实现二叉树的遍历。对于一棵二叉树，它的遍历方式有三种：前序遍历、中序遍历和后序遍历。其中，前序遍历的顺序是根节点、左子树、右子树；中序遍历的顺序是左子树、根节点、右子树；后序遍历的顺序是左子树、右子树、根节点。以下是这三种遍历方式的C++实现代码。

前序遍历：


void preorderTraversal(TreeNode* root) {
  if (root == NULL) return;
  cout << root->val << " ";
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

中序遍历：


void inorderTraversal(TreeNode* root) {
  if (root == NULL) return;
  inorderTraversal(root->left);
  cout << root->val << " ";
  inorderTraversal(root->right);
}

后序遍历：


void postorderTraversal(TreeNode* root) {
  if (root == NULL) return;
  postorderTraversal(root->left);
  postorderTraversal(root->right);
  cout << root->val << " ";
}

需要注意的是，我们在遍历节点时使用了cout语句输出节点的值，实际应用中可以根据具体情况来修改输出方式。

接下来，我们来实现二叉树叶子节点数量的计数。叶子节点是指没有子节点的节点，所以我们可以使用递归的方法遍历二叉树，每次判断当前节点是否为叶子节点。以下是C++实现代码。


int countLeafNodes(TreeNode* root) {
  if (root == NULL) return 0;
  if (root->left == NULL && root->right == NULL) return 1;
  return countLeafNodes(root->left) + countLeafNodes(root->right);
}

需要注意的是，递归结束的条件是遍历到空节点时返回0，而不是1。当遍历到叶子节点时，返回1表示有1个叶子节点。对于非叶子节点，则递归遍历它的左右子树，然后将它们的叶子节点数量相加即可。

综上所述，我们可以使用C++实现二叉树的遍历和叶子节点计数。这些算法都是基于递归的实现方式，易于理解和实现。在实际应用中，我们可以根据需要对它们进行修改和优化，以满足特定的需求。

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

下一篇: 如何在nodejs中文网上安装及配置环境？

评论区

()

相似文章