首页 > 试题广场 >

对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为

[问答题]

对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，推导n0和n2的关系。

牛客882122502号

二叉树部分的重要公式：非空二叉树的叶子结点数等于双分支结点数加1，即n₀=n₂+1;

推导：设二叉树上的叶子结点数为n₀，单分支结点数为n₁，双分支结点数为n₂；

则总的结点数为n=n₀+n₁+n₂;

二叉树中，所有结点的分支数应等于双分支结点数的两倍，即总的分支数=n₁+2n₂；

由于二叉树中除了根节结点每个结点都有唯一的一个分支指向它，

总结点数=总分支数+1

n₀+n₁+n₂=n₁+2n₂+1;

可以得到n₀=n₂+1;

编辑于 2021-04-10 10:06:34 回复(0)

DonMuv

叶子结点数=双结点数＋1

发表于 2019-11-05 10:17:28 回复(0)

大蛭若鱼

n-1=2*n2+n1 ,n=n0+n1+n2. 解得n2+1=n0.

发表于 2019-10-14 18:03:45 回复(0)

灰蒙

设一颗二叉树上叶子结点数为n₀，单分支结点数为n₁，双分支结点数为n₂，则总结点数为：n₀+n₁+n₂。

而一颗二叉树中，所有结点的分支数（即度数）应等于单分支结点数加上双分支结点数的两倍，即总分支数=n₁+2n₂。

由于二叉树中除了根结点以外，每个结点都有唯一的一个分支指向它，因此二叉树中：总分支数=总结点数-1。

即n₁+2n₂=n₀+n₁+n₂-1。即n₀=n₂+1。

发表于 2021-12-19 16:25:07 回复(1)

提交观点

问题信息

树

上传者：城市里的养猫者

难度：

4条回答 2收藏 3129浏览

扫一扫，把题目装进口袋