具有n个节点的度为m的树的最大高度和最低高度推导

一、最大高度

试想一下，若有n个节点的度为m的树，当只有最后一层有m个节点，其余层均只有一个节点，在所有含有nn个节点的度为m的树中一定是最高的。

二、最低高度

当每个非终端节点均含有m个孩子节点时间，此时整棵树在所有含有n个节点的度为m的树中是最矮胖的，此时这棵树的高度也是含有n个节点度为m的树中高度最低。在极限的状态下可以称之为满m叉树，因此可以推导不等式，得出最低高度。

结论：综上分析，对于一个含有n个节点的度为m的树的高度范围为：ceil(logm((m-1)*n + 1) <= h <= n-m+1