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

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

💫性质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\ast 0+2\ast 1+2\ast 2+2\ast 3+1$

💫性质2

性质2 结点表示个数：n为总结点个数，$n_i$为度为i(0≤i≤m)的结点个数，则$n=n_0+n_1+...+n_m$

对于上面这棵树

总结点树 n=13；
这树的度数m=3；
$n_0$=7;
$n_1$=2;
$n_2$=2;
$n_3$=2;
$n=n_0+n_1+n_2+n_3$

对于上面两种计算树的结点的方法，我认为一个是从一个结点本身出发，计算它自己本身；另一种是从它的孩子出发，计算之和 ，但由于这样树的根节点没有被纪录，所以不要忘了加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\ast 4+10\ast 3+1\ast 2+10\ast 1+1$
联立上面两式，可以解得$n_0=82$

💫例题2

已知一棵树度为m的树中有$n_1$个度为1的结点，$n_2$个度为2的结点，…,$n_m$个度为m的结点，问该树中有多少个叶子结点？

设总结点n
则$n=n_1+n_2+...+n_m+n_0$
且$n=1\ast n_1+2\ast n_2+3\ast n3+...+m\ast n_m+1$
联立解得，$n_0=n_2+2n_3+3n_4+...+(m-1)n_m+1$