如何理解二叉树的深度?
发布网友
发布时间：2023-10-12 21:46
共1个回答
热心网友
时间：2023-10-13 00:48
度分为三种：树的深度：树中最大的结点层、结点的度：结点子树的个数、树的度： 树中最大的结点度。
叶子结点是离散数学中的概念。一棵树当中没有子结点（即度为0）的结点称为叶子结点，简称“叶子”。 叶子是指度为0的结点，又称为终端结点。
【二叉树定义】
二叉树在图论中是这样定义的：二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。
【例题】
一棵树度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1，则这棵树的叶子节点个数为多少？
解：因为任一棵树中，结点总数=度数+1，所以：
n0+4+2+1+1 = （n0*0 + 1*4 + 2*2 + 3*1 + 4*1）+1
则：n0=8
其中：n0表示叶子结点。
【如何统计叶子结点的数目】
该算法的递归形式比较容易实现。
具体的代码块如下：
int leaf(BiTree root)
{
static int leaf_count = 0; --->在递归调用时只进行一次初始化。
if (NULL != root) {
leaf(root->lchild);
leaf(root->rchild);
if (root->lchild == NULL
&& root->rchild == NULL)
leaf_count++;
}
return leaf_count;
}
该算法的代码模块的独立性算是设计的比较好的。
耦合比较底，传入树的树根，返回树的叶子节点的个数。
内聚比较高，模块中的代码比较紧密。容易阅读，易维护。
该算法是用递归实现的，效率肯定不是很高。
该算法是在对树的后序遍历的基础上实现的。如果该节点的左子树，再右子树，最后是根节点。
