一、最大高度
试想一下,若有n个节点的度为m的树,当只有最后一层有m个节点,其余层均只有一个节点,在所有含有nn个节点的度为m的树中一定是最高的。
二、最低高度
当每个非终端节点均含有m个孩子节点时间,此时整棵树在所有含有n个节点的度为m的树中是最矮胖的,此时这棵树的高度也是含有n个节点度为m的树中高度最低。在极限的状态下可以称之为满m叉树,因此可以推导不等式,得出最低高度。
结论:综上分析,对于一个含有n个节点的度为m的树的高度范围为:ceil(logm((m-1)*n 1) <= h <= n-m 1