完全二叉树已知总结点求叶结点

n个结点的完全二叉树,则其中叶子结点的个数是____

注释:性质详见白皮书P372~373;

①公式:设叶结点个数为i,总结点数为n则有

i=floor(n+1)/2  注:floor为取整。

注:经过反复证明公式是正确的,可直接使用。

公式版权所有——历城二中信息学奥赛。

②由性质52*i>n时没有左孩子(因为是完全二叉树所以也没右孩子);

所以i为叶子结点;

求出i的最小值;

n-i+1 即叶子结点数。    

③由性质4求出层数k

由性质2求出若为满二叉树时的总结点数X=2^k-1

由性质1Y=2^k-1),即第k层的结点最大数;

Z=(X-n)/2取整即第k-1层的叶结点数;

X-(2^(k-1)-1)最后一层叶结点数;

总叶结点数:(X-n)/2+X-(2^(k-1)-1)

性质1:二叉树第i层上最大有2^(i-1)结点;

性质2:深度为k的二叉树最大有2^k-1个结点;

性质3:任意二叉树,叶结点数为n0,度为2的结点数为n2,则n0=n2+1

性质4:具有n个结点的完全二叉树深度为floorlog 2 n+1

性质5:具有n个结点的完全二叉树,任意结点为i

       2*i>n 的结点为叶结点;

       2*i+1>n的结点无左孩子。

原文地址:https://www.cnblogs.com/wty20010315/p/5517067.html