C++数据结构--计算二叉树叶子数和深度

1.示例二叉树

2.计算二叉树深度：
*先计算左右子树的深度，然后整棵树的深度就是左右子树深度较大值加1
*递归遍历结束条件：定义空树的深度为-1，于是得到叶子节点的深度计算公式
Depth(叶节点）= 1 + max(depth(左子树），depth(右子树））
= 1 + max(-1,-1)
= 1 + -1
=0
计算二叉树深度图解：#后的数字代表遍历的步骤，字母的下标表示节点的深度

实现代码：
template<typename T>
class node
{
public:
T val;//节点值
node<T>* left;//左节点
node<T>* right;//右节点

node():val(T()),left(nullptr),right(nullptr){}
node(T v, node<T>* l=nullptr, node<T>* r=nullptr):val(v),left(l),right(r){}
};

node<char>* createBTree() //构建一棵示例二叉树
{
node<char>* g=new node<char>('G');
node<char>* e=new node<char>('E');
node<char>* f=new node<char>('F');
node<char>* d=new node<char>('D',nullptr,g);
node<char>* c=new node<char>('C',nullptr,f);
node<char>* b=new node<char>('B',d,e);
node<char>* a=new node<char>('A',b,c);

return a;

}

//计算叶子节点数只需用前序，中序，后序等任一种方式遍历二叉树
void leafCounts(node<char>* root,int &cnt)
{
if(root)
{
if(root->left==nullptr&&root->right==nullptr)//判断是否为叶子节点
{
cnt++;
return;
}
else
{
leafCounts(root->left,cnt);//遍历左子树
leafCounts(root->right,cnt);//遍历右子树
}
}
}


//计算二叉树的深度
int depth(node<char>* root)
{
  int rdepth=0;//根节点深度
int lval=0;//左子树深度
int rval=0;//右子树深度
  if(!root) //当到达叶子节点的左子树或右子树或整棵树为空树时
   {
   rdepth=-1;

   }
  else
{
lval=depth(root->left);//遍历左子树
rval=depth(root->right);//遍历右子树

rdepth=1+(lval>rval?lval:rval);
}

return rdepth;

}

int main()
{
node<char>* root=createBTree();
int count=0;
leafCounts(root,count);
cout<<count<<endl;//3

int dpt=depth(root);
cout<<dpt<<endl;//3

return 0;
}

原文链接：https://blog.csdn.net/piniheaven/article/details/9697879