Java教程

已知树中非叶子节点的度数和数量,如何计算树中叶子节点的个数?

本文主要是介绍已知树中非叶子节点的度数和数量,如何计算树中叶子节点的个数?,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

树的一些定义

1、一棵树的度树指其中节点的度数最大值。

2、一个节点的度数为该节点的子节点数量,显然叶子节点度数为0。

3、树中的边和节点的关系有:节点数=边数+1。

也就是说每条边代表一个度数,而树的根节点例外,所以树的总节点数=总度数+1。


示例

1、节点 A 的度数为3,节点 C 的度数为1,节点 F 的度数为0。

2、这棵树的度数为 A 节点的度数,为3。


题目

已知一棵树中度数为1的节点有4个,度数为2的节点有3个,度数为3的节点有2个,度数为4的节点有2个。

则该树中有多少个叶子结点?


求解

这里假设树中有 S 个结点,根据定义可知,树的总度数则为 S-1;

再假设树中有 X 个叶子结点,则能得出式子

S = X + 4 + 3 + 2 + 2
S-1 = 0*X + 1*4 + 2*3 + 3*2 + 4*2

两个方程式,求解两个未知数,这是必然能够解出来的,求得

S = 25
X = 14

因此,树中有 14 个叶子结点。

这篇关于已知树中非叶子节点的度数和数量,如何计算树中叶子节点的个数?的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!