平衡二叉树高为6,非叶结点的平衡因子都为1,则节点总数是多少?为啥是20?求详解

题目详情

平衡二叉树高为6,非叶结点的平衡因子都为 1,则节点总数是多少?为啥是20?求详解

▼优质解答

答案和解析

显然这棵平衡二叉树为高度为6的最少结点数量
设 N 是深度为 h 的平衡二叉树的最少结点数,对于 h >= 1,有 N = F(h + 2) - 1 成立,其中的F(n)为Fibonacci 数列：1,1,2,3,5,8,13,21,34,55,...
于是对于h = 6,得到F(6 + 2) = 21,所以结点数目为21 - 1 = 20
那个公式的推导过程可以去参看比较全的数据结构教材

看了平衡二叉树高为6,非叶结点的...的网友还看了以下：

亚铁离子与高锰酸根离子反应达化学计量点时各离子间的关系是啥?为什么? 　2020-05-14 …

化学平衡常数原理是啥为啥就是那个关系　2020-05-14 …

有100个数,将它们2个2个一组合,可以有多少个组合?为什么?.这简单的除法我突然想不出道理了,道　2020-06-08 …

3次根号下a的立方的意思是啥啊结果是啥　2020-06-23 …

如何做下面的化学问题在氢氧化钡晶体与氯化铵晶体的反应中,为什么即使不结冰,烧杯与玻璃片还是粘在一起　2020-06-26 …

问is和are“就近原则”具体规则是什么?例题：Whereyourforkandknife?Ais 　2020-06-30 …

从分子的角度分析，下列解释正确的是（）A．水降温会结冰，是因为结冰时水分子静止不动B．热胀冷缩-分　2020-07-05 …

找规律题31415926.后面是啥为什么　2020-07-17 …

假定用两个一维数组L[n+1]和R[n+1]作为有n个结点的二叉树的存储结构,L[i]和R[i]分　2020-08-03 …

二次函数为什么a决定开口大小,a的绝对值和开口大小关系是啥,为什么　2020-11-04 …