【数据结构】树的基本性质(计算树的总结点数与叶结点数)

树的基本性质

• ⭐️计算树的总结点与叶结点数
• • 💫性质1
  • 💫性质2
  • 💫例题1
  • 💫例题2

⭐️计算树的总结点与叶结点数

💫性质1

性质1 树中的结点数等于所有结点的度数之和加1

例如上面这棵树，A的孩子为B、C、D，A的度数为3；B的孩子为E、F，B的度数为2；C的孩子为G，C的度数为1；D的孩子为H、I，D的度数为2…

结点数=A的度数+B的度数+C的度数+D的度数+…+J的度数+K的度数+L的度数+M的度数+1

＝(B+C+D)+(E+F)+G+(H+I)+…+0+0+0+0+1

也就是结点数等于每个结点的孩子树之和(度之和)再加1，这个1就是根节点。

总结点数：n=13;

树的度：m=3;

n0(度为0的结点数)=7；

n1(度为1的结点数）=2；

n2(度为2的结点数) =2；

n3(度为3的结点数)=2；

n

=

7

∗

0

+

2

∗

1

+

2

∗

2

+

2

∗

3

+

1

n=7*0+2*1+2*2+2*3+1

n=7∗0+2∗1+2∗2+2∗3+1

💫性质2

性质2 结点表示个数：n为总结点个数，

n

i

{n_i}

ni​为度为i(0≤i≤m)的结点个数，则

n

=

n

0

+

n

1

+

.

.

.

+

n

m

{n=n_0+n_1+…+n_m}

n=n0​+n1​+…+nm​

对于上面这棵树

总结点树 n=13；

这树的度数m=3；

n

0

{n_0}

n0​=7;

n

1

{n_1}

n1​=2;

n

2

{n_2}

n2​=2;

n

3

{n_3}

n3​=2;

n

=

n

0

+

n

1

+

n

2

+

n

3

n={n_0+n_1+n_2+n_3}

n=n0​+n1​+n2​+n3​

对于上面两种计算树的结点的方法，我认为一个是从一个结点本身出发，计算它自己本身；另一种是从它的孩子出发，计算之和 ，但由于这样树的根节点没有被纪录，所以不要忘了加1。

💫例题1

一颗树度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶子结点个数为（）

A.41 B.82 C.113 D.122

分析：

从两种角度出发：

从结点自身：

总结点

n

=

20

+

10

+

1

+

10

+

n

0

n=20+10+1+10+n_0

n=20+10+1+10+n0​

从结点的孩子：

总结点

n

=

20

∗

4

+

10

∗

3

+

1

∗

2

+

10

∗

1

+

1

n=20*4+10*3+1*2+10*1+1

n=20∗4+10∗3+1∗2+10∗1+1

联立上面两式，可以解得

n

0

=

82

n_0=82

n0​=82

💫例题2

已知一棵树度为m的树中有

n

1

n_1

n1​个度为1的结点，

n

2

n_2

n2​个度为2的结点，…,

n

m

n_m

nm​个度为m的结点，问该树中有多少个叶子结点？

设总结点n

则

n

=

n

1

+

n

2

+

.

.

.

+

n

m

+

n

0

n=n_1+n_2+…+n_m+n_0

n=n1​+n2​+…+nm​+n0​

且

n

=

1

∗

n

1

+

2

∗

n

2

+

3

∗

n

3

+

.

.

.

+

m

∗

n

m

+

1

n=1*n_1+2*n_2+3*n3+…+m*n_m+1

n=1∗n1​+2∗n2​+3∗n3+…+m∗nm​+1

联立解得，

n

0

=

n

2

+

2

n

3

+

3

n

4

+

.

.

.

+

(

m

−

1

)

n

m

+

1

n_0=n_2+2n_3+3n_4+…+(m-1)n_m+1

n0​=n2​+2n3​+3n4​+…+(m−1)nm​+1