校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 二叉树相关概念
题目

若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是()

A.9

B.11

C.15

D.不确定

解答

正确答案是 B

在任意一棵二叉树中,若终端结点的个数为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。原命题得证

C 5条回复 评论
我吃小朋友

哇,好棒啊,崇拜的小眼神

发表于 2022-12-27 23:00:00
0 0
wyj

真的好拼呀

发表于 2022-01-17 23:00:00
0 0
改造家

度为0的节点数为度为2的节点数加1

发表于 2018-10-23 11:23:34
0 0
心意

度为2的结点n2,度为1的结点n1,度为0的结点n0
总度数为 n = 2*n2+1*n1
总结点数 ~n =  n2+n1+n0
n = ~n - 1   ==> n0 = n2+1 = 11

发表于 2018-10-23 11:23:17
0 0
途安米

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

发表于 2018-10-23 11:23:03
0 0