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;
  /*
  求二叉树叶子节点数
  叶子节点：即没有左右子树的.结点
  递归方式步骤：
  如果给定节点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;
  stackst;
  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);//递归

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。