某二叉树中有n个度为2的结点,则该二叉树中的叶子结点为

论坛 期权论坛 期权     
846275084   2018-4-26 13:40   4329   1
分享到 :
0 人收藏

1 个回复

倒序浏览
2#
wxhsun  2级吧友 | 2018-4-30 02:32:46 发帖IP地址来自
n+1

对任何一棵二叉树T,如果其终端节点数为n0,度为2的节点数为n2,则n0=n2+1.
设n1为二叉树T中度为1的结点数.因为二叉树中所有结点的度军小于或等于2,所以其结点总数为
n=n0+n1+n2    (1)
再看二叉树中的分支数.除了根结点外,其余结点都有一个分支进入,设B为分支总数,则n=B+1.由于这些分支是由度为1或2的结点射出的,所以B=n1+2n2.于是得
n=n1+2n2+1    (2)
由式(1)(2)得
n0=n2+1
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:
帖子:
精华:
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP