本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法。分享给大家供大家参考，具体如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
/*求二叉树叶子节点个数 -- 采用递归和非递归方法经调试可运行源码及分析如下：***/#include <stdlib.h>#include <iostream>#include <stack>using std::cout;using std::cin;using std::endl;using std::stack;/*二叉树结点定义*/typedef struct BTreeNode{ char elem; struct BTreeNode *pleft; struct BTreeNode *pright;}BTreeNode;/*求二叉树叶子节点数叶子节点：即没有左右子树的结点递归方式步骤：如果给定节点proot为NULL，则是空树，叶子节点为0，返回0；如果给定节点proot左右子树均为NULL，则是叶子节点，且叶子节点数为1，返回1；如果给定节点proot左右子树不都为NULL，则不是叶子节点，以proot为根节点的子树叶子节点数=proot左子树叶子节点数+proot右子树叶子节点数。/*递归实现求叶子节点个数*/int get_leaf_number(BTreeNode *proot){ if(proot == NULL) return 0; if(proot->pleft == NULL && proot->pright == NULL) return 1; return (get_leaf_number(proot->pleft) + get_leaf_number(proot->pright));}/*非递归：本例采用先序遍历计算判断当前访问的节点是不是叶子节点，然后对叶子节点求和即可。 **/int preorder_get_leaf_number(BTreeNode* proot){ if(proot == NULL) return 0; int num = 0; stack <BTreeNode*> st; while (proot != NULL || !st.empty()) { while (proot != NULL) { cout << "节点：" << proot->elem << endl; st.push(proot); proot = proot->pleft; } if (!st.empty()) { proot = st.top(); st.pop(); if(proot->pleft == NULL && proot->pright == NULL) num++; proot = proot -> pright; } } return num;}/*初始化二叉树根节点*/BTreeNode* btree_init(BTreeNode* &bt){ bt = NULL; return bt;}/*先序创建二叉树*/void pre_crt_tree(BTreeNode* &bt){ char ch; cin >> ch; if (ch == '#') { bt = NULL; } else { bt = new BTreeNode; bt->elem = ch; pre_crt_tree(bt->pleft); pre_crt_tree(bt->pright); }}int main(){ int tree_leaf_number = 0; BTreeNode *bt; btree_init(bt);//初始化根节点 pre_crt_tree(bt);//创建二叉树 tree_leaf_number = get_leaf_number(bt);//递归 cout << "二叉树叶子节点个数为:" << tree_leaf_number << endl; cout << "非递归先序遍历过程如下：" << endl; tree_leaf_number = preorder_get_leaf_number(bt);//非递归 cout << "二叉树叶子节点个数为:" << tree_leaf_number << endl; system("pause"); return 0;}/*运行结果：a b c # # # d e # # f # #---以上为输入------以下为输出---二叉树叶子节点个数为:3非递归遍历过程如下：节点：a节点：b节点：c节点：d节点：e节点：f二叉树叶子节点个数为:3请按任意键继续. . .本例创建的二叉树形状： a b d c e f*/ |
希望本文所述对大家C++程序设计有所帮助。
