⼆叉树之统计⼆叉树的节点个数
⼆叉树之统计⼆叉树的节点个数
⼀，问题描述
给定⼀颗⼆叉树，已知其根结点。
①计算⼆叉树所有结点的个数
②计算⼆叉树中叶⼦结点的个数
③计算⼆叉树中满节点（度为2）的个数
⼆，算法分析
出各个问题的基准条件，然后采⽤递归的⽅式实现。
①计算⼆叉树所有结点的个数
1)当树为空时，结点个数为0，否则为根节点个数加上根的左⼦树中节点个数再加上根的右⼦树中节点的个数
借助遍历⼆叉树的思路，每访问⼀个结点，计数增1。因此，可使⽤类似于先序遍历的思路来实现，代码如下：
1 //计算树中节点个数
2 private int nubmerOfNodes(BinaryNode<T> 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<T> 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<T> 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<T> root){
return numberOfLeafs(root) > 0 ? numberOfLeafs(root)-1 : 0;// n(2)=n(0)-1
}
⼆，完整程序代码如下：
1 import c2.C2_2_8;
2
3 public class BinarySearchTree<T extends Comparable<? super T>> {
4
5 private static class BinaryNode<T> {
6 T element;
7 BinaryNode<T> left;
8 BinaryNode<T> right;
9
10 public BinaryNode(T element) {
11 this(element, null, null);
12 }
13
14 public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
15 this.element = element;
16 this.left = left;
17 this.right = right;
18 }
19
20 public String toString() {
21 String();
22 }
23 }
24
25 private BinaryNode<T> root;
26
27 public BinarySearchTree() {
28 root = null;
29 }
30
31 public void insert(T ele) {
32 root = insert(ele, root);// 每次插⼊操作都会'更新'根节点.
33 }
34
35 private BinaryNode<T> insert(T ele, BinaryNode<T> root) {
36 if (root == null)
37 return new BinaryNode<T>(ele);
38 int compareResult = elepareTo(root.element);
39 if (compareResult > 0)
40 root.right = insert(ele, root.right);
41 else if (compareResult < 0)
42 root.left = insert(ele, root.left);
43 else
44 ;
45 return root;
46 }
47
48 public int height() {
49 return height(root);
50 }
51
52 private int height(BinaryNode<T> root) {
53 if (root == null)
54 return -1;// 叶⼦节点的⾼度为0，空树的⾼度为1
55
56 return 1 + (int) Math.max(height(root.left), height(root.right));
57 }
58
59 public int numberOfNodes(BinarySearchTree<T> tree){
60 return );
61 }
62
63 //计算树中节点个数
64 private int nubmerOfNodes(BinaryNode<T> root){
65 int nodes = 0;
66 if(root == null)
67 return 0;
二叉树公式68 else{
69 nodes = 1 + nubmerOfNodes(root.left) + nubmerOfNodes(root.right);
70 }
71 return nodes;
72 }
73
74
75 public int numberOfLeafs(BinarySearchTree<T> tree){
76 return );
77 }
78 //计算树中叶结点的个数
79 private int numberOfLeafs(BinaryNode<T> root){
80 int nodes = 0;
81 if(root == null)
82 return 0;
83 else if(root.left == null && root.right == null)
84 return 1;
85 else
86 nodes = numberOfLeafs(root.left) + numberOfLeafs(root.right);
87 return nodes;
88 }
89
90 public int numberOfFulls(BinarySearchTree<T> tree){
91 return );
92 // return ) > 0 ? )-1 : 0;// n(2)=n(0)-1
93 }
94 //计算树中度为2的节点的个数--满节点的个数
95 private int numberOfFulls(BinaryNode<T> root){
96 int nodes = 0;
97 if(root == null)
98 return 0;
99 else if(root.left == null && root.right == null)
100 return 0;
101 else if(root.left == null && root.right != null)
102 nodes = numberOfFulls(root.right);
103 else if(root.left != null && root.right == null)
104 nodes = numberOfFulls(root.left);
105 else
106 nodes = 1 + numberOfFulls(root.left) + numberOfFulls(root.right);
107 return nodes;
108 }
109
110
111 public static void main(String[] args) {
112 BinarySearchTree<Integer> intTree = new BinarySearchTree<>();
113 double averHeight = intTree.averageHeigth(1, 6, intTree);
114 System.out.println("averageheight = " + averHeight);
115
116 /*-----------All Nodes-----------------*/
117 int totalNodes = intTree.numberOfNodes(intTree);
118 System.out.println("total nodes: " + totalNodes);
119
120 /*-----------Leaf Nodes-----------------*/
121 int leafNodes = intTree.numberOfLeafs(intTree);
122 System.out.println("leaf nodes: " + leafNodes);
123
124 /*-----------Full Nodes-----------------*/
125 int fullNodes = intTree.numberOfFulls(intTree);
126 System.out.println("full nodes: " + fullNodes);
127 }
128
129 public double averageHeigth(int tree_numbers, int node_numbers, BinarySearchTree<Integer> tree) { 130 int tree_height, totalHeight = 0;
131 for(int i = 1; i <= tree_numbers; i++){
132 int[] randomNumbers = C2_2_8.algorithm3(node_numbers);
133 //build tree
134 for(int j = 0; j < node_numbers; j++)
135 {
136 tree.insert(randomNumbers[j]);
137 System.out.print(randomNumbers[j] + " "); 138 }
139 System.out.println();
140 tree_height = tree.height();
141 System.out.println("height:" + tree_height); 142
143 totalHeight += tree_height;
144 // = null;//for building next tree
145 }
146 return (double)totalHeight / tree_numbers;
147 }
148 }
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论