数据结构：树相关的一些知识点（考研）

1.叶子节点和度为二节点个数之间的关系从两方面考虑。 （1）节点个数：在二叉树中，由度为0，1，2三种节点组成，因此其总的节点个数:n=n0+n1+n2。 （2）从分支考虑，n个节点中除了根节点没有前驱节点，其他节点有且仅有一个前驱节点。因此构成了n-1条边，这n-1条边是由度为0，1，2的节点扩散出来的，同时它们的扩散的边也为0，1，2，因此可以得到第二个方程:n-1 = 0*n0 + 1*n1 + 2*n2

2.树中节点总的个数等于所有节点的度加1。 可以这样理解，在树中，除了根节点之外，其余节点(n-1个)有且仅有一个前驱节点，也构成了n-1条边。考察树中每一个节点的度数之和，正是这n-1条边。因此n-1=树中所有节点的度之和，立即推n=所有节点度之和+1。

3.度为m的树中在第k层最大节点个数为m^(k-1)

4.高度为h的m叉树至多有(m^h-1)/(m-1)个节点。换句话说，就是高度为h的m叉满树节点个数为多少。 其实就是求解等比数列的前n项和1, m, m^2, m^3,...,m^h-1

5.具有n个节点的m叉树的最小高度为：ceil(logm[n*(m-1) + 1])，最大高度为n-m+1。