Question

一棵有124个叶结点的完全二叉树，最多有多少结点？

Answer 1

最多有248个结点。

根据完全二叉树性质，叶子结点数n0等于树结点数n的二分之一，即n0=n/2，或叶子结点数n0等于树结点数n加上1之和的二分之一，即n0=(n+1)/2。

两个公式变形得，n=2*n0或n=2*n0－1，题中要求树的最多结点数，即树的结点数等于叶子数的2倍，n=2*n0＝2*124＝248。

扩展资料：

完全二叉树性质推导：

假设n0是度为0的节点总数（即叶子结点数），n1是度为1的节点总数，n2是度为2的节点总数。

因为n=n0+n1+n2（其中n为完全二叉树的节点总数），又因为一个度为2的节点会有2个子结点，一个度为1的结点会有1个子结点，除根结点外其他节点都有父结点，得到n=1+n1+2*n2；

由n=n0+n1+n2和n=1+n1+2*n2两式把n2消去得：n=2*n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=n/2或n0=(n+1)/2。

简便来算，就是n0=n/2，其中n为奇数时（n1=0）向上取整；n为偶数时（n1=1）向下取整。可根据完全二叉树的结点总数计算出叶子结点数。

参考资料来源：百度百科—完全二叉树

参考资料来源：百度百科—叶子结点