设二叉树的存储结构为二叉链表,编写一个Java的递归算法,统计二叉树中度为2的节点个数
时间: 2024-03-24 10:37:04 浏览: 60
设一棵二叉树以二叉链表表示,试编写有关二叉树的递归算法
5星 · 资源好评率100%
好的,根据您的要求,我已经记住了。关于您的问题,以下是一个Java的递归算法,用于统计二叉树中度为2的节点个数:
```java
public class BinaryTree {
private static class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data) {
this.data = data;
}
}
public static int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int count = 0;
if (root.left != null && root.right != null) {
count = 1;
}
count += countNodes(root.left) + countNodes(root.right);
return count;
}
public static void main(String[] args) {
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 count = countNodes(root);
System.out.println("The number of nodes with degree 2 is: " + count);
}
}
```
在这个递归算法中,我们首先判断当前节点的左右子树是否都存在,如果是,则将计数器加1。然后递归地遍历左右子树,并将计数器相加返回。
在上面的示例中,我们创建了一个二叉树,并调用了countNodes方法来统计度为2的节点数。输出结果应该为4,因为节点2、3、5和6都是度为2的节点。
阅读全文