完全二叉树叶子节点的算法

求讲解...不要百科上的.就是公式:n0＝（n＋1）/2怎么推导的- -谢谢了

chiconysun · 2018-4-30 01:54:31

设二叉树中度为0叶子有n0个，度为1 结点有n1 个，度为2 结点有n2个
n0 + n1 + n2 = n (1)
按照二叉树性质：n0 = n2 + 1，也就是n2 = n0 -1
于是代入(1) 得：2n0 + n1 - 1 = n
按照完全二叉树性质，度为1 的结点最多1个
因此当n为偶数时，n1 = 1，因此n0 = n / 2
当n为奇数时，n1 = 0，因此n0 = (n + 1)/2
合并这两个结果有：n0 = (n + 1)/2 ，实际是整数除法，也就是下取整

热心网友 · 2018-4-30 01:54:32

设二叉树的叶子节点数为n0，度数为2的节点数为n2.设n1为二叉树中度为1的节点数。因为二叉树中所有节点的度都钓鱼或者等于2，所以二叉树节点总数n=n0+n1+n2再看二叉树的分支数，除了根节点外，其余节点都有一个分支进入，设B为分支总数，则n=B+1。由于这些分支都是有度为1或者2 的节点射出的，所以B=n1+n2;于是有：n=n1+2*n2+1；综合n=n0+n1+n2和n=n1+2*n2+1两式即可得到n0=n2+1；完全二叉树是特殊的二叉树，对于n0=n2+1当然成立。

热心网友 · 2018-4-30 01:54:33

仔细想想 1 2 4 8完全二叉树其实就是一个等比数列吗这么一说你应该会推导了吧

完全二叉树叶子节点的算法

3 个回复