对任意一棵二叉树T，H(T)表示树的高度。若树T含有n个结点

[单选题]

对任意一棵二叉树T，H(T)表示树的高度。若树T含有n个结点，那么（）

```
H(T)=O(n)
```
```
H(T)≤O(logn)
```
```
H(T)=O(logn)
```
```
H(T)≥O(logn)
```

推荐

白驹之过隙

选D。考察的是二叉树的性质：高度为H的二叉树至多有 2^H+1 -1 个结点。

如下图所示：满二叉树结点数最多，为15。高度为3。即：n<= 2^H+1 -1 ；logn<= H

转化为：H(T)≥O(logn)

编辑于 2019-05-28 15:02:45 回复(3)

houziqiang

完全二叉树的高度最小是log(n),所以树高应该大于等于log(n)

发表于 2019-05-27 21:03:26 回复(0)

choice240701

树的高度和树的第几层要区分开

发表于 2020-04-21 18:58:13 回复(0)

Cara_Smith

设高度为x。根据上一题得，叶子节点数n0＝(n+1-n1)/2。则:2ˣ≥(n+1-n1)/2⇨2ˣ⁺¹≥n+1-n1(n1=1或0)⇨log(x+1)≥log(n+1-n1)。当n1＝0即该二叉树为完全二叉树时满足:log(x+1)≥log(n+1)⇨H(T)=log(x)≥log(n)，故完全二叉树也满足此定律，选择D选项。

编辑于 2024-04-16 02:40:29 回复(0)