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

本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法。分享给大家供大家参考，具体如下：

#include 
#include 
#include 
using std::cout;
using std::cin;
using std::endl;
using std::stack;

typedef struct BTreeNode
{
  char elem;
  struct BTreeNode *pleft;
  struct BTreeNode *pright;
}BTreeNode;

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  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;
}

希望本文所述对大家C++程序设计有所帮助。