二叉树的深度的深度计算与完全二叉树、满二叉树概念

阳光穿透心脏的1/2处 2023-07-06 14:53 17阅读 0赞

**二叉树的深度计算**  
1、一颗树只有一个节点，它的深度是1；

2、二叉树的根节点只有左子树而没有右子树，那么可以判断，二叉树的深度应该是其左子树的深度加1；

3、二叉树的根节点只有右子树而没有左子树，那么可以判断，那么二叉树的深度应该是其右树的深度加1；

4、二叉树的根节点既有右子树又有左子树，那么可以判断，那么二叉树的深度应该是其左右子树的深度较大值加1。

int TreeDeep(struct node *T)
    { 
        int deep=0;
        if(T)
        { 
            int ld=TreeDeep(T->l);
            int rd=TreeDeep(T->r);
            deep=ld>=rd?ld+1:rd+1;
        }
        return deep;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTkzOTgy_size_16_color_FFFFFF_t_70]  
**满二叉树与完全二叉树**  
一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树 。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTkzOTgy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200127172117925.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTkzOTgy,size_16,color_FFFFFF,t_70