二叉树的操作之统计二叉树中节点的个数 |
您所在的位置：网站首页 › 叶结点个数 › 二叉树的操作之统计二叉树中节点的个数 |
二叉树的操作之统计二叉树中节点的个数
|
一，问题描述 给定一颗二叉树，已知其根结点。 ①计算二叉树所有结点的个数 ②计算二叉树中叶子结点的个数 ③计算二叉树中满节点（度为2）的个数
二，算法分析 找出各个问题的基准条件，然后采用递归的方式实现。 ①计算二叉树所有结点的个数 1)当树为空时，结点个数为0，否则为根节点个数 加上 根的左子树中节点个数 再加上 根的右子树中节点的个数 借助遍历二叉树的思路，每访问一个结点，计数增1。因此，可使用类似于先序遍历的思路来实现，代码如下： 
1 //计算树中节点个数
2 private int nubmerOfNodes(BinaryNode root){
3 int nodes = 0;
4 if(root == null)
5 return 0;
6 else{
7 nodes = 1 + nubmerOfNodes(root.left) + nubmerOfNodes(root.right);
8 }
9 return nodes;
10 }
计算树中节点个数的代码方法与计算树的高度的代码非常相似！
②计算叶子结点的个数 1)当树为空时，叶子结点个数为0 2)当某个节点的左右子树均为空时，表明该结点为叶子结点，返回1 3)当某个节点有左子树，或者有右子树时，或者既有左子树又有右子树时，说明该节点不是叶子结点，因此叶结点个数等于左子树中叶子结点个数 加上 右子树中叶子结点的个数
这种形式的递归返回的node值 是最外层方法的node。
1 //计算树中叶结点的个数
2 private int numberOfLeafs(BinaryNode root){
3 int nodes = 0;
4 if(root == null)
5 return 0;
6 else if(root.left == null && root.right == null)
7 return 1;
8 else
9 nodes = numberOfLeafs(root.left) + numberOfLeafs(root.right);
10 return nodes;
11 }
③计算满节点的个数（对于二叉树而言，满节点是度为2的节点） 满节点的基准情况有点复杂： 1)当树为空时，满节点个数为0 2)当树中只有一个节点时，满节点个数为0 3)当某节点只有左子树时，需要进一步判断左子树中是否存在满节点 4)当某节点只有右子树时，需要进一步判断右子树中是否存在满节点 5)当某节点即有左子树，又有右子树时，说明它是满结点。但是由于它的左子树或者右子树中可能还存在满结点，因此满结点个数等于该节点加上该节点的左子树中满结点的个数 再加上 右子树中满结点的个数。 代码如下：
1 //计算树中度为2的节点的个数--满节点的个数
2 private int numberOfFulls(BinaryNode root){
3 int nodes = 0;
4 if(root == null)
5 return 0;
6 else if(root.left == null && root.right == null)
7 return 0;
8 else if(root.left == null && root.right != null)
9 nodes = numberOfFulls(root.right);
10 else if(root.left != null && root.right == null)
11 nodes = numberOfFulls(root.left);
12 else
13 nodes = 1 + numberOfFulls(root.left) + numberOfFulls(root.right);
14 return nodes;
15 }
对于二叉树而言，有一个公式：度为2的结点个数等于度为0的结点个数减去1。 即：n(2)=n(0)-1 故可以这样： private int numberOfFulls(BinaryNode root){ return numberOfLeafs(root) > 0 ? numberOfLeafs(root)-1 : 0;// n(2)=n(0)-1 }
计算满节点个数的一些错误的方法： 错误方法一：
/*
* 错误,忽略了如下情况:某个结点的左子树中存在满结点的情况
* 6
* 2
* 1 3
*/
private int numberOfFulls2(BinaryNode root){
int nodes = 0;
if(root == null)
return 0;
else if(root.left == null || root.right == null)
return 0;
else if(root.left != null && root.right != null)
nodes = 1 + numberOfFulls2(root.left) + numberOfFulls2(root.right);
return nodes;
}
错误方法二：
1 //忽略了一种基准情况:只有一个节点的二叉树
2 private int numberOfFulls3(BinaryNode root){
3 int nodes = 0;
4 if(root == null)
5 return 0;
6 else if(root.left == null && root.right != null)
7 nodes = numberOfFulls3(root.right);
8 else if(root.left != null && root.right == null)
9 nodes = numberOfFulls3(root.left);
10 else
11 nodes = 1 + numberOfFulls3(root.left) + numberOfFulls3(root.right);
12 return nodes;
13 }
三，完整程序代码如下：
1 import c2.C2_2_8;
2
3 public class BinarySearchTree |
【本文地址】