具有n层结点的平衡二叉树至少有几个节点

问题描述

精选答案

至少有12个结点。

分析过程如下：

因为根结点层次为1，则高度为h的平衡二叉树最少有F(h + 2) -1个结点；

其中F 为Fibonacci序列1, 1, 2, 3, 5, 8, 13, 21,...；

Fibonacci数列种，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子数的节点数量；

易知F(1)=1，F(2)=2，F(3)=4 ；

F(5)=F(4)+F(3)+1=2*F(3)+F(2)+2；

因为F(2)=2，F(3)=4；

故F(5)=2*F(3)+F(2)+2=2*4+2+2=12；

即具有5层结点的平衡二叉树至少有12个结点。

此题利用了平衡二叉树的性质解题。