2

设 n 为二叉树的节点数，那么找出二叉树的最小高度的一般函数项是什么？

我认为这将是 n=floor(log2(n))+1。但是，我想，我错了。

4

3 回答 3

5

看到记住这个概念

为了使高度最小，您必须给出每个级别，它可以容纳的最大节点数

所以对于高度为 h 的树，树总共可以容纳的最大节点数 = 2^(h+1)-1，所以 n<=2^(h+1)-1
解决后你会得到
h>=log(n+1)base2 -1
现在决定 log 的 floor 或 ceil，这样想

如果我的登录是 3.56.. 那么这意味着直到高度 3 每个级别都被完全消耗，最后一个级别没有完全填充。因此，正如高度的定义所说，它是从根到叶的最长路径，所以在高度中我们也将包括最后一层。

因此 ceil 将比 floor 更受欢迎。通过这种方法，您还可以找到 m-ary 树。

于 2014-10-05T10:21:01.650 回答
2

从二叉树高度：

如果你有 N 个元素，二叉树的最小高度将为 log2(N)+1。

于 2012-10-14T19:52:17.540 回答
1

尝试通过归纳来证明这一点。二叉树的类型是归纳的，有两个构造函数：

  • Leaf(v)
  • Node(Tree,Tree)

您现在可以使用结构归纳来显示二叉树的最小高度。要获得最小高度，您有一个完整的二叉树。这是一棵二叉树，对于任何子树，它的子树都具有相同的高度。（这基本上意味着如果你把树画出来，你看不到任何“洞”。）所以假设你有这种类型的树，我们要证明它的高度是floor(log_2(n)) + 1。你可以通过转动它并说：假设我有一棵高度为的树floor(log_2(n))+1，证明它最多有n节点。您可以通过对构造函数的结构归纳来证明这一点。

于 2012-10-14T19:52:48.120 回答