/*求二叉樹葉子節點個數 -- 采用遞歸和非遞歸方法經調試可運行源碼及分析如下：***/#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*/