首页 > 其他 > 详细

为什么二叉树的叶子结点数等于度为2的结点数+1

时间:2020-05-12 13:50:58      阅读:65      评论:0      收藏:0      [点我收藏+]

假设:

二叉树的结点数为n,

叶子结点数为n0,

度为1的结点数为n1,

度为2的结点数为n2,

边的数量为b

 

则有:n = n0 + n1 + n2;

   b = n - 1;(树的性质:边数量 = 结点数 - 1) 

变形:b = n0 + n1 + n2 - 1;

     b = n1 + 2 * n2;(度为1的结点有一条边,度为2的结点有两条边)

所以:n0 + n1 + n2 - 1 =  n1 + 2 * n2

   n0 - 1 = n2

   n0 = n2 + 1

为什么二叉树的叶子结点数等于度为2的结点数+1

原文:https://www.cnblogs.com/xuecl/p/12875642.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!