树中的叶子结点的个数-计算方法

2023-03-03学习1 分钟264 次阅读
AI 摘要salmon-ai

本文讲解了树中叶子结点个数的计算方法,通过建立不同度数结点数量与边数之间的关系,推导出叶子结点(度为0的结点)数量的通用公式:n0 = n2 + 2n3 + 3n4 + … + 1。文章结合两

树中的叶子结点的个数 计算方法

在学习树的时候经常会遇到计算树中叶子结点的个数的题,比如现在有这样一道题。

例1

已知在一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶子结点的个数为?

解决这道题的思路是列出一个关于各个度的结点的等式,从而根据已知条件算出度为0的结点的个数,下面具体说一下解题方法:

设树T中的结点个数为n,度为0的结点的个数为n0,度为1的结点的个数为n1,度为2的结点的个数为n2,度为3的结点的个数为n3,度为4的结点的个数为n4,则有:

复制代码
n = n0 + n1 + n2 + n3 + n4

设树T中的总边数为e,因为除了根节点的入度为0,其余各节点的入度都为1,则有:

复制代码
e = n - 1 = n0 + n1 + n2 + n3 + n4 - 1

又因为,n0的出度为0,n1的出度为1,n2的出度为2,n3的出度为3,n4的出度为4,所以:

复制代码
e = n0 * 0 + n1 * 1 + n2 * 2 + n3 * 3 + n4 * 4

综上所述:

复制代码
e = n0 * 0 + n1 * 1+ n2 * 2 + n3 * 3 + n4 * 4 = n0 + n1 + n2 + n3 + n4 - 1,
n0 = n2 + n3 * 2 + n4 * 3 + 1

根据题意,n2 = 1, n3 = 10 , n4 = 20 ,代入得:

复制代码
n0 = 82

因此该树T有82个叶子结点

例2

一棵度为3的树中,有3度的结点100个,有2度的结点200个,有叶子结点多少个?

复制代码
n = n0 + n1 + n2 + n3,//总结点数
e = n - 1 = n - n0 + n1 + n2 + n3 -1,//边数
e = 3 * n3 + 2 * n2 + 1 * n1 + 0 * n0,//边数
n - n0 + n1 + n2 + n3 -1 = 3 * n3 + 2 * n2 + 1 * n1 + 0 * n0,
n0 = n2 + n3 * 2 + 1,//代入n2 = 200, n3 = 100,
n0 = 401个
觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句