#include <iostream>
#include "BiTree.h"
using namespace std;

//递归方法求解二叉树叶节点个数
template <class DT>
int LeafNum_1(BTNode<DT>* bt) {
	if (!bt) {
		return 0;
	}
	else if (bt->lchild == NULL && bt->rchild == NULL) {
		return 1;
	}
	else {
		return LeafNum_1(bt->lchild) + LeafNum_1(bt->rchild);
	}
}

//非递归方法求解二叉树叶节点个数
template <class DT>
int LeafNum_2(BTNode<DT>* bt) {
	if (!bt)
		return 0;
	SqStack<DT> S;
	InitStack(S, 20);
	BTNode<DT>* p = bt;
	int count = 0;
	while (p != NULL || !StackEmpty(S))
	{
		while (p != NULL)
		{
			if (p->lchild == NULL && p->rchild == NULL)
				count++;
			Push(S, p);
			p = p->lchild;
		}
		if (!StackEmpty(S))
		{
			Pop(S, p);
			p = p->rchild;
		}
	}
	return count;
}

int main() {
	BTNode<char>* bt;
	CreateBiTree(bt);
	cout << "递归方法求得二叉树叶节点个数为：" << LeafNum_1(bt) << endl;
	cout << "非递归方法求得二叉树叶节点个数为：" << LeafNum_2(bt) << endl;
	DestroyBiTree(bt);
	return 0;
}