统计树中叶子结点个数,树用孩子链表表示
时间: 2023-06-04 12:06:00 浏览: 78
这是一个技术问题,我可以回答。统计树中叶子结点的个数可以使用递归算法,首先判断当前节点是否为空,如果为空则返回0。如果当前节点是叶子节点,则返回1。否则,遍历当前节点的每一个孩子节点,将每个孩子节点返回的叶子节点个数相加即可。
相关问题
编写算法,在以二叉链表存储的二叉树中,统计二叉树中叶子结点个数
可以使用递归的方式来统计二叉树中叶子节点的个数。具体算法如下:
1. 如果二叉树为空,则叶子节点个数为。
2. 如果二叉树只有一个节点,则叶子节点个数为1。
3. 否则,递归计算左子树和右子树中叶子节点的个数,然后将它们相加即可。
以下是具体的代码实现:
```
int countLeafNodes(TreeNode* root) {
if (root == nullptr) {
return ;
}
if (root->left == nullptr && root->right == nullptr) {
return 1;
}
int leftCount = countLeafNodes(root->left);
int rightCount = countLeafNodes(root->right);
return leftCount + rightCount;
}
```
其中,`TreeNode` 表示二叉树节点的结构体,包含左右子节点指针和节点值等信息。
先序遍历序列建立一个二叉树的二叉链表,统计二叉树中叶子结点个数和二叉树的深度
先序遍历序列建立二叉树的步骤:
1. 从先序遍历序列中取出第一个元素作为根节点。
2. 剩余的序列中,找到第一个大于根节点的值,它左边的部分是根节点的左子树的先序遍历序列,右边的部分是根节点的右子树的先序遍历序列。
3. 对左子树序列和右子树序列分别递归进行上述步骤。
代码如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(preorder):
if not preorder:
return None
root = TreeNode(preorder[0])
i = 1
while i < len(preorder) and preorder[i] < root.val:
i += 1
root.left = build_tree(preorder[1:i])
root.right = build_tree(preorder[i:])
return root
```
统计二叉树中叶子结点个数和二叉树的深度可以通过递归实现。叶子结点的定义是没有左右子树的节点,因此可以判断当前节点是否为叶子节点,如果是,则返回1,否则返回左右子树的叶子结点个数之和。二叉树的深度可以定义为根节点到最深叶子节点的路径长度,因此可以递归计算左右子树的深度,然后取较大值加1即可。
代码如下:
```python
def count_leaf(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaf(root.left) + count_leaf(root.right)
def max_depth(root):
if not root:
return 0
return max(max_depth(root.left), max_depth(root.right)) + 1
```
完整代码如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(preorder):
if not preorder:
return None
root = TreeNode(preorder[0])
i = 1
while i < len(preorder) and preorder[i] < root.val:
i += 1
root.left = build_tree(preorder[1:i])
root.right = build_tree(preorder[i:])
return root
def count_leaf(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaf(root.left) + count_leaf(root.right)
def max_depth(root):
if not root:
return 0
return max(max_depth(root.left), max_depth(root.right)) + 1
preorder = [5, 3, 1, 4, 7, 6, 8]
root = build_tree(preorder)
print(count_leaf(root)) # 4
print(max_depth(root)) # 3
```