C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

/*求二叉树叶子节点个数 -- 采用递归和非递归方法经调试可运行源码及分析如下：***/#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*/