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

男娘i 2021-11-26 23:56 297阅读 0赞

**1.示例二叉树  
![20130801082401140][]  
  
  
  
  
  
  
  
  
2.计算二叉树深度：  
\*先计算左右子树的深度，然后整棵树的深度就是左右子树深度较大值加1  
\*递归遍历结束条件：定义空树的深度为-1，于是得到叶子节点的深度计算公式  
Depth(叶节点）= 1 + max(depth(左子树），depth(右子树））  
= 1 + max(-1,-1)  
= 1 + -1  
=0  
计算二叉树深度图解：\#后的数字代表遍历的步骤，字母的下标表示节点的深度  
![20130801082510359][]  
  
  
  
  
实现代码：  
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;  
\}**

[20130801082401140]: /images/20211126/65eddb9e754e44848b11b44fa6e7b022.png
[20130801082510359]: /images/20211126/0d9d38621cb04427985f7a2d87ccece1.png