若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为

[单选题]

若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）

```
9
```
```
11
```
```
15
```
```
不确定
```

查看答案及解析

nowscoder

对任何非空二叉树T，若n0 表示叶结点的个数、n2 表示度为2 的非叶结点的个数，那么两者满足关系n0 = n2 + 1。

证明：首先，假设该二叉树有N 个节点，那么它会有多少条边呢？答案是N - 1，这是因为除了根节点，其余的每个节点都有且只有一个父节点，那么这N 个节点恰好为树贡献了N - 1 条边。这是从下往上的思考，而从上往下(从树根到叶节点)的思考，容易得到每个节点的度数和 0*n0 + 1*n1 + 2*n2 即为边的个数。

因此，我们有等式 N - 1 = n1 + 2*n2，把N 用n0 + n1 + n2 替换，得到n0 + n1 + n2 - 1 = n1 + 2*n2，于是有

n0 = n2 + 1

发表于 2018-02-24 21:18:52 回复(0)