已知二叉树采用二叉链表存储结构,编写算法统计二叉树中的叶子结点数。Java完整代码
时间: 2024-01-23 09:20:15 浏览: 86
用Java实现的二叉树算法.doc
以下是统计二叉树中叶子结点数的Java代码:
```java
public class BinaryTree {
private static class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
private Node root;
public BinaryTree() {
root = null;
}
public int countLeaves() {
return countLeaves(root);
}
private int countLeaves(Node node) {
if (node == null) {
return 0;
}
if (node.left == null && node.right == null) {
return 1;
}
return countLeaves(node.left) + countLeaves(node.right);
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
int numLeaves = tree.countLeaves();
System.out.println("Number of leaves in binary tree: " + numLeaves);
}
}
```
这里的 `countLeaves` 方法使用递归来实现。如果当前节点为空,返回0;如果当前节点是叶子节点,返回1;否则,递归计算左子树和右子树的叶子节点数,并将它们相加作为当前节点的叶子节点数。在 `main` 方法中创建了一棵二叉树,并计算其叶子节点数。
阅读全文