非空二叉树的一个有趣的性质:n0 = n2 + 1

2015-05-09 08:27  星星之火✨🔥  阅读(5803)  评论(3)  编辑  收藏  举报

对任何非空二叉树T，若n0 表示叶结点的个数、n2 表示度为2 的非叶结点的个数，那么两者满足关系n0 = n2 + 1。

这个性质很有意思，下面我们来证明它。

证明：首先，假设该二叉树有N 个节点，那么它会有多少条边呢？答案是N - 1，这是因为除了根节点，其余的每个节点都有且只有一个父节点，那么这N 个节点恰好为树贡献了N - 1 条边。这是从下往上的思考，而从上往下(从树根到叶节点)的思考，容易得到每个节点的度数和 0*n0 + 1*n1 + 2*n2 即为边的个数。

因此，我们有等式 N - 1 = n1 + 2*n2，把N 用n0 + n1 + n2 替换，得到n0 + n1 + n2 - 1 = n1 + 2*n2，于是有

　　　　n0 = n2 + 1。命题得证。

网址：非空二叉树的一个有趣的性质:n0 = n2 + 1 http://c.mxgxt.com/news/view/183368

相关内容

一个内心强大的人，身上往往兼有男性女性特质
我妈常说 “客厅有树，十有九富”！适合客厅放的6种树，“富贵人家”都爱养！
叉开腿坐才是最健康的坐姿？骨科专家提醒
趣谈十二星座的大明星潜质
如何跟明星一样成穿搭达人？这一招很有必要学
十二星座性格12星座(12星座的全部性格)
个人的形象管理.docx
二次函数的概念及y=ax^2(a≠0）、y=ax^2+c(a≠0）的图象与性质
难怪人参果树天地间仅此一棵，你看看菩提祖师对孙悟空说了啥
《西游记》猪八戒为何一直挤兑孙悟空？其中有三个原因！

随便看看