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