高度为n的平衡二叉树最少需要多少个节点

递推关系
A(1)=1
A(2)=2
A(n+2)=A(n+1)+A(n)+1
子树高度为n+1,n以及根节点
你可以照这个以此类推就可以得出答案了。算下A（4）=7

 

 

设f（n）为高度为n的平衡二叉树最少含有的节点数，则：f(1) = 1;f(2) = 2; f(3) = 4;f(4) = 7;……

这些可以通过画图就能得到，但是当n很大时呢？其实有如下结论：f(n) = f(n-1) + f(n-2) +1,(n>=3)。这个递推结论如何得到的呢？

引导问题：求一棵二叉树的节点数目：

假设一颗二叉树T，其左右子树分别为TL,TR。又假设T的节点数目为F(T),TL，TR的节点数目分别为F(TL),F(TR)。则显然：

F(T) = F(TL) + F(TR) + 1。

本文的问题：求高度为n的平衡二叉树最小需要多少节点：

同样假设T为高度为n的平衡二叉树，其需要最少的节点数目为F(n)。又假设TL，TR为T的左右子树，因此TL，TR也为平衡二叉树。假设F1,F2为TL，TR的最少节点数，则，F(n) = F1+F2 +1。那么F1,F2 到底等于多少呢？由于TL，TR与T一样是平衡二叉树，又由于我们知道T的最少节点数是F(n),其中n为T的高度，因此如果我们知道TL，TR的高度就可以知道F1,F2的值了。由平衡二叉树的定义可以知道，TL和TR的高度要么相同，要么相差1，而当TL与TR高度相同(即:都等于n-1)时，我们算出来的F(n)并不能保证最小，因此只有当TL与TR高度相差一(即：一个高度为n-1，一个高度为n-2)时，计算出来的F(n)才能最小。此时我们假设TL比TR高度要高1(即：TL高度为n-1，TR高度为n-2)，则有：F1 = F(n-1),F2 = F(n-2)。因此得到结论：F(n) = F(n-1) + F(n -2 ) + 1!

这个地方推导思路稍微有点不清晰，应该都能明白，这个问题本来是很简单的问题，通过这个问题，我们可以看出递归的思想在树结构中的重要性，通过递归将问题抽象为多个规模更小的同类问题是解决这类问题的关键！当然，编程计算的时候一般用递推来计算较好(递归时会使用函数堆栈，函数堆栈是有限的，小心溢出).