您的当前位置：首页正文

叶子结点

2024-11-18 来源：个人技术集锦

叶子结点
叶子结点是离散数学当中的概念。一棵树当中没有子结点（即度为0）的结点，称为叶子结点，简称“叶子”。叶子是指度为0的结点，又称为终端结点。

叶子结点就是度为0的结点就是没有子结点的结点

n0：度为0的结点数，n1:度为1的结点 n2：度为2的结点数。 N是总结点
在二叉树中：
n0=n2+1；

N=n0+n1+n2

例题
一棵树度为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表示叶子结点。

完全二叉树算法：

可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0=n2+1，则n= n0+n1+n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=(n+1)/2或n0=n/2。
总结起来，就是 n0=[n/2]，其中[]表示上取整。可根据完全二叉树的结点总数计算出叶子结点数。