#include "stdio.h"
#include "string.h"
#include "malloc.h"
#define NULL 0
#define MAXSIZE 30
typedef struct BiTNode //定义二叉树数据结构
{
char data;
struct BiTNode *lchild,*rchild;
} BiTNode;
void preCreate(BiTNode *& T) //先序遍历建立二叉树,#代表空树
{
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else
{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
printf("Error!");
T->data=ch;
preCreate(T->lchild);
preCreate(T->rchild);
}
}
int getLeafNum(BiTNode *root)//统计二叉树叶子节点个数
{
int count=0;//叶子总数,左子树叶子数.右子数叶子数
int left_count=0;
int right_count=0;
/*推断根节点是否为null
若根节点不空,推断根节点是否是叶子。是的话叶子总数+1并返回,
若不是统计左子树叶子数目和右子数叶子数目并相加返回
若根节点为空,则叶子数为0并返回
*/
if(root)
{
if(root->lchild==NULL&&root->rchild==NULL)
count++;
else
{
left_count=getLeafNum(root->lchild);
right_count=getLeafNum(root->rchild);
count=left_count+right_count;
}
}
else
{
count=0;
}
return count;
}
int getTreeDepth(BiTNode *root)//统计二叉树深度
{
int depth=0;
int left_depth=0;
int right_depth=0;
/*
推断根节点是否为空，
若根节点为空，深度置为0，并返回
若根节点不为空，统计左子树深度，统计右子树深度，二者相加后再加上1（1位根节点）并返回
*/
if(root)
{
left_depth=getTreeDepth(root->lchild);
right_depth=getTreeDepth(root->rchild);
depth=1+(left_depth>right_depth?
left_depth:right_depth);
}
else
{
depth=0;
}
return depth;
}
int main()
{
BiTNode * bitree=NULL;
preCreate(bitree);//先序遍历创建二叉树
printf("叶子个数:%d\n",getLeafNum(bitree));
printf("该二叉树深度:%d\n",getTreeDepth(bitree));
return 0;
}