###递归算法NB

#include <iostream>
using namespace std;

typedef char BTDataType;

typedef struct BiTNode
{
	BTDataType data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;

//按先序次序输入二叉树结点的值(一个字符),创建二叉链表表示的二叉树T
void CreateBiTree(BiTree& T) {
	char ch;
	cin >> ch;
	if (ch == '#') T = NULL;		//递归结束,建空树
	else
	{
		T = new BiTNode;			//生成根结点
		T->data = ch;				//根节点数据域置为ch
		CreateBiTree(T->lchild);	//递归创建左子树
		CreateBiTree(T->rchild);	//递归创建右子树
	}
}

//为了方便测试,不用一个个输入创建二叉树,这个数组是先序存放的二叉树,深度为4
char treeArray[] = { 'A','B','#','C','D','#','#','E','#','#','F','#','G','H','#','#','#' };
int i = 0;
void CreateBiTreeTest(BiTree& T) {
	char ch;
	ch = treeArray[i++];
	if (ch == '#') T = NULL;
	else
	{
		T = new BiTNode;
		T->data = ch;
		CreateBiTreeTest(T->lchild);
		CreateBiTreeTest(T->rchild);
	}
}

//复制一颗和T完全相同的二叉树
void Copy(BiTree T, BiTree& NewT)
{
	if (T == NULL)
	{
		NewT = NULL;
		return;
	}
	else
	{
		NewT = new BiTNode;
		NewT->data = T->data;			//复制根节点
		Copy(T->lchild, NewT->lchild);	//递归复制左子树
		Copy(T->rchild, NewT->rchild);	//递归复制右子树
	}
}

//计算二叉树的深度--在后序遍历二叉树的基础上进行的运算
int Depth(BiTree T)
{
	int m = 0, n = 0;
	if (T == NULL) return 0;
	else
	{
		m = Depth(T->lchild);	//递归计算右子树的深度m
		n = Depth(T->rchild);	//递归计算左子树的深度n
		if (m > n) return m + 1;	//左右深度较大者+1根节点
		else return n + 1;
	}
}

//统计二叉树T中结点的个数
int NodeCount(BiTree T)
{
	if (T == NULL) return 0;
	else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

//计算二叉树叶子结点总数
int LeadCount(BiTree T)
{
	if (T == NULL) return 0;
	if (T->lchild == NULL && T->rchild == NULL) return 1;
	else return LeadCount(T->lchild) + LeadCount(T->rchild);
}

int main()
{
	BiTree T;
	CreateBiTreeTest(T); i = 0;		//方便测试,不用输入创建
	cout << Depth(T) << endl;
	cout << NodeCount(T) << endl;
	cout << LeadCount(T) << endl;
	return 0;
}