以二叉链表作存储结构,建立一棵二叉树,统计该二叉树的叶子结点数。
时间: 2024-09-06 17:01:52 浏览: 39
二叉链表作存储结构,设计求二叉树高度的算法
3星 · 编辑精心推荐
在计算机科学中,二叉树是一种重要的数据结构,具有以下特性:
1. 每个节点最多有两个子节点,称为左孩子和右孩子。
2. 二叉树的每个子树都是二叉树。
3. 二叉树可以是空的,即不存在任何节点。
要统计一个以二叉链表为存储结构的二叉树的叶子节点数,我们可以递归地遍历这棵树。叶子节点定义为没有子节点的节点,即左右孩子都为空的节点。统计过程中,每当遇到一个叶子节点,我们就增加叶子节点的计数。
以下是实现这一过程的伪代码:
```
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
int countLeaves(TreeNode root) {
if (root == null) {
// 空树,没有叶子节点
return 0;
} else if (root.left == null && root.right == null) {
// 当前节点是叶子节点,计数加1
return 1;
} else {
// 递归统计左右子树的叶子节点数,并加起来
return countLeaves(root.left) + countLeaves(root.right);
}
}
```
在这个伪代码中,`TreeNode` 类定义了二叉树的节点结构,其中包含一个整数值 `val` 和两个指向其子节点的引用 `left` 和 `right`。`countLeaves` 函数接受一个 `TreeNode` 类型的参数 `root`,表示二叉树的根节点。函数递归地计算并返回整棵树的叶子节点数。
阅读全文