任意创建一棵二叉树,统计该二叉树的叶子结点数C++代码
时间: 2023-09-08 18:05:28 浏览: 80
C++如何实现二叉树叶子节点个数计算.pdf
### 回答1:
二叉树的叶子结点是指没有子节点的结点,因此可以使用递归的方式进行统计。下面是C++代码实现:
```c++
#include<iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
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);
}
int main() {
// 创建二叉树
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->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
// 统计叶子结点数
int leafNodes = countLeafNodes(root);
cout << "The number of leaf nodes is: " << leafNodes << endl;
return 0;
}
```
输出结果为:
```
The number of leaf nodes is: 4
```
### 回答2:
二叉树是一种树形结构,其中每个节点最多有两个子节点,分别称为左子节点和右子节点。
以下是一个任意创建的二叉树及统计叶子节点数的代码:
```python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def count_leaves(root):
if root is None:
return 0
if root.left is None and root.right is None:
return 1
return count_leaves(root.left) + count_leaves(root.right)
# 创建二叉树
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
# 统计二叉树的叶子节点数
leaves = count_leaves(root)
print("叶子节点数为:", leaves)
```
在上述代码中,我们首先定义了一个`Node`类,用于表示二叉树节点。每个节点包含一个`data`数据和两个子节点`left`和`right`。
然后,我们定义了一个`count_leaves`函数,用于统计二叉树的叶子节点数。这个函数使用递归的方式遍历二叉树,如果当前节点为空,则返回0;如果当前节点没有左子节点和右子节点,则返回1;否则,递归统计左子树和右子树的叶子节点数,并相加返回。
接下来,我们创建了一棵任意的二叉树,并调用`count_leaves`函数统计叶子节点数,最后输出结果。
### 回答3:
创建二叉树的代码如下所示:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 创建二叉树
def create_binary_tree(nodes):
if not nodes:
return None
n = len(nodes)
root = TreeNode(nodes[0])
queue = [root]
i = 1
while i < n:
node = queue.pop(0)
if nodes[i]:
left_child = TreeNode(nodes[i])
node.left = left_child
queue.append(left_child)
i += 1
if i < n and nodes[i]:
right_child = TreeNode(nodes[i])
node.right = right_child
queue.append(right_child)
i += 1
return root
# 统计叶子节点数
def count_leaves(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaves(root.left) + count_leaves(root.right)
```
例如,我们可以创建以下二叉树:
```
1
/ \
2 3
/ \
4 5
```
对应的代码如下:
```python
nodes = [1, 2, 3, 4, 5]
root = create_binary_tree(nodes)
leaf_count = count_leaves(root)
print("叶子节点数: ", leaf_count)
```
输出结果为:
```
叶子节点数: 3
```
所以,对于上述二叉树,叶子节点数为3。
阅读全文