平衡二叉树高为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,非叶结点的...的网友还看了以下：

如图为一个真核基因的结构示意图，根据图中所示，对该基因特点叙述正确的是（）A.非编码区是外显子，编　2020-04-08 …

英语翻译我是属猴的,所以我最喜欢的动物是猴子,因为它全身毛毛的非常可爱．它们和人类很相似,非常聪明　2020-05-13 …

人工合成的目的基因缺少内含子与非编码区,会影响基因表达,这是为什么呢?内含子与非编码区是什么?有什　2020-05-17 …

● 对于二叉查找树(Binary Search Tree) ,若其左子树非空,则左子树上所有结点的值　2020-05-26 …

对于二叉查找树(Binary Search Tree),若其左子树非空,则左子树上所有结点的值均小于　2020-05-26 …

生命科学研究:蛋白质分子是非常复杂的链,可以表示为无数个3D图形。在将蛋白质放到某种溶液中时,它们会　2020-05-31 …

“君子生非异也,善假于物也.”“如果说我比别人看得更远些,那是因为我站在巨人的肩上.”这两句话“君　2020-06-04 …

心头十八添一笔.你旁立人非余地.王爷呒有脊梁骨.白头汉子冒舌压.一点一横散光眼.扁担棍子合交叉.二人　2020-11-25 …

树的后根遍历序列等同于该树对应的二叉树的A．先序序列B．中序序列C．后序序列D．层次序列52．对于前　2020-12-05 …

求p所指结点的中序后继算法设指针p指向二叉树中的某个结点,且该结点的左右子树非空,写出求p所指结点的　2020-12-05 …