完全二叉树的叶子节点数公式是什么？

发布网友发布时间：2022-04-20 21:45

共1个回答

热心网友时间：2023-10-23 22:21

完全二叉树的叶子节点数公式为：设叶子节点数为n0, 度为1的节点数为n1，度为2的节点数为n2，总节点为n。

1、当n为奇数时（即度为1的节点为0个），n0= (n+1)/2。

2、当n为偶数（即度为1的节点为1个）， n0= n/2。

n1，n2，都可以求。

完全二叉树的特点：

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

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

完全二叉树的性质：

1.具有n个结点的完全二叉树的深度为logn+1。

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

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

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

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