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

2022-02-25 08:28:19 浏览数 (1)

一、最大高度

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

二、最低高度

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

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

0 人点赞