完全二叉树的叶子节点数公式为:设叶子节点数为n0, 度为1的节点数为n1,度为2的节点数为n2,总节点为n。
1、当n为奇数时(即度为1的节点为0个),n0= (n+1)/2。
2、当n为偶数(即度为1的节点为1个), n0= n/2。
完全二叉树的性质:
1、具有n个结点的完全二叉树的深度为logn+1。
2、如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i,有:
(1)如果i=1,则结点i是二叉树的根节点,无双亲;如果i>1,则其双亲是结点⌊i/2⌋。
(2)如果2i>n,则结点i无左孩子;否则其左孩子是结点2i。
(3)如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1。