首页 > 其他 > 详细

【数据结构】【树】二叉树叶子结点与度为2的结点的关系

时间:2021-08-16 10:30:03      阅读:20      评论:0      收藏:0      [点我收藏+]

二叉树 叶子结点 与 度为2的节点关系

在二叉树中,一个结点最多拥有两个儿子结点,因而结点的类型可以分为拥有0个儿子结点的结点\(n_0\),拥有1个儿子结点的结点\(n_1\)和拥有2个儿子结点的结点\(n_2\)?,记总结点个数为S

\[结点数=拥有0个儿子结点的结点+拥有1个儿子结点的结点+拥有2个儿子结点的结点 \]

\[S=n_{0}+n_{1}+n_{2} \]

注意:显然,根结点不是任何结点的子结点

所以有,总儿子结点个数=总结点数-1,记为\(S_{0}=S-1\)

换种角度出发,从儿子结点个数是如何产生的角度来看,有

\(S-1=S_{0}=0\times n_{0}+1\times n_{1}+2\times n_{2}=n_{1}+2n_{2}\)??

即有

\(S=n_{1}+2n_{2}+1\)

\(n_{0}=n_{2}+1\)

而一个结点没有儿子结点,就是说这个结点的度为0,也就是所谓的儿子结点。

所以在一颗二叉树中,叶子结点的个数等于入度为2的结点的个数再加上1.

【数据结构】【树】二叉树叶子结点与度为2的结点的关系

原文:https://www.cnblogs.com/BeautifulWater/p/15145254.html

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