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

2024-11-16 00:48:36

推荐回答（5个）

回答（1）：

设：度为i的结点数为ni，由二叉树的性质可知：
n0 = n2 + 1……………………①式
n = n0 + n1 + n2……………②式
由①式可得 n2 = n0 - 1，带入②式得：
n0 = （n + 1 - n1）/ 2
由完全二叉树性质可知：
如图，当n为偶数时，n1 = 1， n0 = n / 2

如图，当n为奇数时，n1 = 0，n0 = （n + 1）/2

将两式合并，写作：n0 = ⌊（n+1）/2⌋（向下取整符号不能丢）

扩展资料：

完全二叉树的特点:

1.叶子结点只可能在层次最大的两层上出现。

2.对任一结点，若其由分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l+1。

完全二叉树的性质：

1.具有n个结点的完全二叉树的深度为⌊log₂n⌋+1。

2.如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i，有：

（1）如果i=1，则结点i是二叉树的根节点，无双亲；如果i>1，则其双亲是结点⌊i/2⌋。

（2）如果2i>n，则结点i无左孩子；否则其左孩子是结点2i。

（3）如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。

回答（2）：

回答（3）：

设二叉树中度为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 ，实际是整数除法，也就是下取整

回答（4）：

设二叉树的叶子节点数为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当然成立。

回答（5）：

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