我要招人

去企业版

首页 > 试题广场 >

对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总

[填空题]

对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为？1

查看正确选项

K1890

证明过程如下：
假设二叉树的0度,1度,2度结点为n0,n1,n2,总节点数为T
则有按照结点求和的
T = n0 + n1 + n2 （1）
按照边求和得：
T = n1 + 2 * n2 + 1 （2）
所以（2） - （1）可得
n2 + 1 - n0 = 0
所以n0 = n2 + 1

发表于 2019-08-11 13:16:22 回复(3)

pein531

特殊值法：既然任意二叉树都满足，那随便举一个满二叉树肯定也满足，假如有一棵有7个节点的满二叉树，度为0的节点为叶子节点，一共N0=4个，度为2的节点为非叶子节点，一共N2=3个，因此N2=N0-1

发表于 2021-02-18 21:05:15 回复(0)

雄心饽饽且谦恭温逊

N0－1

发表于 2020-05-21 22:22:37 回复(0)

漂流一只Fan

N0-1

发表于 2020-05-15 13:03:53 回复(0)

new世界

设一棵二叉树中度为0，1，2的结点个数分别为n₀、n₁、n₂。

从上往下看：

边数 = n₁+2*n₂ （1）

从下往上看：除了根节点，每个结点都有父结点，所以子结点到父结点有一条边。

变数 = n₀+n₁+n₂-1 （2）

解（1）（2）得：

n₀-1=n₂。

编辑于 2020-05-13 00:23:50 回复(0)

牛客797079600号

n0-1

发表于 2020-05-10 20:14:07 回复(0)

EdwardZhao

发表于 2020-04-29 12:35:29 回复(0)

刘铭悦

N0-1

发表于 2020-04-29 10:30:54 回复(0)

学数据结构的小白

N2=N0-1

发表于 2020-04-09 20:12:25 回复(0)

仙女培

n0-1

发表于 2020-03-27 19:31:51 回复(0)

牛客402550302号

节点总数为N，N=n0+n1+n2

N= 1+n1+2*n2

得n2=n0-1

编辑于 2020-03-28 20:37:26 回复(0)

琥珀川中行

N0-1

发表于 2020-03-21 23:43:54 回复(0)

客栈的小二

no-1

发表于 2020-03-16 14:09:43 回复(0)

fantianyulu

度是节点的分叉数，也就是出度

发表于 2020-03-13 23:35:38 回复(0)

牛客524086029号

N0-1

发表于 2019-12-27 15:08:48 回复(0)

SpriteNevGp

n0-1

发表于 2019-12-15 22:35:46 回复(0)

牛客70985747号

no＝n2＋1

发表于 2019-12-11 23:36:15 回复(0)

牛客106468492号

N0-1

发表于 2019-12-09 23:52:28 回复(0)

chanicia

N0-1

发表于 2019-11-25 21:25:38 回复(0)

来做题了

N2=N0-1

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

提交观点

问题信息

C++工程师瓜子二手车算法工程师树 2019 Java工程师

上传者：小小

难度：

30条回答 56收藏 3900浏览

对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总

问题信息

热门推荐

相关试题