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

[单选题]

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

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

查看正确选项

点滴快乐

度为0的结点总是比度为2的结点多1，即n0 = n2+1;

发表于 2017-08-25 11:47:42 回复(0)

一瓢之饮

度为2的结点n2,度为1的结点n1，度为0的结点n0

总度数为 n = 2*n2+1*n1

总结点数 ~n = n2+n1+n0

n = ~n - 1 ==> n0 = n2+1 = 11

发表于 2017-08-18 11:39:18 回复(0)

colining

总有人和我一样不知道这个公式吧；传送门

性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)="0度结点数(n0)" + "1度结点数(n1)" + "2度结点数(n2)"。由此，得到等式一。
(等式一) n=n0+n1+n2
另一方面，0度结点没有孩子，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：n1+2n2。此外，只有根不是任何结点的孩子。故二叉树中的结点总数又可表示为等式二。
(等式二) n=n1+2n2+1
由(等式一)和(等式二)计算得到：n0=n2+1。原命题得证！

编辑于 2017-08-19 13:26:25 回复(1)

风清扬゛

二叉树中，节点就只有三种可能，度为0的节点n0，度为1的节点n1，度为2的节点n2，则节点总数n = n0 + n1 + n2; 孩子节点总数n‘ = 0 * n0 + 1* n1 + 2 * n2，则总的节点数n = 孩子节点数 + 根节点(不是任何节点的孩子，所以要单独加上他) = n' + 1 = n1 + 2*n2 + 1；

所以 n0 + n1 + n2 = n1 + 2*n2 + 1 =》 n0 = n2 + 1;

度为0的节点数 = 度为2的节点数 +1

发表于 2019-04-04 11:49:22 回复(0)